Misplaced Pages

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.

Theory

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

Variants

Several variants of this model are also equivalent to DFAs. In particular, the nondeterministic case (in which the transition from one state can be to multiple states given the same input) is reducible to a DFA.

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. In particular, the language {abc} can be parsed by an algorithm which verifies first that there are the same number of a's and b's, then rewinds and verifies that there are the same number of b's and c's. 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.

Applications

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.

See also

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

References

1. Kozen, Dexter C. (1997) . David Gries, Fred B. Schneider (ed.). Automata and Computability (hardcover). Undergraduate Texts in Computer Science (1 ed.). New York: Springer-Verlag. pp. 158, 210, 224. ISBN 978-0-387-94907-9.
2. Computational Complexity by Wagner and Wechsung, section 13.3 (1986, ISBN 90-277-2146-7)
3. Computational Complexity by Wagner and Wechsung, section 13.1 (1986, ISBN 90-277-2146-7)
4. Kondacs, A.; J. Watrous (1997). "On the power of quantum finite state automata". Proceedings 38th Annual Symposium on Foundations of Computer Science. pp. 66–75. CiteSeerX 10.1.1.49.6392. doi:10.1109/SFCS.1997.646094. ISBN 978-0-8186-8197-4. S2CID 14025116. Archived from the original on 2007-08-23. Retrieved 2007-11-07.
5. Dwork, Cynthia; Stockmeyer, Larry (1990). "A Time Complexity Gap For 2-Way Probabilistic Finite State Automata". SIAM Journal on Computing. 19 (6): 1011–1023. doi:10.1137/0219069. Archived from the original on 2009-10-28. Retrieved 2007-11-07.

External links

• Lecture on finite-state automata by Adam Webber

• Turing machine