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.

  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Apr 5 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.