Theory of Computation — The Full Map

Theory of Computation answers three fundamental questions:
① What problems can be solved by a computer at all? (Computability)
② What problems can be solved efficiently? (Complexity)
③ What is the minimum machine needed to solve a given problem? (Automata)

This is the most mathematically pure branch of CS — it uses formal proofs, not code. But it has enormous practical impact: every regex engine, every parser, every programming language, every proof that certain bugs cannot be detected automatically — all rooted here.

The three pillars:

AUTOMATA THEORY — models of computation:
- Finite Automata (FA): the simplest machine. Has states, reads input, accepts or rejects. Models regex.
- Pushdown Automata (PDA): FA + a stack. Models programming language syntax (parsers).
- Turing Machine (TM): the most powerful theoretical model. Has infinite tape. Models everything a real computer can do.

FORMAL LANGUAGES — what each machine can recognize:
- Regular Languages: recognized by FA. Described by regular expressions.
- Context-Free Languages: recognized by PDA. Described by context-free grammars. Most programming language syntax is CFL.
- Recursively Enumerable Languages: recognized by Turing Machines.
- Some languages cannot be recognized by ANY machine (undecidable problems).

COMPLEXITY THEORY — efficiency of computation:
- P: problems solvable in polynomial time (efficient)
- NP: problems verifiable in polynomial time (maybe hard to solve)
- NP-Complete: the hardest problems in NP. If any one is in P, then P=NP.
- P vs NP: the most famous unsolved problem in mathematics. Million dollar prize.

The Chomsky Hierarchy — a beautiful classification:
Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable
Each level requires a more powerful machine. Each level is strictly larger than the previous.

1# Theory of Computation — orientation
2
3# The central question: given a PROBLEM and a MACHINE,
4# can the machine solve the problem?
5
6problems = {
7    "Match email regex":           ("Regular",       "Finite Automaton",   "O(n)"),
8    "Parse Python syntax":         ("Context-Free",  "Pushdown Automaton", "O(n³)"),
9    "Type-check a program":        ("Context-Sens.", "Linear Bounded TM",  "PSPACE"),
10    "Run any program":             ("Rec. Enum.",    "Turing Machine",     "varies"),
11    "Does program halt?":          ("UNDECIDABLE",   "No machine",         "∞"),
12    "Is program correct?":         ("UNDECIDABLE",   "No machine",         "∞"),
13    "Shortest path (Dijkstra)":    ("P",             "TM (poly time)",     "O(E log V)"),
14    "Traveling Salesman (exact)":  ("NP-Hard",       "TM (exp time)",      "O(n! )"),
15    "Boolean Satisfiability":      ("NP-Complete",   "TM (exp time)",      "O(2ⁿ)"),
16}
17
18print(f"{'Problem':<35} {'Class':<15} {'Machine':<22} {'Complexity'}")
19print("─" * 90)
20for problem, (cls, machine, complexity) in problems.items():
21    print(f"{problem:<35} {cls:<15} {machine:<22} {complexity}")
22
23# The Chomsky Hierarchy in one line each:
24print("
25Chomsky Hierarchy:")
26print("  Type 3: Regular          → Finite Automaton      → a*b+, [0-9]+")
27print("  Type 2: Context-Free     → Pushdown Automaton    → aⁿbⁿ, {balanced}")
28print("  Type 1: Context-Sensitive→ Linear Bounded TM     → aⁿbⁿcⁿ")
29print("  Type 0: Rec. Enumerable  → Turing Machine        → anything computable")
30print("  -----:  Undecidable      → NO machine            → halting problem")