I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of something not extremely complicated that goes over all combinations of the alphabet for a given word length, then type # onto the print tape and copies it back in reverse.

Is there something I'm missing here? Could there be a simpler algorithm here?

Thanks in advance.

  • $\begingroup$ This is not a research-level question, and hence off-topic here. It might be suitable for Computer Science. $\endgroup$ – Jan Johannsen Mar 10 '17 at 8:36
  • $\begingroup$ I agree -- and ironically enough, the points garnered from answering this question have granted me the privilege of voting to close. $\endgroup$ – Aryeh Mar 10 '17 at 8:44
  • 2
    $\begingroup$ My bad- sorry about that. Thanks for the help. $\endgroup$ – Bob V. Mar 10 '17 at 9:32

Here is a simple Turing machine segment that reads a binary word $w$ starting at a position immediately to the right of the delimeter symbol # and replaces it with $w$'s successor in the lexicographic ordering. Here, L,R,S indicate moving the read/write head Left, Right, or Stay. enter image description here

This simple and powerful (standard) trick avoids a brute-force enumeration by using the results of previous computations to produce future ones. If you're allowed multiple tapes, it's now quite easy to accomplish the task you defined. Otherwise, there are standard $k$-tape to $1$-tape conversions.

| cite | improve this answer | |
  • $\begingroup$ The $\not{b}$ character represents a blank tape symbol. $\endgroup$ – Aryeh Mar 10 '17 at 8:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.