Computability theory: Turing machine, halting problem, Turing degrees, hyperarithmetic + analytical hierarchy, Π^1_1-set theory, Friedberg-Muchnik, KL-randomness.
recursion-theory
Turing machine + halting problem
Turing 1936: universal computational model. Halting-problem undecidable: no algorithm decides whether arbitrary TM halts on input.…
Post correspondence problem
Post 1946: undecidable problem about matching tile-sequences. Used to show undecidability of CFG-ambiguity, semi-Thue word-problems.…
Turing degrees + Turing jump
Post 1944: classify problems by relative-computability. Turing-jump A' = halting-problem-for-A. Friedberg-Muchnik 1956: incomparable r.e.…
Hyperarithmetic + analytical hierarchy
Kleene 1955 / Spector 1955: extends arithmetic-hierarchy to ordinal-stages via Π^1_1-comprehension. Δ^1_1 = hyperarithmetic. Foundation of…
Kolmogorov complexity (cross)
Cross-listed L0 information-theory. K(x) length of shortest program outputting x. Algorithmic-randomness. Bridges recursion-theory +…
Kolmogorov-Loveland randomness
Martin-Löf 1966 / Schnorr 1973 / Levin 1974. Formal definition of random infinite sequences via measure-1 sets / martingales. ML-random /…
Computable real analysis (Weihrauch)
Weihrauch 2000 'Computable Analysis'. Computability-on-reals via TTE Type-2-effectivity. Computable-functions on reals =…
Rice's theorem (extensional properties)
Rice 1953: any non-trivial extensional-property of partial-recursive-functions is undecidable. Generalises halting-problem. Foundational…
Recursive vs r.e.
Set is recursive (decidable) iff both it + complement are r.e. Halting-problem r.e. but not recursive. Friedberg 1958…
Computational complexity (P vs NP)
Cook-Levin 1971 NP-completeness. Major open: P vs NP. Karp 1972 21 NP-complete problems. Foundational. Bridges recursion + algorithm-design…
Descriptive set theory (Borel + projective)
Cantor 1880 / Lebesgue 1905 / Luzin 1917 / Suslin 1917. Borel-hierarchy + projective-hierarchy + analytic-coanalytic sets. Determinacy…
Kolmogorov program-space tradeoff
Solomonoff 1964 / Levin 1973: time-bounded Kolmogorov-complexity. Resource-bounded randomness. Foundation of average-case complexity +…
Turing machine + halting (1936)
Turing 1936: TM = (Q, Sigma, Gamma, delta, q0, F); halting problem H = {(M, w) : M halts on w} undecidable; Church-Turing thesis equates…
Kleene recursion theorem
Kleene 1938 second recursion theorem: every total computable f has fixed point e with phi_e = phi_{f(e)}; basis of self-reference +…
Post correspondence problem (1946)
Post 1946 PCP: given (a_i, b_i) pairs, find sequence i_1...i_n with a_{i_1}...a_{i_n} = b_{i_1}...b_{i_n}; PCP undecidable; reduction-base…
Rice theorem (1953)
H G Rice 1953: every nontrivial semantic property of partial computable functions is undecidable; index-set {e : phi_e in P} not recursive…
Arithmetic hierarchy (Sigma_n / Pi_n)
Kleene-Mostowski 1943-1947 arithmetic hierarchy: Sigma_n = exists-then-bounded-quantifiers; Pi_n = forall-then-bounded; Halting = Sigma_1;…
Priority method (Friedberg-Muchnik 1956)
Friedberg + Muchnik 1956 independently: solution to Post problem - exist intermediate Turing degrees 0 < d < 0'; finite-injury argument…