org.metasyntactic.math.automata
Class TuringMachine

java.lang.Object
  |
  +--org.metasyntactic.math.automata.TuringMachine

All Implemented Interfaces:

FiniteAutomata, java.io.Serializable

public class TuringMachine

extends java.lang.Object

implements FiniteAutomata

FORMAL DEFINITION OF A TURING MACHINE

The heart of the definition of a Turing machine is the tansition function δ because it tells us how the machine gets from one step to the next. For a Turing machine, δ takes the form Q x Γ → Q x Γ x {L, R}. That is, when the machine is in a certain state q and the head is over a tape square containing a symbol a, and if δ(q, a) = (r, b, L), the machine writes the symbol b replacing the a, and goes to state r. The third component is either L or R and indicates whether the head moves to the left or right after writing. In this case the L indicates a move to the left.

A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q₀, q_accept, q_reject), where Q, Σ, Γ, are all finite sets and

1. Q is the set of states,
2. Σ is the input alphabet not containing the special blank symbol " ",
3. Γ is the tape alphabet, where " " ∈ Γ and Σ ⊆ Γ,
4. δ: Q x Γ → Q x Γ x {L, R} is the transition function
5. q₀ ∈ Q is the start state,
6. q_accept ∈ Q is the accept state,
7. q_reject ∈ Q is the reject state, where q_reject ≠ q_accept.

See Also:

Serialized Form

Constructor Summary

TuringMachine(java.util.Set states, java.util.Set inputAlphabet, java.util.Set tapeAlphabet, TransitionFunction transitionFunction, java.lang.Object startState, java.lang.Object acceptState, java.lang.Object rejectState)

Method Summary

boolean

accept(java.util.Iterator w) A Turing machine M = (Q, Σ, Γ, δ, q0, qaccept, qreject) computes as follows.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TuringMachine

public TuringMachine(java.util.Set states,
                     java.util.Set inputAlphabet,
                     java.util.Set tapeAlphabet,
                     TransitionFunction transitionFunction,
                     java.lang.Object startState,
                     java.lang.Object acceptState,
                     java.lang.Object rejectState)

Method Detail

accept

public boolean accept(java.util.Iterator w)
               throws ParseException

A Turing machine M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) computes as follows. Initially M receives its input w = w₁w₂…w_n ∈ Σ^* on the leftmost n squares of the tape, and the rest of the tape is blank (i.e., filled with blank symbols). The head starts on the leftmost square of the tape. Not that Σ does not contain the blank symbol, so the first blank appearing on the tape marks the end of the input. Once M starts, the computation proceeds according to the rules described by the transition function. If M ever tries to move its head to the left off the left-hand end of the tape, the head stays in the same place for that move, even though the transition function indicates L. The computation continues until it enters either the accept or reject state at which point it halts. If neither occurs, M goes on forever.

Specified by:

accept in interface FiniteAutomata

Parameters:

w - A string over some alphabet Σ

Returns:

true if this machine accepts w

Throws:

ParseException - if along the way of testing for acceptance, an exception occurred over the format of w