Trading States for Symbols with a Turing Machine

Question

Show that for each string $w ∈ \{0, 1\}^∗$ there exists a stay-put Turing machine

$$M_w = (Q, \{0, 1\}, \Gamma, \delta, s, q_{\mathit{accept}}, q_{\mathit{reject}})$$

with $|Q| ≤ 5$ states that starts on a blank tape in state $s$ and ends in state $q_{\mathit{accept}}$ with the tape content $w$ beginning in the first cell and the head under that cell.

That is, starting on a blank tape, the machine outputs $w$ and stops in $q_{\mathit{accept}}$.

I know that if there were infinite states then we could put each letter into its own state so that we could print the letter when needed, but I don't know how to reduce it to 5 states.

Answer 1

Here is one idea. Let $|w| = n$. We will have a tape symbol for each number in $\{0,1,\ldots,n\}$, which we will denote by $\langle i \rangle$. The machine starts by writing $\langle n \rangle$ on the tape. Then it repeatedly performs the following steps:

• Read $\langle i \rangle$.
• Depending on the value of $i$ and on $w$, switch to a write-0 or a write-1 state.
• In write-$b$ step, move right until reaching the first blank, write $b$, then move left until reaching a cell of the form $\langle j \rangle$.
• Replace $\langle j \rangle$ with $\langle j-1 \rangle$, or terminate if $j = 0$.

The exact implementation of this algorithm depends on your exact model. In your model, you might be able to do it using 5 states. But in any reasonable model, $O(1)$ states are needed, regardless of $w$.