Turing Machines: Definition
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
Mathematical note:
3/45