Theory of Computation

Theory of Computation

Theory of computation answers a fundamental question: what can be computed? And equally important — what cannot? These answers define the outer limits of software engineering, explain why some problems have no algorithmic solution, and underpin formal methods for program verification.

The Chomsky Hierarchy

Noam Chomsky classified formal languages into four levels, each recognized by a different computational model. This hierarchy directly maps to language features in programming languages.

Regular Languages (Level 3) are recognized by finite automata (FA). A FA has a finite set of states, transitions on input characters, and accepting states. Regular languages include all patterns expressible by regular expressions: email validation, lexical tokens, simple pattern matching. Key limitation: no memory between characters — a FA cannot count matched parentheses because that requires unbounded memory.

Context-Free Languages (Level 2) are recognized by pushdown automata (PDA) — finite automata with a stack. The stack enables counting and matching: balanced parentheses, properly nested HTML, arithmetic expression parsing. Programming language syntax is context-free. Parsers (LL, LR, LALR) are implementations of PDAs.

Context-Sensitive Languages (Level 1) require linear bounded automata and capture some natural language constructs. Rarely used in CS practice.

Recursively Enumerable Languages (Level 0) are recognized by Turing machines — the most powerful computational model.

Turing Machines

A Turing machine has: an infinite tape (the memory), a read/write head, a finite set of states, and a transition function δ: (state, symbol) → (new state, new symbol, direction). Despite its simplicity, a Turing machine can simulate any algorithm computable on any physical computer.

The Church-Turing Thesis (not a theorem, a philosophical claim) states that anything computable by any physical device is computable by a Turing machine. This defines what "computation" means.

Universal Turing Machine: a single TM that can simulate any other TM, given that TM's description as input. This is the theoretical basis for general-purpose computers and interpreters.

Decidability

A language L is decidable (recursive) if there exists a TM that halts on all inputs and correctly accepts inputs in L and rejects inputs not in L. Most problems you'll ever code are decidable.

A language is recognizable (recursively enumerable) if a TM accepts all inputs in L — but may loop forever on inputs not in L. An algorithm exists, but it might not terminate.

An undecidable problem has no TM that always halts and gives the correct answer.

The Halting Problem

Alan Turing's 1936 proof that the Halting Problem is undecidable is one of the most important results in mathematics.

Claim: There is no algorithm H that, given any program P and input I, always correctly determines whether P halts on I.

Proof (by contradiction): Suppose H exists. Construct a program D that does the following: given input P, if H(P, P) says "halts", then D loops forever; if H(P, P) says "loops forever", then D halts. Now ask: what does H(D, D) do? If it says "halts", then D loops forever — contradiction. If it says "loops forever", then D halts — contradiction. Therefore H cannot exist.

This diagonalization argument shows there is a hard limit on what any algorithm can determine about other programs. Practical implication: static analysis tools (linters, type checkers) can never perfectly detect all bugs or termination issues — they are fundamentally incomplete. They can be sound (no false negatives) or complete (no false positives) but not both.

Rice's Theorem

Rice's Theorem generalizes the Halting Problem: any non-trivial semantic property of programs is undecidable. "Does this program always return a positive number?" "Does this function compute the square root?" "Is this program equivalent to that one?" — all undecidable in general.

This is why:

• Virus scanners use heuristics, not exact detection — exactly determining if code is malicious is undecidable
• Type checkers use conservative approximations — they might reject valid programs to remain sound
• Test suites are necessary — full program verification is undecidable in general

Reductions

To prove problem B is undecidable, show it is at least as hard as the Halting Problem by reduction: a polynomial-time algorithm that converts any Halting Problem instance to a B instance. If B were decidable, we could solve the Halting Problem — contradiction.

The same technique proves NP-completeness in complexity theory. The landscape of computational problems is partially ordered by reducibility, forming a rich theoretical structure that explains why some problems are intrinsically hard.

Applications in Practice

Understanding computability shapes how you approach problems. When a specification asks for something impossible (e.g., "automatically determine if any two versions of this code are equivalent"), you know to either restrict the problem (only certain code patterns), use approximations, or ask for human judgment.

Compilers apply these concepts directly: lexical analysis uses finite automata, parsing uses context-free grammars, and the theoretical limits of static analysis follow from Rice's theorem.