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.
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:
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.)
- (qi,a) -> (qij,b,R), and
- (qij,x) -> (qj,x,L), for each character x in GammaT
by implementing a Turing machine that decides this language. Note that "bbacbcaac" and "" (the empty word) belong to L, but "babca" doesn't.
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.
The following is the state-diagram for Approach 1 above.
Solution by David Loose:
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.
Here is the state diagram: