Read-only Turing machine

We define a standard Turing machine by the 9-tuple

${\displaystyle M=(Q,\Sigma ,\Gamma ,\vdash ,\_,\delta ,s,t,r)}$ where

• ${\displaystyle Q}$ is a finite set of states;
• ${\displaystyle \Sigma }$ is the finite set of the input alphabet;
• ${\displaystyle \Gamma }$ is the finite tape alphabet;
• ${\displaystyle \vdash \in \Gamma -\Sigma }$ is the left endmarker;
• ${\displaystyle \_\in \Gamma -\Sigma }$ is the blank symbol;
• ${\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}}$ is the transition function;
• ${\displaystyle s\in Q}$ is the start state;
• ${\displaystyle t\in Q}$ is the accept state;
• ${\displaystyle r\in Q,~r\neq t}$ is the reject state.

So given initial state ${\displaystyle q}$ reading symbol ${\displaystyle a}$, we have a transition defined by ${\displaystyle \delta (q,a)=(q_{2},a_{2},d)}$ which replaces ${\displaystyle a}$ with ${\displaystyle a_{2}}$, transitions to state ${\displaystyle q_{2}}$, and moves the "read head" in direction ${\displaystyle d}$ (left or right) to read the next input.[1] In our 2DFA read-only machine, however, ${\displaystyle a=a_{2}}$ always.

This model is now equivalent to a DFA. The proof involves building a table which lists the result of backtracking with the control in any given state; at the start of the computation, this is simply the result of trying to move past the left endmarker in that state. On each rightward move, the table can be updated using the old table values and the character that was in the previous cell. Since the original head-control had some fixed number of states, and there is a fixed number of states in the tape alphabet, the table has fixed size, and can therefore be computed by another finite state machine. This machine, however, will never need to backtrack, and hence is a DFA.

A read-only Turing machine is used in the definition of a Universal Turing machine to accept the definition of the Turing machine that is to be modelled, after which computation continues with a standard Turing machine.

In modern research, the model has become important in describing a new complexity class of Quantum finite automata or deterministic probabilistic automata.[4][5]

• Computability
• Turing machine equivalents
• Stack machine
• Queue automaton
• Quantum computer

• Lecture on finite-state automata by Adam Webber