turing.md

Turing Machine

Definition

Formal

• 5 tuple (Q, Σ, Γ, q0, δ)
  • Q is finite state of inputs
  • Σ is alphabet
  • Γ is tape input
  • (δ: Q x (Γ ∪ {[,]}) -> (Q {ha,hr}) x (Γ ∪ {[,]} x {R,L,S})) is the transition function

Informal

• Turing machine is very similar to linear bounded automata except that the tape in a turing machine is semi infinite.
• At each step the turing machine can perform an action where action = {L, R, S}
  • L = Left
  • R = Right
  • S = Stationary
• Can halt in two states accept state (ha) / reject state (hr)

Transitions

Transition function looks like:

(q,a), (p,b,A) where:

• q = original state
• a = item at read write position
• p = new state
• b = new item at read write position
• A = action to be performed where a ∈ {L,R,S}

A transition can be shown as:

xQy -> zPw where:

• x = symbols to left of read write head
• Y = symbols to right of read write head
• Q = current state
• z = new symbols to left of read write head
• w = new symbols to right of read write head
• P = new state