How could I design a turing machine that prints all natural numbers on its tape in order?

1k Views Asked by At

How one could implement a turing machine that prints all natural numbers of its tape in order. Two consecutive numbers are separated on the tape with the symbol #. The tape should look like this:

#0#00#000#0000#00000#...

the number of 0s is the natural number.

1

There are 1 best solutions below

3
On

I would design it out of two components:

The first component copies the "previous" string, i.e. the string between the second and first appearance of # to the left of the string. You can do this by moving left until you reach the first #, then left until you meet the first non-zero, then move one right, replace the $0$ with $1$, and move right to write $0$. When this is all done, replace all the ones with zeroes.

This should produce something like this:

#0#00#000#  ---> #0#00#100#0 ---> #0#00#110#00  --> #0#00#111#000 --> #0#00#000#000

The second component writes a 0# at the end of the string.