Read-only Turing machines

The goal of this article is to show that read-only Turing machines can only accept regular languages. The idea is to develop a "DP algorithm" to decide whether the Turing machine will accept that proceeds linearly from left to right and only remembers a finite amount of information.

Let:

• $\Sigma$ be an alphabet,
• $S$ a finite set of *states*,
• $T \subseteq S$ the set of accepted states and $s_0\in S$ be the initial state,
• $D \coloneqq \{ L, N, R \}$ the set of possible movements of a Turing machine, namely left, nothing and right, and
• $\delta\colon S \times (\Sigma\cup\{\bot\}) \to S \times D$ the transition function of a *read-only* Turing machine. (We assume for simplicity that the Turing machine starts on the first character of the word and that it never moves more that one $\bot$ away from the word.)

Then this Turing machine recognizes some language $L \subseteq \Sigma_*$, the set of all words for which the Turing machine reaches some accepted state. In order to prove that $L$ is regular, it suffices to construct another Turing machine that moves right in every step and also accepts $L$.

Fast-forwarding procedure

Note that the configuration of the Turing machine at a given point in time can be encoded as a tuple $(w, i, s) \in C \coloneqq \Sigma_* \times \mathbb{N}_0 \times S$, where $i$ is the word on the band beginning at position $1$, $i$ is the position of the head and $s$ is the current state.

Let $c = (w, i, s) \in C$ be a Turing machine configuration. If we try to simulate the Turing machine until we reach an accepted state or the head moves to $i + 1$, we can encounter one of the following three situations:

• The simulation never ands because it never fulfils these termination conditions. (non-halting case, represeted by $\bot$).
• The simulation ends on an accepted state at a head position $\le i$ (accepting case, represented by $\top$).
• The simulation ends with head at $i + 1$ in some state $s'\in S$. (progress case, represented by $s'$).

An important note: To determine whether $w\in L$, we can apply the following algorithm, provided we can compute the outcome of any fast-forward operation.

• Put the Turing machine into the initial configuration for word $w$ (i.e. put the head on position $1$ and enter the start state).
• Repeat forever:
  • Fast-forward.
  • If the result is either $\bot$ or $\top$, reject or accept, and terminate.
  • Otherwise, the result is some $s\in S$. Move the head to the right and enter state $s\in S$.

This algorithm terminates because the head was assumed to stay at most one $\bot$ symbol away from the word.

Defining a new state space

Let $c = (w, i, s) \in C$ be a configuration. For each $s'\in S$, let $f(s')$ be the outcome of forwarding beginning in $(w, i - 1, s')$. This defines the data for a tuple $(s, f) \in Z \coloneqq S \times (S \cup \{\bot, \top\})^S$. We will later consider $Z$ as the state space of the linear Turing machine we construct. Remember that $s$ is the state of the configuration $c$, while $f$ describes the fast-forward behavior at position $i-1$, where $i$ is the head position of $c$. Writing $\sigma(c) \coloneqq (s, f)$, we have defined a map $\sigma\colon C \to Z$.

Again, let $c = (w, i, s) \in C$ be a configuration. The following algorithm determines the result of fast-forwarding $(w, i, \tilde s)$ for any $\tilde s\in S$ (non-termination corresponds to the $\bot$ outcome), solely using $\sigma(c) = (s, f)$ and the symbol under the head, namely $w_i$:

• If $s$ is accepted, accept ($\top$) and terminate.
• If $\delta(s, w_i) = (s', R)$, return $s'$.
• If $\delta(s, w_i) = (s', N)$, return the result of this algorithm when $s$ is replaced by $s'$.
• If $\delta(s, w_i) = (s', L)$, and determine $f(s')$. If it is $\top$ or $\bot$, return its result; otherwise, its result is some $s''\in S$. Then return the result of this algorithm when $s$ is replaced by $s''$.

We collect the fast-forwardings in the map $\tilde f\colon S \to S \cup \{\bot, \top\}$. If the result of fast-forwarding is not $\bot$ or $\top$, then $c$ has moved to another configuration $\tilde c = (w, i + 1, \tilde f(s))$, and $\sigma(\tilde c) = (\tilde f(s), \tilde f)$.

Hence, if we know $\sigma(c)$ and the symbol under the head, we can determine $\sigma(\tilde c)$, where $\tilde c$ is the fast-forwarded configuration.

A right-linear Turing machine that accepts L

To prove that $L$ is regular, we now construct a right-linear Turing machine that accepts $L$. Its state space is $Z$, and its alphabet is $\Sigma$. In every step, if the Turing machine is not in an accepted state, it moves the head to the right. If the head is on the $\bot$ after the word and the Turing machine does not accept in the next step, it rejects.

The initial state is $(s_0, f_0)$, where $s_0$ was the initial state of the original Turing machine and $f_0(s)$ is the result of fast-forwarding the configuration $(w, 0, s)$. Importantly, $f_0$ is independent of the word $w$, because during the fast-forwarding, the Turing machine does not get to see the band to the right of position $0$ (where the symbol is $\bot$).

If the current state is $(s, f) \in Z$ and the head is on symbol $x \in \Sigma \cup \{\bot\}$, we use the algorithm from the last section to uniquely determine the successor state $(\tilde f(s), \tilde f)$.

If we ignore the second component of $(s, f) \in Z$, then every configuration of this linear Turing machine corresponds to a configuration $c$ of our original read-only Turing machine, and we can reconstruct $(s, f)$ as $\sigma(c) = (s, f)$. Making a step with the linear Turing machine corresponds to fast-forwarding the read-only Turing machine. Hence both Turing machines accept the same language $L$.