A read-only Turing machine or two-way deterministic finite-state automaton (2DFA) is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape.
The machine in its bare form is equivalent to a deterministic finite automaton in computational power, and therefore can only parse a regular language.
We define a standard Turing machine by the 9-tuple
, and moves the "read head" in direction
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.
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.
Other variants of this model allow more computational complexity.
With a single infinite stack the model can parse (at least) any language that is computable by a Turing machine in linear time.
With the further aid of nondeterminism the machine can parse any context-free language.
With two infinite stacks the machine is Turing equivalent and can parse any recursive formal language.
If the machine is allowed to have multiple tape heads, it can parse any language in L or NL, according to whether nondeterminism is allowed.
In modern research, the model has become important in describing a new complexity class of Quantum finite automata or deterministic probabilistic automata.