Read-only Turing machine

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

We define a standard Turing machine by the 9-tuple

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

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

So given initial state q reading symbol a, we have a transition defined by \delta(q,a)=(q_2,a_2,d) which replaces a with a_2, transitions to state q_2, and moves the "read head" in direction d (left or right) to read the next input.[1] In our 2DFA read-only machine, however, 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[edit]

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.[2] In particular, the language {anbncn} 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.[3]

Applications[edit]

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]

See also[edit]

References[edit]

  1. ^ Kozen, Dexter C. (1997) [1951]. 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 0-387-94907-0. 
  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" (– Scholar search). 38th Annual Symposium on Foundations of Computer Science (FOCS '97): 66–75. doi:10.1109/SFCS.1997.646094. Archived from the original on 2007-08-23. Retrieved 2007-11-07.  [dead link]
  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-26. Retrieved 2007-11-07. 

External links[edit]