Dozent Beschreibung Rekursionstheorie Wintersemester 2021/22 Universität Hamburg Fachbereich Mathematik Prof. Dr. Benedikt Löwe Die Rekursionstheorie oder Berechenbarkeitstheorie ist die mathematische Theorie der Funktionen, die durch einen digitalen Computer berechnet werden können. Sobald man eine konkrete Definition dieses Begriffs hat, stellt sich heraus, dass nicht alle Funktionen diese Eigenschaft haben können und man somit die Grenzen der Berechenbarkeit mathematisch untersuchen kann. Es gibt nicht nur berechenbare und nicht berechenbare Funktionen, sondern man kann nicht berechenbare Funktionen nach ihrem Grad der Unberechenbarkeit klassifizieren. In dieser Vorlesung wollen wir die Grundbegriffe dieser Theorie erlernen und einige grundlegende Eigenschaften der Grade der Unberechenbarkeit kennenlernen. Im letzten Teil der Vorlesung werden diese Ergebnisse im Bereich der mathematischen Logik angewandt und wir beweisen zwei wichtige Resultate unter Verwendung der Ergebnisse aus dem ersten Teil: den ersten Gödelschen Unvollständigkeitssatz und die Unentscheidbarkeit von Tautologien in der Logik erster Stufe (das sogenannte Entscheidungsproblem). Wir behandeln unter anderem: Turing-Maschinen und Turing-Berechenbarkeit. Registermaschinen. Der Churchsche Funktionenkalkül. Das Software-Prinzip und universelle Maschinen. Das Halteproblem. Rekursiv aufzählbare Mengen. Diagonalisierung. Reduktionsfunktionen. Der Satz von Rice. Grade der Unberechenbarkeit. Kodierung der Logik in Turing-Maschinen. Der erste Gödelsche Unvollständigkeitssatz und das Entscheidungsproblem. The name of the field: Recursion Theory vs Computability Theory. Mathematical concepts (proof / computation / geometric construction): sufficient criteria for positive results; necessary criteria for negative results. The Entscheidungsproblem: Hilbert-Ackermann (1928). Decision procedure for propositional logic. Solution of the Entscheidungsproblem: Church and Turing. Historical background on Turing. §1 Basics. Alphabets, words, infinite words. Partial functions; concatenation of partial functions. §2 Models of Computation. Transition functions, output functions. Computations. Halting of computations. Definition of a partial function represented by a program. Lecture Notes. Remarks on the status of the definition of "model of computation": neither necessary nor sufficient, just a technical tool. Computable functions, computable sets. There are countably many computable functions; there are non-computable functions. §3 The halting problem. Definition of the halting problem. Compositionality and Case Distinction. Non-computability of the halting problem. §4 Reduction Functions. Many-one reductions. The relation of many-one reducibility: reflexivity and transitivity. Many-one degrees. The degree of the empty set and the set of all words. Lecture Notes. The many-one degrees of the computable sets. Universality and the Software Principle. §5 Computably enumerable sets. Definition of computably enumerable sets. The halting problem is computably enumerable. Equivalent formulations of computable enumerability (under the additional assumptions of Domain Check and Range Check). Closure of computably enumerable sets under many-one reductions. Informal argument why Domain Check is a reasonable assumption for models of computation. Lecture Notes. Informal argument why Range Check is a reasonable assumption for models of computation: computable bijection between the set of pairs of natural numbers and the set of natural numbers; mimicking the parallel computation of infinitely many computations in one. §6 Turing machines. Definition. Check that they are a model of computation in our sense. §7 Register machines. Definition. Check that they are a model of computation in our sense. Lecture Notes. §8 Other models of computation & the Church-Turing thesis. WHILE programming languages; pseudocode. Relationship to our earlier informal arguments. Computational frameworks. Equivalence of computational frameworks. Equivalence of Turing machines, register machines, and WHILE programming languages (without proof); brief sketch of the proof strategy. The Church-Turing Thesis. §9 Diagonalisation. Intersection of two (finitely many) c.e. sets are c.e. The set of programs that have non-empty domain is c.e. The set of programs that have domain at least size k is c.e. Lecture Notes. A set is c.e. if and only if it is the range of total computable function. Co-c.e. sets. A set is computable if and only it is c.e. and co-c.e. The complement of the Halting Problem is not c.e.  Selfduality; examples of selfdual and nonselfdual sets. §10 Turing joins. Definition of the Turing join. Turing joins are upper bounds. Turing joins are selfdual. Turing joins are least upper bounds. Lecture Notes. §11 The s-m-n Theorem. The s-m-n Theorem or Parameter Theorem. Currying. Application: a set is c.e. if and only if it many-one reducible to the halting problem. Hardness and completeness. The halting problem is c.e.-complete. §12 Index sets & Rice's Theorem. Parametrisation of the c.e. sets. The boldface Halting problem K0. Index sets: examples and non-examples (K is not an index set without proof). Rice' Theorem. Proof. K1 as the index set variant of the Halting problem. Lecture Notes. Proof that Inf and Tot are equivalent. Remarks on the fact that one reduction function can show multiple reduction results. Proof that K reduces to Fin. All three index sets Fin, Inf, and Tot are at least as complex as the Turing join of K and its complement. §13 Π2 sets. Definitions. Π2 hardness and completeness. Inf and Tot are Π2 complete. Discussion of Post's Theorem (without proof). Lecture Notes. Σ1 and Π1 sets. Closure properties of classes of sets: closure under many-one reducibility, unions, intersections, and complements. Normal Form Theorem for c.e. sets. Closure under unions and intersections for Σ1, Π1, Σ2, and Π2 sets. Abstract theorem: classes with closure properties cannot have complete sets. Application: There are Σ2 sets that are not Π2 and therefore is Fin not equivalent to Inf. The arithmetical hierarchy; the arithmetical hierarchy does not collapse (without proof). Lecture Notes. §14 Recursion Theorem. Recursion Theorem / Kleene's Fixed Point Theorem. Applications. The Halting Problem is not an index set. §15 Growth Functions. Growth functions and their computability. Functions that grow too fast to be computable. The Ackermann function (without details). Lecture Notes. Improvement on the proof from Lecture X. Another example of an application of the Recursion Theorem: a function that is constant and outputs its own code. §16 Gödel's Incompleteness Theorem: general discussion. Standard formulation of the Incompleteness Theorem (for arithmetic). Essential incompleteness. Standard presentation of an informal proof: self-reference. Technical obstacles. Advantages of proving it for set theory rather than arithmetic. §17 Theories of hereditarily finite sets. Finite levels of the von Neumann hierarchy and their properties. HF and its set-theoretic properties: HF is a model of FST and therefore contains finite sequences. The theory HFST. The augmented language of hereditarily finite sets and the their theory AHFST. Non-standard models of AHFST. Coding of formulas in AHFST. Lecture Notes. §18 Reconstruction of Provability in HF. Reminder: sequent calculi, notions of sequent, derivation, derivability. Computable axiom systems, computable calculi. The set of formulas provable from a computable axiom system in a computable calculus is c.e. The Gentzen calculus is computable. §19 Reconstruction of Computability in LST+. Formula describing that a computation halts. Lecture Notes. Formula describing that a program P halts and produces non-empty output on a given input w. Formula describing the truth of a Π1 statement. Formula is computable from P and w. The set of true formulas is Π1-hard. §20 Gödel's Incompleteness Theorems. Proof of the first incompleteness theorem. Incompleteness is a stronger limitative result than compactness. Second incompleteness theorem (without proof). Lecture Notes.