Prof Dr Benedikt Loewe: Rekursionstheorie (WS 2021/22)

	Rekursionstheorie Wintersemester 2021/22 Universität Hamburg Fachbereich Mathematik
Dozent	Prof. Dr. Benedikt Löwe
Beschreibung	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.
First Lecture. Wednesday 13 October 2021, 11-13.	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.
Second Lecture. Friday 22 October 2021, 16-18.	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.
Third Lecture. Wednesday 3 November 2021, 16-18.	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.
Fourth Lecture. Tuesday 16 November 2021, 11-13.	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.
Fifth Lecture. Tuesday 23 November 2021, 16-18.	§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.
Sixth Lecture. Tuesday 30 November 2021, 16-18.	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.
Seventh Lecture. Tuesday 21 December 2021, 11-13.	*§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 K₀. Index sets: examples and non-examples (K is not an index set without proof). Rice' Theorem. Proof. K₁ as the index set variant of the Halting problem. Lecture Notes.
Eighth Lecture. Wednesday 5 January 2022, 14-16.	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 Π₂ sets. Definitions. Π₂ hardness and completeness. Inf* and Tot are Π₂ complete. Discussion of Post's Theorem (without proof). Lecture Notes.
Ninth Lecture. Thursday 6 January 2022, 16-18.	Σ₁ and Π₁ 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 Σ₁, Π₁, Σ₂, and Π₂ sets. Abstract theorem: classes with closure properties cannot have complete sets. Application: There are Σ₂ sets that are not Π₂ and therefore is Fin not equivalent to Inf. The arithmetical hierarchy; the arithmetical hierarchy does not collapse (without proof). Lecture Notes.
Tenth Lecture. Wednesday 12 January 2022, 14-16.	*§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.
Eleventh Lecture. Thursday 13 January 2022, 16-18.	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.
Twelfth Lecture. Wednesday 19 January 2022, 14-16.	§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.
Thirteenth Lecture. Tuesday 24 January 2022, 10-12.	Formula describing that a program P halts and produces non-empty output on a given input w. Formula describing the truth of a Π₁ statement. Formula is computable from P and w. The set of true formulas is Π₁-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.