Construct a Turing-Machine to decide ww^Rw

Question

w^R is the reverse of w and w is {0, 1}* . So the TM needs to decide a word followed by the reverse of this word followed by the word. I don't want the answer, I just want a lead to start and to get on the right track.

Answer 1

Since some time has passed and the answer probably isn't needed anymore, I guess I'll propose a solution for the benefit of future students looking for an example of how one language can be recognized by a Turing machine.

Here's the idea. We'll take as the tape alphabet {0, 1, a, b, c, d} and make a single-tape singly-infinite tape Turing machine that recognizes w w^R w. The machine will work in five phases:

1. Replace 0s and 1s in the prefix w w^R with a's and b's.
2. See whether w w^R is a palindrome.
3. Restore the tape to its pristine state.
4. Replace 0s and 1s in the suffix w^R w with c's and d's.
5. See whether w^R is a palindrome.

Note that this is simply one easy (for me to understand, that is) way to show that there exists a Turing machine to recognize this language. Naturally, showing that there exists an algorithm to solve this in any Turing-equivalent system of computation is just as good (it proves there exists a TM)... still, this outlines the construction of one such TM. Also note that there may be a simpler, more efficient or more intuitive TM to solve this problem... again, this is only one approach.

Step 1 will work as follows:

• Precondition: The tape begins with a blank, contains any string in (0+1)*, and is followed by an infinite string of blank squares.

• Postcondition: Halts if tape is empty or if length is not a multiple of 3; else, the tape begins with a blank, is followed by (a+b)^2n (c+d)^n, followed by an infinite string of blanks.

  1. Move to the right.
  2. If empty, halt accept. Otherwise, Scan to the right until you find an empty tape square, then move left.
  3. Change the tape to c if 0 or d if 1.
  4. Scan left until you find an empty tape square. Move right.
  5. If the tape is 0 or 1, change to a or b then move right. If the tape is c or d, halt reject.
  6. If the tape is 0 or 1, change to a or b then move right. If the tape is c or d, halt reject.
  7. If tape is c or d, scan to the beginning of the tape and go to Step 2. Otherwise, scan right until c or d, then move left.
  8. Change the tape to c if 0 or d if 1.
  9. Scan left until you find either a or b. Move right.
  10. Repeat starting at 4.

Step 2 will work as follows:

• Precondition: The tape begins with a blank, is followed by (a+b)^2n (c+d)^n, followed by an infinite string of blanks.

• Postcondition: Halts if the prefix (a+b)^2n isn't a palindrome; otherwise, leaves the tape in a state like D (c+d)^3n D*

  1. Move right.
  2. If tape is a (or b), move right. If tape is c or d, go to the beginning of the tape, then go to Step 3.
  3. If the tape is c, d or blank, halt reject. Otherwise, scan right until you find a c, d or blank. Move left.
  4. If the tape is a b (or a), halt reject. Otherwise, change this to a c (or d) and scan back to the left until you see a blank, a c or a d. Move right. Change a (or b) to c (or d). Move right.
  5. Repeat starting at step 2.

Step 3 will work as follows

• Precondition: Tape is D (c+d)^3n D*

• Postcondition: Tape is D (0+1)^3n D*

  1. Move right.
  2. If tape is c, write 0 and move right. If tape is d, write 1 and move right. If tape is blank, move to first blank space at the end of tape and go to step 4.
  3. Repeat step 2.

Step 4 and 5 work just like steps 1 and 2, except you work backwards (the tape now looks like D (c+d)^n (a+b)^2n D*, and you must check to see whether the (a+b)^2n part is a palindrome.

Any string passing both these tests must be of the form w w^R w where w is in (0+1)*.