• README ⤓ .txt 2026-10-22T165042.936 000000000000808
  The metatheory of computation: what functions and sets are effectively computable, decidable, or enumerable, and how the undecidable problems are stratified by degree and hierarchy. It is the recursion-theoretic branch of mathematical logic, standing alongside model theory and proof theory.
• Algorithmic Randomness ⤓ .md 2026-08-19T230251.000 000000000040088
  Per Martin-Löf, "The definition of random sequences" (1966), giving the first definition that survived. Levin and Chaitin gave the incompressibility characterization (1970s); Schnorr gave the martingale one (1971). Developed by Kučera, Solovay, Downey, Hirschfeldt, Nies. The subject is the recursion theory of what a random object is.
• Arithmetical Hierarchy ⤓ .md 2026-08-20T060857.000 000000000033320
  Kleene, Mostowski (1940s). Classify sets of naturals by the number of alternating quantifiers over a recursive matrix. The analytical hierarchy extends this to second-order quantifiers.
• Bishop-Style Constructive ⤓ .md 2026-10-22T092707.000 000000000051848
  Errett Bishop, Foundations of Constructive Analysis (McGraw-Hill, 1967), rebuilt measure theory, Banach space theory, and complex analysis without excluded middle, answering the standing objection that constructive mathematics could not carry ordinary analysis. The revised edition, Bishop and Bridges, Constructive Analysis (Grundlehren 279, Springer, 1985), is the standard reference. Unlike Brouwer, Bishop imposed no philosophy of the continuum and added no principle that classical mathematics rejects.
• Choice Sequences ⤓ .md 2026-10-22T165042.936 000000000000872
  Brouwer (1920s). Intuitionist foundations. Sequences created by free choice. Not predetermined. Foundation for Brouwerian analysis.
• Church-Turing Thesis ⤓ .md 2026-08-20T060915.000 000000000035304
  Church (1936), Turing (1936), Kleene. Identifies the informal notion of effective calculability with a formal model of computation. A thesis, not a theorem: it links intuition to mathematics.
• Computability Theory ⤓ .md 2026-08-20T061023.000 000000000036688
  Gödel, Church, Turing, Kleene, Post (1930s). Formalize effective calculability. Several independently proposed models coincide. Foundation of the theory of the computable and the fourth branch of mathematical logic.
• Computable Analysis ⤓ .md 2026-08-20T061045.000 000000000054544
  Turing's computable reals (1936); Grzegorczyk (1955) and Lacombe (1955) independently gave the computable real functions; Pour-El and Richards, Computability in Analysis and Physics (1989); Weihrauch, Computable Analysis (2000), which established TTE as the standard framework. Computability on reals. TTE (Type-2 Theory of Effectivity). Computable real functions. Foundation of exact real computation.
• Computable Structure Theory ⤓ .md 2026-10-22T224109.000 000000000076192
  Fröhlich and Shepherdson, "Effective procedures in field theory" (Philosophical Transactions of the Royal Society A 248, 1956, 407–432), Rabin, "Computable algebra, general theory and theory of computable fields" (Transactions of the AMS 95, 1960, 341–360), and Mal'tsev, "Constructive algebras I" (Uspekhi Matematicheskikh Nauk 16(3), 1961; Russian Mathematical Surveys 16(3), 77–129) founded the subject twice, as effective algebra in the West and as the theory of constructivizations in Novosibirsk. The Russian school around Mal'tsev, Ershov and Goncharov set it inside Ershov's numbering theory — Teoriya numeratsii (Nauka, Moscow 1977), paralleled by the series "Theorie der Numerierungen" I–III (1973–1977). Ash and Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundations of Mathematics 144, Elsevier 2000), is the standard reference.
• Halting Problem ⤓ .md 2026-08-20T061213.000 000000000034008
  Turing (1936). The first proved-undecidable problem. Established by diagonalization, it grounds undecidability throughout logic and computer science.
• Higher Recursion Theory ⤓ .md 2026-08-20T061235.000 000000000037768
  Kleene, Kreisel, Sacks (1960s-70s). Generalizes computability beyond the finite: to recursive ordinals, admissible sets, and higher types. Recursion theory meets definability.
