Can a halting turing machine write any combination on a tape before halting?

204 Views Asked by At

Assume, a halting turing machine uses $n$ items of the tape. Can it write every possible combination on this $n$ items before halting ?

We start with a blank tape.

Example $n=2$ , alphabet $0,1$

The machine could make the task as follows : It prints a $1$ (combination $10$) goes to the right, prints a $1$ again (combination $11$) , goes to the left, prints a $0$ (combination $01$) and halts. So, it used only $2$ items and all possible combinations occured ($00$ occured at the start)

1

There are 1 best solutions below

2
On

Yes. A Turing Machine can carry out any finite set of instructions, and what you desire is certainly finite. You just have it start in state $1$, do whatever you want, then go to state $2$, do something, go to state $3$, etc.. You'll have a lot of states in your machine, but it's still a Turing machine. You could be a bit more sophisticated and implement a Turing machine specified as follows. It starts in state $0$ and proceeds as:

  • State 0: If you read a $0$, write a $1$ and don't move the head. Stay in state $0$. Otherwise, transition to state $+1$ and move the head right.

  • State +1: If you read a $0$, write a $1$ and move the head left. Transition to state $-1$. Otherwise, transition to state $+2$ and move the head right.

  • State $+i$: If you read a $0$, write a $1$ and move the head left. Transition to state $-i$. Otherwise, transition to state $n+1$ and move the head right.

...

  • State $+n-1$: If you read a $0$, write a $1$ and move the head left. Transition to state $-(n-1)$. Halt otherwise.

...

  • State $-1$: Write a $0$ and transition to state $0$.

  • State $-i$: Write a $0$, move the head left, and transition to state $-(i-1)$.

This is probably the simplest machine that can count in binary without using additional positions on the tape (e.g. if we mark where the start and end of the string is with a different character, then it only takes two states, excluding the halting state). It basically counts how many $1$s it has seen when it is incrementing, finds the first $0$, changes it to a $1$, then backtracks, zeroing the previous digits.