Part IX: Computational Mathematics and Logic

Computability theory draws the line between what is mechanically calculable and what is not. Complexity theory refines this to what is tractably calculable. Information theory quantifies the content of messages.

9.1 Computability Theory

Turing machine: A formal model of computation: a finite-state controller operating on an infinite tape, reading and writing symbols. A Turing-computable function is one computed by a Turing machine.

Church-Turing thesis: Every "effectively calculable" function is Turing-computable. This is a thesis, not a theorem — it cannot be proved because "effectively calculable" is informal.

The Halting Problem (Turing, 1936): There is no Turing machine that decides, for any machine M and input w, whether M halts on w. Proof: assume H decides the halting problem. Define D(M) = halt if M(M) does not halt, loop if M(M) halts. Then D(D) halts iff D(D) does not halt — contradiction.

Undecidable problems: Many important mathematical problems are undecidable:

• Entscheidungsproblem (FOL validity): undecidable (Church, Turing, 1936)
• Hilbert's tenth problem (Diophantine equations): undecidable (Matiyasevich, 1970)
• Word problem for groups: undecidable (Novikov, Boone, 1952-55)
• Tiling the plane with a given finite set of tiles: undecidable

Reducibility: Problem A reduces to problem B if an algorithm for B solves A. This defines a partial order on problems by their computational difficulty.

9.2 Complexity Theory

Time complexity: A Turing machine runs in time T(n) if it halts within T(n) steps on inputs of length n.

Class	Informal description
P	Problems solvable in polynomial time
NP	Problems whose solutions can be verified in polynomial time
NP-complete	The hardest problems in NP
PSPACE	Problems solvable in polynomial space
EXP	Problems solvable in exponential time

P vs. NP: Is P = NP? If yes, every efficiently verifiable problem is efficiently solvable — encryption would fail, mathematical proofs could be found by search, creativity would be mechanizable. Almost universally believed to be false; completely open. The most important open problem in computer science and one of the Millennium Prize Problems.

NP-completeness: Cook's theorem (1971): Boolean satisfiability (SAT) is NP-complete. Every NP problem reduces to SAT. Karp (1972) showed 21 natural problems are NP-complete, including graph coloring, subset sum, traveling salesman.

9.3 Information Theory (Shannon, 1948)

Entropy: For a discrete probability distribution P = (p₁, …, pₙ), the Shannon entropy is:

H(P) = − ∑ pᵢ log₂ pᵢ  (bits)

H = 0 when one pᵢ = 1 (certainty); H = log₂ n when all pᵢ = 1/n (maximum uncertainty).

Mutual information: I(X;Y) = H(X) + H(Y) − H(X,Y). How much knowing Y tells you about X.

Shannon's source coding theorem: The minimum average number of bits per symbol needed to encode a source with entropy H is H bits. No lossless compression can do better.

Shannon's channel capacity theorem: The maximum rate at which information can be reliably transmitted over a noisy channel with capacity C is C bits per channel use. Channels with capacity C exist that achieve this rate with arbitrary reliability.

Kolmogorov complexity: The algorithmic information content K(x) of string x is the length of the shortest program that prints x. K is incomputable but provides a deep framework for defining randomness, compressibility, and information.

9.4 Formal Languages and Automata

Chomsky hierarchy:

• Type 0 (Recursively Enumerable): Languages recognized by Turing machines
• Type 1 (Context-Sensitive): Recognized by linear-bounded automata
• Type 2 (Context-Free): Recognized by pushdown automata; generated by CFGs. Programming language syntax is typically context-free
• Type 3 (Regular): Recognized by finite automata; generated by regular grammars. Pattern matching via regular expressions

Pumping lemmas: Tools for proving languages are not in a given class. The regular pumping lemma shows {aⁿbⁿ : n ≥ 1} is not regular.

---