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. Let us define the machine, then walk the halting-problem argument step by step.
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. The tape is doing the counting the stack of a PDA could also do, but the TM's read-write tape is strictly more powerful.
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.
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.
[DIAGRAM: Nested ovals of the language hierarchy from inside out: Regular, then Context-Free, then Recursive (decidable), then Recursively Enumerable, with a final outer region labelled Not RE; each ring names its recognising machine (FA, PDA, halting TM, TM).]
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.
The proof is a diagonalisation, and it is worth following step by step.
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.
Both cases are contradictions. So the assumed H cannot exist, 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, type-2 (context-free) 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. This caps the ladder that begins with Regular Expressions and the Pumping Lemma and Context-Free Grammars and Pushdown Automata, so study them in order. 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.