Turing machines

For applications of Turing machines, see the section on

enumerating a language

computing a function

To insert a sample Turing machine into your document, select from the editor

Insert⟶ Structure⟶Turing machine.

A Turing machine is a state machine consisting of 5 components∶

Description

Math notation

Grafstate code

Set of states Q

Q={s,a,q1,q2}.

Q={s,a,q1,q2}

Input alphabet Σ

Σ={a,b}.

S={a,b}

Tape alphabet Τ

Τ={a,b,␣}

T={a,b,\_}

Transition

q1⟶q2∶b⟶␣,R

q1->q2:b->\_,R

Starting state (q₀)

q₀=q_s.

q0=qs

Syntax constraints for a Turing machine

Each line of a Turing machine is checked against the following constraints. If a line violates a constraint, then you will receive an error message.

Q , S , and T must be nonempty sets.

q0 must be defined as a state in Q .

The current state and destination state for each transition must be defined in Q .

The instruction part of each transition must have the form r⟶w,m, where r and w are defined in T and m is either L, R, or S.

The optional states qa and qr must be defined in Q , if used.

qa and qr cannot have outgoing transitions.

Q , S , T , and q0 must be defined exactly once.

You may give a Turing machine an optional title to be displayed on the state diagram using the title instruction. title place a title here .

You can add a comment to any line of the Turing machine code by typing /* followed by the comment.

Abbreviated syntax

Consider the following transition∶

Code
`q1-q2: a->a, R`

The transition above can be define using the following line∶

Code
`q1->q2: a, R`

Consider the following transitions∶

Code
`q1-q2: a->\_, R` `q1->q2: b->\_, R`

The transitions above can be define using the following line∶

Code
`q1->q2: {a,b}->\_, R`

Consider the following transitions∶

Code
`q1-q2: a->a, R` `q1->q2: b->b, R`

The transitions above can be define using the following line∶

Code
`q1->q2: {a,b}, R`

The line above will generate a state diagram with a transition labelled

{a,b}⟶σ,R.

The σ indicated that the tape head slips over the symbols being read without changing them.

Example

Below is the state diagram for a Turing machine that recognizes the language {aⁿbⁿ∣n ≥ 0}∶

Turing machine

Mab

Below is the Grafstate code for M_ab∶

Code
`:+ tm Mab` `Q={q0,q1,q2,qa,qr,q3}` `S={a,b}` `T={X,\_,a,b}` `q0=q0` `q0->q1:a->\_,R /* mark the beginning of the "data"` `q0->qr:b->b,S /* starts with b or more b's than a's` `q0:X->X,R /* skip the marked symbols` `q0->qa:\_->\_,S /* accept` `q1:a->a,R /* looking for b's so do not change a's` `q1:X->X,R /* skip the marked b's` `q1->qr:\_->\_,S /* more a's than b's` `q1->q2:b->X,R /* mark this b to match the a` `q2:b->b,R /* prepare to repeat` `q2->qr:a->\_,S /* a comes after b` `q2->q3:\_->\_,L /* prepare to rewind` `q3:b->b,L /* rewind past b's` `q3:X->X,L /* rewind past marks` `q3:a->a,L /* rewind past a's` `q3->q0:\_->\_,R /* found beginning of "data"` `done.`

Code

:+ tm Mab
Q={q0,q1,q2,qa,qr,q3}
S={a,b}
T={X,\_,a,b}
q0=q0
q0->q1:a->\_,R /* mark the beginning of the "data"
q0->qr:b->b,S /* starts with b or more b's than a's
q0:X->X,R /* skip the marked symbols
q0->qa:\_->\_,S /* accept
q1:a->a,R /* looking for b's so do not change a's
q1:X->X,R /* skip the marked b's
q1->qr:\_->\_,S /* more a's than b's
q1->q2:b->X,R /* mark this b to match the a
q2:b->b,R /* prepare to repeat
q2->qr:a->\_,S /* a comes after b
q2->q3:\_->\_,L /* prepare to rewind
q3:b->b,L /* rewind past b's
q3:X->X,L /* rewind past marks
q3:a->a,L /* rewind past a's
q3->q0:\_->\_,R /* found beginning of "data"
done.