<p>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. <a href="https://i.sstatic.net/bJ6pi.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bJ6pi.jpg" alt="enter image description here"></a></p>

<p>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.</p>

CC BY-SA 3.0
2017-03-10T08:24:44.790Z
The $\not{b}$ character represents a blank tape symbol.
Aryeh
CC BY-SA 3.0
2017-03-10T05:27:15.230Z
2017-03-10T05:27:15.230Z
Aryeh
<p>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. </p>

<p>Is there something I'm missing here? Could there be a simpler algorithm here?</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2017-03-10T08:36:28.527Z
This is not a research-level question, and hence off-topic here. It might be suitable for [Computer Science](http://cs.stackexchange.com/).
Jan Johannsen
CC BY-SA 3.0
2017-03-10T08:44:24.547Z
I agree -- and ironically enough, the points garnered from answering this question have granted me the privilege of voting to close.
Aryeh
CC BY-SA 3.0
2017-03-10T09:32:44.413Z
My bad- sorry about that. Thanks for the help.
Bob V.
<computability><turing-machines>
Enumerator for the language w#w^R?
Bob V.
# Enumerator for the language w#w^R?

(Asked by: username_0 on 2017-03-09)

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.

**Tags:** computability, turing-machines

> **Comments:**
> **username_1**: This is not a research-level question, and hence off-topic here. It might be suitable for [Computer Science](http://cs.stackexchange.com/).  
> **username_2**: I agree -- and ironically enough, the points garnered from answering this question have granted me the privilege of voting to close.  
> **username_0**: My bad- sorry about that. Thanks for the help.  

---

## 1 answers

### Answer by username_2 on 2017-03-10. Score: 2 | Accepted answer

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](https://i.sstatic.net/bJ6pi.jpg)](https://i.sstatic.net/bJ6pi.jpg)

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.

> **Comments:**
> **username_2**: The $\not{b}$ character represents a blank tape symbol.  

---

