Bonn Mathematical Logic Group

Higher set theory (V4A3)
Classical and ordinal computability

Lecturer

Assistant and exercise class

Time and location

Lecture: Tuesdays and Thursdays, both 16:15-18:00 in room 0.007, in the main building Endenicher Allee 60.
Exercise class: Fridays, 12:15-14:00 in room N0.003, in the rear building behind Endenicher Allee 60.

Remark

This lecture course presents the classical theory of Turing computability and its equivalents, and then generalizes computations on the natural numbers to analogous computations on the set theoretical ordinal numbers. The first half of the course is introductory, the second half assumes knowledge of basic axiomatic set theory as presented in the introductory module “Mengenlehre“. Formally the course is classified as the Master module “Higher Set Theory, V4A3” but it can also be taken by Bachelor students with sufficient knowledge in basic set theory. An exercise class will be offered.

Vorbemerkung

Diese Vorlesung stellt die klassische Theorie der Turing-Berechenbarkeit und ihrer Äquivalenzen vor und verallgemeinert dann Berechnungen mit natürlichen Zahlen zu Berechnungen mit Ordinalzahlen. Die erste Hälfte des Vorlesung hat den Charakter einer Einführung, während die zweite Hälfte elementare Mengenlehre voraussetzt, etwa aus dem Einführungsmodul “Mengenlehre”. Formal ist die Vorlesung als Master-Modul “Higher Set Theory, V4A3” eingestuft, aber sie kann auch von Bachelor-Studierenden mit hinreichenden Mengenlehrekenntnissen gehört werden. Eine Übungsgruppe wird angeboten. Weitere Fragen zur Einordnung in das Bachelorstudium können mit dem Dozenten besprochen werden.

Contents

Classical computability theory, formerly called “recursion theory”, studies abstract models of computation processes. From today's perspective one may view these models as idealized computers, controlled by finite programs and equipped with arbitrary time and memory resources. The models define the notion of a computable function from natural numbers to natural numbers. The class of computable functions satisfies a number of closure properties and structural properties. Not every function is computable, and indeed there are many natural mathematical functions which are not computable. Computable functions may be classified by the complexity (in terms of time or memory requirements) of calculating them. We shall briefly discuss complexity theory including the famous and central P≠NP problem.

Ordinal computability uses strong analogies between natural numbers and Cantor's ordinal numbers. Various types of calculations with ordinals are defined and studied as in classical computability. The theory may be parametrized by restricting to initial segments of the class of ordinals. The restriction to natural numbers agrees with classical computability theory. Allowing all ordinal numbers gives a new approach to Gödel's model of constructible sets. We shall prove some fundamental properties of constructible sets via ordinal computability.

Literature

N. J. Cutland, Computability, Cambridge UP, 1980

K. J. Devlin, Constructibility, Springer, 1984

H. B. Enderton, Computability Theory: An Introduction to Recursion Theory, Academic Press, 2011

J. R. Shoenfield, Recursion Theory, Springer, 2000

P. Koepke, Turing Computations on Ordinals, Bulletin of Symbolic Logic 11, 2005

P. Koepke, Ordinal Computatility, in: Lecture Notes in Computer Science 5028, 2009

Exercise sheets

  1. released 7 April, due 12 April PDF
  2. released 14 April, due 21 April PDF
  3. released 24 April, due 28 April PDF
  4. released 28 April, due 3 May PDF
  5. released 5 May, due 10 May PDF
  6. released 12 May, due 17 May PDF
  7. released 19 May, due 24 May PDF
  8. released 26 May, due 31 May PDF
  9. released 2 June, due 7 June PDF
  10. released 23 June, due 28 June PDF
  11. released 30 June, due 5 July PDF

 

Last changed: 30 June 2011