# Turing Machines

A turing machine is a 7-tuple (Q, Î£, Î“, Î´, q_{0}, q_{accept}, q_{reject}), where

- Q is the set of states.
- Î£ is the input alphabet not containing the blank symbol,
- Î“ is the tape alphabet, where âˆˆ Î“ and Î£ âŠ† Î“.
- Î´ : Q Ã— Î“ â†’ Q Ã— Î“ Ã— {L, R} is the transition function.
- q
_{0}âˆˆ Q is the start state. - q
_{accept}âˆˆ Q is the accept state. - q
_{reject}âˆˆ Q is the reject state, where q_{reject}â‰ q_{accept}.

Initially M (turing machine) receives its input w âˆˆ Î£* on the leftmost n squares of the tape and rest of the tape is blank, i.e. filled with blank symbol. The head starts from the leftmost square of the tape. Once M has started, 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 transition continues until it enters either the accept or reject states at which point it halts. If neither occurs, M goes on forever. As a TM computes, changes occur in the current state, current tape content and current head location. A setting of these three items is called a CONFIGURATION.

- The above diagram shows a TM with configuration 10101q
_{7}110.Let C_{1}and C_{2}be configuration of M. C_{1}yields C_{2}if M is in configuration C_{2}after running M in configuration C_{1}for one step. Suppose Î´(q_{1}, b) = (q_{2}, C, L), then aaq_{1}bb yields aq_{2}acb. Let w âˆˆ Î£* and M be a turing machine. M accepts w if there are configs C_{o}, C_{i}, ..........., C_{k}, s.t.

â€” C_{o}= q_{0}w

â€” C_{i}yields C_{i + 1}for i = 0, ........., k-1, and

â€” C_{k}contains the accept state q_{accept}. - A Turing Machine M recognizes a language L if M accepts exactly those strings in L.
- A language L is called recognizable or recursively enumerable if some TM recognizes L.
- A TM decides a language L if M accepts all strings in L and rejects all strings not in L.
- A language is called decidable or recursive if some TM decides L.
- L is decidable if and only if both L and Â¬ L are recognizable.