Read-only right moving Turing machines

Read-only right moving Turing machines are a particular type of Turing machine.

Definition

The definition based on a single infinite tape defined to be a 7-tuple

[math]\displaystyle{ M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle }[/math] where

• [math]\displaystyle{ Q }[/math] is a finite set of states
• [math]\displaystyle{ \Gamma }[/math] is a finite set of the tape alphabet/symbols
• [math]\displaystyle{ b \in \Gamma }[/math] is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
• [math]\displaystyle{ \Sigma }[/math], a subset of [math]\displaystyle{ \Gamma }[/math] not including b is the set of input symbols
• [math]\displaystyle{ \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{R\} }[/math] is a function called the transition function, R is a right movement (a right shift).
• [math]\displaystyle{ q_0 \in Q }[/math] is the initial state
• [math]\displaystyle{ F \subseteq Q }[/math] is the set of final or accepting states

In the case of these types of Turing Machines, the only movement is to the right. There must exist at least one element of the set F (a HALT state) for the machine to accept a regular language (Not including the empty language).

An example Read Only right moving Turing machine

[math]\displaystyle{ Q = \{ A, B, C, \text{HALT} \} }[/math]

[math]\displaystyle{ \Gamma = \{ 0, 1 \} }[/math]

[math]\displaystyle{ b = 0 }[/math], "blank"

[math]\displaystyle{ \Sigma = \varnothing }[/math], empty set

[math]\displaystyle{ \delta = }[/math] see state-table below

[math]\displaystyle{ q_0 = A }[/math], initial state

[math]\displaystyle{ F = }[/math] the one element set of final states :[math]\displaystyle{ \{\text{HALT}\} }[/math]

State table for 3 state, 2 symbol read only machine

	Current state A			Current state B			Current state C
tape symbol	Write symbol	Move tape	Next state	Write symbol	Move tape	Next state	Write symbol	Move tape	Next state
0	1	R	B	1	R	A	1	R	B
1	1	R	C	1	R	B	1	N	HALT

See also

• DFA
• NFA
• Finite-state machine
• Read-only Turing machine
• Turing machine
• Turing machine examples

References

• Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.