• Kolmogorov Complexity ⤓ .md 2026-08-20T061341.000 000000000036216
  Solomonoff (1960), Kolmogorov (1965), Chaitin (1966). Algorithmic information theory. Measures the information content of an individual object by its shortest description.
• Markov Principle ⤓ .md 2026-08-20T070032.000 000000000045112
  A.A. Markov (1950s). Russian constructive mathematics. Computable sequences. Church's thesis. Foundation of recursive mathematics.
• Realizability ⤓ .md 2026-10-22T092654.000 000000000061896
  Kleene introduced realizability (1945) to interpret intuitionistic logic via computable functions. A formula is true if "realized" by a computation. Connects constructive logic to computability theory. Extended by Kreisel, Troelstra, and others. Foundation for program extraction from proofs.
• Recursive Functions ⤓ .md 2026-10-22T090714.000 000000000035352
  Dedekind and Skolem formalized primitive recursion; Gödel, Herbrand, and Kleene defined the general recursive functions (1930s). A syntactic characterization of the computable number-theoretic functions.
• Recursively Enumerable Sets ⤓ .md 2026-10-22T085741.000 000000000036840
  Kleene, Post (1944). The semi-decidable sets and their structure. Post's problem and the priority method (Muchnik 1956, Friedberg 1957) opened the study of r.e. degrees.
• Rice's Theorem ⤓ .md 2026-10-22T180154.561 000000000000864
  Rice (1953). Sweeping undecidability result: every non-trivial semantic property of programs is undecidable. Generalizes the halting problem to all extensional properties.
• Turing Degrees ⤓ .md 2026-10-22T085808.000 000000000031360
  Turing (1939) introduced oracle machines; Post, Kleene developed degrees of unsolvability. Structure of relative computability. Measures how uncomputable a set is.
• Weihrauch Degrees ⤓ .md 2026-10-22T180154.561 000000000000888
  Klaus Weihrauch introduced the reducibility in the late 1980s within his Type-2 Theory of Effectivity; it circulated in two unpublished 1992 technical reports, "The degrees of discontinuity of some translators between representations of the real numbers" (ICSI TR-92-050, Berkeley) and "The TTE-interpretation of three hierarchies of omniscience principles" (Informatik Berichte 130, FernUniversität Hagen), and in Hagen theses of von Stein, Mylatz, Brattka, Hertling and Pauly. The modern theory dates from Gherardi and Marcone, "How incomputable is the separable Hahn-Banach theorem?" (Notre Dame Journal of Formal Logic 50(4): 393–425, 2009), which generalized the reducibility to multi-valued problems and proposed it as a uniform version of reverse mathematics, and from Brattka and Gherardi, "Weihrauch degrees, omniscience principles and weak computability" (Journal of Symbolic Logic 76(1): 143–176, 2011) and "Effective choice and boundedness principles in computable analysis" (Bulletin of Symbolic Logic 17(1): 73–117, 2011); Pauly, "On the (semi)lattices induced by continuous reducibilities" (Mathematical Logic Quarterly 56(5): 488–502, 2010), supplied the lattice structure independently. Brattka, Gherardi and Pauly's survey "Weihrauch Complexity in Computable Analysis" (2018) fixes the state of the subject.
• Zero-One Laws ⤓ .md 2026-08-20T061741.000 000000000046784
  Glebskii, Kogan, Liogon'kii, and Talanov (1969) in the Soviet literature and Ronald Fagin, "Probabilities on finite models" (Journal of Symbolic Logic, 1976), independently. Compton, Kolaitis, and Vardi extended the subject through the 1980s and 90s; Shelah and Spencer (1988) settled the sparse random-graph case.
• CRITERIA ⤓ .txt 2026-07-15T162128.000 000000000008880
  Required: At least one of the following: - A model or thesis of effective computation (recursive functions, Turing machines, Church-Turing) - A result about decidability or its failure (halting problem, Rice's theorem, r.e. sets) - A structure of the non-computable (Turing degrees, arithmetical hierarchy, higher recursion, Kolmogorov complexity)