Some problems cannot be solved by any program, no matter how much time or memory you allow. That is not an engineering limit but a mathematical one, and the Turing machine is the model that lets us prove it. This is the capstone of Theory of Computation and a reliable source of exam questions. The machine itself is austere, a finite control and one unbounded tape, and the argument that defeats it turns on a single move: handing a machine its own description and asking it about itself.
The Turing machine: definition and configurations
A Turing machine has a finite control and an infinite tape divided into cells, with a head that reads and writes one cell at a time and moves left or right. Formally it is a seven-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject), where Q is states, Σ the input alphabet, Γ the tape alphabet (including a blank), δ the transition function, and the last three are the start, accept, and reject states.
A configuration (or instantaneous description) captures the machine's full state at one instant: the current control state, the tape contents, and the head position. A computation is a sequence of configurations, each following from the previous by one application of δ. The machine halts when it enters qaccept or qreject; it may also run forever.
To see it work, take a TM that recognises {aⁿbⁿ} by crossing off pairs. On input aabb it replaces the leftmost a with X, scans right to the leftmost b and replaces it with Y, returns to the left end, and repeats. Step by step the tape reads a a b b, then X a Y b, then X X Y Y, at which point no unmarked a or b remains and the machine accepts. If any a or b were left over, it would reject. On this one language the tape is only doing the counting a stack already does in Context-Free Grammars and Pushdown Automata. The TM pulls ahead on {aⁿbⁿcⁿ}, which no PDA accepts: matching the a's against the b's empties a stack, leaving nothing to count the c's with, while the tape's head can simply return to the cells it marked earlier and run a second crossing-off pass.
Variants that add no power
Several natural extensions recognise exactly the same languages as the basic model: a multi-tape TM, a TM with a two-way infinite tape, and a non-deterministic TM (an NDTM) all have the same language-recognising power as a single-tape deterministic TM. They may be faster or easier to program, but they compute the same class. This robustness is the evidence behind the Church-Turing thesis: anything effectively computable is computable by a Turing machine. The cost of that equivalence is time, not power: a k-tape machine that runs for t steps is simulated by a single-tape machine in O(t²) steps.
Recursive versus recursively enumerable
Two language classes sit at the top of the hierarchy, and telling them apart is heavily tested.
A language is recursively enumerable (RE), also called Turing-recognisable, if some TM accepts every string in the language and, on strings not in it, either rejects or loops forever.
A language is recursive, also called decidable, if some TM accepts every string in the language and rejects every string not in it, always halting.
Every recursive language is RE, but not conversely. A key theorem: a language is recursive if and only if both it and its complement are RE. So the recursive languages are closed under complement, while the RE languages are not.
The halting problem
The halting problem asks: given a description of a Turing machine M and an input w, does M halt on w? This language is RE but not recursive, meaning it is undecidable: no algorithm decides it for all inputs. Its complement, the set of pairs on which M runs forever, is not even RE. If it were, halting and its complement would both be RE, and the theorem above would make halting recursive, which it is not. That complement is the region outside every oval in the diagram above, beyond the reach of any machine at all.
The proof is a diagonalisation: assume the decider exists, then use it to build one machine whose behaviour on its own description must be the opposite of whatever the decider predicts.
Assume, for contradiction, a TM H exists that decides halting. On input (M, w), H halts and says "yes" if M halts on w, and "no" if M loops on w.
Build a new machine D that takes a machine description M as input, runs H on (M, M), and then does the opposite of what H reports: if H says M halts on M, then D loops forever; if H says M loops on M, then D halts.
Now run D on its own description, D. By D's construction, D halts on D exactly when H says D does not halt on D, and D loops on D exactly when H says D does halt.
H was assumed correct, so H says D halts on D exactly when D really does halt on D. Put that together with step 3 and you get: D halts on D if and only if D does not halt on D. No machine can satisfy that, so H never existed, and the halting problem is undecidable.
That self-reference, feeding a machine its own description, is the whole engine of the argument, and the exact reasoning exams ask you to reproduce.
Decidability versus undecidability, and reductions
A problem is decidable if its language is recursive, and undecidable otherwise. To prove a new problem P undecidable, we use a reduction: show that a known undecidable problem (usually the halting problem) reduces to P. If P were decidable, we could compose the reduction with P's decider to decide the halting problem, which is impossible. So P must be undecidable.
By this technique, many problems fall: whether a TM accepts the empty language, whether two TMs accept the same language, and whether a TM accepts any string at all are all undecidable. Rice's theorem generalises this: every non-trivial property of the language recognised by a TM is undecidable.
Placement in the Chomsky hierarchy
The Turing machine sits at the top of the Chomsky hierarchy. Type-3 (regular) languages are recognised by finite automata and described by regular expressions, with the pumping lemma marking their limit. Type-2 (context-free) languages are recognised by pushdown automata, type-1 (context-sensitive) by linear-bounded automata, and type-0 (recursively enumerable) by Turing machines. The recursive languages fall strictly between type-1 and type-0: every context-sensitive language is recursive, and every recursive language is RE, but neither inclusion reverses.
How Turing machines and decidability are tested in GATE, NET, and placements
GATE CS asks you to classify a given language as recursive, RE-but-not-recursive, or not RE, to identify which problems are decidable, and to apply closure results (recursive under complement, RE not under complement). Rice's theorem and reduction-based undecidability appear regularly, alongside Chomsky-hierarchy matching.
UGC NET Computer Science favours recall: the definition of decidable versus undecidable, the halting problem's status, and the machine-to-language-class mapping across the hierarchy.
Placement and company tests rarely go deep here, but a strong candidate is expected to state that the halting problem is undecidable and explain, in one line, why a general "will this program loop" checker cannot exist.
The short version
A Turing machine is the model of everything computable; recursive languages are decided by a machine that always halts, while RE languages may loop on rejects. The halting problem is RE but undecidable, proved by diagonalisation, and reductions carry that undecidability to other problems. Reproduce the halting argument by hand until the self-reference is clear. If the pumping lemma or pushdown automata are still shaky, settle those first, because this material sits directly on top of them. The full Theory of Computation learn module and GATE Guidance by Sanchit Sir sequence the whole hierarchy. Learn the halting proof cold, and decidability becomes dependable marks.
