Definition: A Turing
machine (TM) is a 6-tuple M = (Q, S, G, R, s, F), where
• Q is a finite set of states
• S is an input
alphabet
• G is a tape
alphabet; D
Î
G; S Í G
• R is a finite set of rules of the form:
pa
® qbt,
where p, q Î Q, a, b Î G, t Î {S, R, L}
• s Î Q is the start state
• F Í Q is a set of final
states
• Mathematically, R is a relation from Q
´ G to Q ´ G´ {S, R, L}
• Instead of (pa, qbt),
we write pa
® qbt