### CS4123 Theory of Computation. B-2002 Solutions Quiz 1 - November 7, 2002

#### Instructions

• Ask in case of doubt

#### Problem I. Variants of Turing Machines (10 points)

A Left-Right-Stay Turing machine is similar to an ordinary Turing machine except that its head can move Left (L), Right (R), or Stay put (S). In other words, its transition function is defined as:
delta : Q x Gamma -> Q x Gamma x {L,R,S},
where S means that the head does not move.
Prove that this variant of Turing machines is equivalent to the ordinary Turing machines. That is, prove the following two facts.
1. (3 points) Given any ordinary Turing machine M, one can construct a Left-Right-Stay Turing machine that simulates M.
```Let's construct a Left-Right-Stay Turing machine T that simulates M.
Note that since M uses only capabilities of ordinary TMs and
Left-Right-Stay machines have those plus more capabilities, then
we can construct T equal to M.

Clearly T is a Left-Right-Stay TM that simulates M.

```
2. (7 points) Given any Left-Right-Stay Turing machine T, one can construct an ordinary Turing machine that simulates T.
```
Let's construct an ordinary Turing machine M that simulates T.
Assume that the state-diagram of T =  is given.
Let's construct the state-diagram of M = .

QM = QT union QS (I'll explain what QS is below)

SigmaM = SigmaT

GammaM = GammaT

deltaM = QM x GammaM -> QM x GammaM x {L,R}

We need to translate any transition (qi,a)->(qj,b,L/R/S) in deltaT
into a valid transition in deltaM, where qi and qj are arbitrary states
in QT and a and b are arbitrary symbols in GammaT.

If the transition in deltaT is of the form (qi,a)->(qj,b,L/R), that is,
it moves the head Left or Right, then we include exactly the same
transition into deltaM.

If the transition in deltaT is of the form (qi,a)->(qj,b,S), that is,
it keeps the head still, then we include both of the following two
transitions into deltaM:

(qi,a) -> (qij,b,R), and
(qij,x) -> (qj,x,L), for each character x in GammaT

Here, qij is a new state that is included in QS (and hence in QM).
Therefore, we get to keep the head still by moving it once to the right
and immediately after once to the left.
(Note that moving the head once to the left and immediately after once
to the right doesn't work since the head wouldn't stay in the same
position if the head is originally pointing to the "triangle" at the
left-end (i.e. beginning) of the tape.)

```

#### Problem II. Decidable languages (10 points)

Let Sigma = {a,b,c}. Show that the following language over Sigma is decidable

L = { w in Sigma* | w contains the same number of occurrences of a's, b's, and c's}

by implementing a Turing machine that decides this language. Note that "bbacbcaac" and "" (the empty word) belong to L, but "babca" doesn't.

1. (2 points) Briefly describe in words the behavior of your machine. State what symbols belong to Gamma (the tape alphabet).
```I'll describe several possible ways of solving this problem.
I'll include below the state-diagram for jsut one of the alternative
approaches, though.

Approach 1:

Gamma = Sigma union {triangle, blank, X}

I'll use an ordinary TM to solve this problem. Initially the input word
is written on the tape and the head is pointing to the first character.
I'll move the head to the right looking for the first non-blank character.
If blank is found, the word is accepted (the input word is the empty word).
Otherwise, I mark the character I found (it can be an a, a b, or a c) with
an X. Then, continue moving to the right looking for a character different
from the one I just marked. If I don't find it (i.e. I reach a blank at the
end of the input string), I reject. If I find it, I mark it with an X.
Then, continue moving to the right looking for a character different
from the two characters I just marked. If I don't find it (i.e. I reach a
blank at the end of the input string), I reject. If I find it, I mark it
with an X and rewind the tape. I repeat this process until either the
process above rejects the input or all the characters on the tape have been
marked, in which case I accept the input.

Approach 2:

Gamma = Sigma union {triangle, blank, X}

I'll use an ordinary TM to solve this problem. Initially the input word
is written on the tape and the head is pointing to the first character.
If the head is pointing to a blank, the word is accepted (the input word
is the empty word). Otherwise, I'll move the head to the right looking for
an a. If I don't find it (i.e. I reach a blank at the end of the input
string), I reject. If I find it, I mark it with an X.
I rewind the tape.
Then, I move the head to the right looking for a b. If I don't find it
(i.e. I reach a blank at the end of the input string), I reject. If I find
it, I mark it with an X.
I rewind the tape again.
Then, I move the head to the right looking for a c. If I don't find it
(i.e. I reach a blank at the end of the input string), I reject. If I find
it, I mark it with an X.
I rewind the tape again and repeat this process until either the
process above rejects the input or all the characters on the tape have been
marked, in which case I accept the input.

Approach 3:

Gamma = Sigma union {triangle, blank}

I'll use a 4-tape Turing machine. Initially the input word is written on
the 1st tape and the 1st head is pointing to the first character.
If the head is pointing to a blank, the word is accepted (the input word
is the empty word). Otherwise, I'll start processing the input word as follows.
If the 1st head is pointing to an a, then I write an a on the 2nd tape and move
the 1st and the 2nd heads to the right once (the other two heads stay put).
If the 1st head is pointing to a b, then I write a b on the 3rd tape and move
the 1st and the 3rd heads to the right once (the other two heads stay put).
If the 1st head is pointing to a c, then I write a c on the 4th tape and move
the 1st and the 4th heads to the right once (the other two heads stay put).
I repeat this process until the 1st head reaches a blank (end of input).
Then I start moving the 2nd, 3rd, and 4th heads simultaneously to the left.
If they all hit the beginning of their respective tapes (triangles) at the
same time, then I accept the word otherwise I reject it.

See David Loose's solution below. He followed this approach.
```
2. (8 points) Provide a state-diagram for your Turing machine. Remember to make all the transitions explicit in the diagram.

The following is the state-diagram for Approach 1 above.

Here is David's Loose's excellent solution. He followed Approach 3 described above.

Solution by David Loose:

1. (2 points) Briefly describe in words the behavior of your machine. State what symbols belong to Gamma (the tape alphabet).

The Turing machine will have 4 tapes: 1 for input and one each for a's, b's and c's.  Each of these will be able to stay place.  For every a read from input on x will be placed on the a tape.  b's and c's will be marked on their respective tapes with a x as well.  At the end the tapes will read left.  If a left end marker is found before the others are done, the TM will reject.  Otherwise, it accepts.

2. (8 points) Provide a state-diagram for your Turing machine. Remember to make all the transitions explicit in the diagram.

Here is the state diagram: