Define Turing machine and its roles.

A Turing machine (TM) is a mathematical model of computation that has a finite control, an infinite tape divided into cells, and a read/write head that can move left or right. Formally it is a 7-tuple:

M = (Q, Σ, Γ, δ, q₀, B, F)

• Q: finite set of states
• Σ: input alphabet (not containing the blank)
• Γ: tape alphabet, with Σ ⊂ Γ
• δ: transition function, Q × Γ → Q × Γ × {L, R}
• q₀: start state
• B: blank symbol, B ∈ Γ
• F: set of final (accepting) states

In one move, the TM reads the symbol under the head, writes a symbol, moves the head one cell left or right, and changes state. It accepts if it enters a final state.

Roles of a Turing machine

• Language recogniser: it accepts the recursively enumerable languages, the largest class in the Chomsky hierarchy (type-0), which is more than finite automata or pushdown automata can recognise.
• Computing functions: it can compute any function that is computable by an algorithm, for example addition, multiplication and copying strings. By the Church–Turing thesis, anything a real computer can compute, a TM can compute.
• Language generator / enumerator: a TM can list all strings of a language.
• Model of a general-purpose computer: a universal Turing machine takes another TM's description and input and simulates it, like a stored-program computer.
• Studying the limits of computation: TMs are used to prove that some problems are undecidable, such as the halting problem, and to define complexity classes such as P and NP.