Construct a Turing-Machine to decide ww^Rw

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.

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)*.

As a hint, note that ww^Rw must have length 3n for some n (since each character appears exactly three times). You might therefore build a Turing machine that works by somehow counting the length of the string, using this to determine where the boundaries of the three strings are, and then checking that the three pieces all have the appropriate composition. If you can't count up a multiple of 3 characters, you could immediately reject.

Depending on what sort of TM is allowed, this might be easiest with a multitrack or multitape Turing machine so that you can mark up the letters with some extra information.

Hope this helps!

Here's how I did it with 2 tapes and O(n) complexity:

1. make sure the length divides by 3 by scanning tape 1 while moving right on tape 2 every 3 steps in tape 1
2. If you reached the end of tape 1 while the next step for tape 2 is to move right you the sufficient number of letters (divisible by 3)
3. Mark the letter you reached on tape 2 (this is the end of the first thirds)
4. Roll back to the beginning of both tapes
5. Get to the second third by going over tape 2 till the mark and back
6. confirm WWR: move both tapes till the end of tape 2 and then move tape 1 forward and tape 2 backwards. If they match you got WWR
7. Check W at the beginning and the end: simply continue the scan on tape 1 while comparing to tape 2 from its beginning