# Trading States for Symbols with a Turing Machine

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.

• Please edit your question to include a self-contained definition of a "stay-put Turing machine". Please credit the original source where you encountered this exercise.
– D.W.
Apr 5, 2020 at 23:12

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$$.