Read-only Turing machine

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-state machine or DFA in computational power, and therefore can only parse a regular language.

Theory

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\; imes\; Gamma\; ightarrow\; Q\; imes\; Gamma\; imes\; \{L,R\}$ is the "transition function";
* $s\; in\; Q$ is the "start state";
* $t\; in\; Q$ is the "accept state";
* $r\; in\; Q,\; ~\; r\; e\; 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 [cite book |last=Kozen |first=Dexter C. |editor=David Gries, Fred B. Schneider |title=Automata and Computability |origyear=1951 |format=hardcover |edition=1 |series=Undergraduate Texts in Computer Science |year=1997 |publisher=Springer-Verlag |location=New York |language=English |isbn=0-387-94907-0 |pages=158,210,224] . In our 2DFA read-only machine, however, $a=a\_2$ always.

This model is now equivalent to a DFA. The proof is outlined by noting that a Nondeterministic finite state machine (NFA) can model a 2DFA by offering both leftward and rightward movement of the read head as possible transitions. The NFA is then reducible to a DFA by a well-established proof (see article for details). The 2DFA can model a standard DFA quite easily by simply having all transitions move the head in one direction.

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. [ "Computational Complexity" by Wagner and Wechsung, section 13.3 (1986, isbn 9027721467)] In particular, the language {aⁿbⁿcⁿ} 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. [ "Computational Complexity" by Wagner and Wechsung, section 13.1 (1986, isbn 9027721467)]

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 [cite journal |last=Kondacs |first=A. |authorlink= |coauthors=J. Watrous |year=1997 |month= |title=On the power of quantum finite state automata |journal=38th Annual Symposium on Foundations of Computer Science (FOCS '97) |volume= |issue= |pages=66–75 |id= |url=http://www.cs.uwaterloo.ca/~watrous/papers/qfa.ps |accessdate= 2007-11-07 |quote=|doi=10.1109/SFCS.1997.646094|format=dead link|date=June 2008 – ^{[http://scholar.google.co.uk/scholar?hl=en&lr=&q=author%3A+intitle%3AOn+the+power+of+quantum+finite+state+automata&as_publication=38th+Annual+Symposium+on+Foundations+of+Computer+Science+%28FOCS+%2797%29&as_ylo=1997&as_yhi=1997&btnG=Search Scholar search]} ] [cite journal |last=Dwork |first=Cynthia |authorlink= |coauthors=Larry Stockmeyer |year=1990 |month= |title=A Time Complexity Gap For 2-Way Probabilistic Finite State Automata |journal=SIAM Journal on Computing |volume=19 |issue=6 |pages=1011–1023 |id= |url=http://www.geocities.com/[e-mail]/pfa_gap.ps |accessdate= 2007-11-07 |quote=|doi=10.1137/0219069 ] .

References

See also

* Computability
* Turing machine equivalents
* Stack machine
* Queue machine
* Quantum computer

External links

[http://www.webber-labs.com/fl/lectures/ppt-slides/09.ppt Lecture on finite-state automata by Adam Webber]