UvA Logo

Seminar on Mathematical Logic

2017/2018; 1st Semester

Institute for Logic, Language & Computation
Universiteit van Amsterdam

Instructor: Prof. Dr. Benedikt Löwe
ECTS: 3
Topic: Transfinite Computation.
Literature:

  1. Joel David Hamkins & Andy Lewis. Infinite Time Turing Machines. Journal of Symbolic Logic 65:2 (2000), 567-604.
  2. Kenneth Kunen. Set theory, An introduction to independence proofs. Studies in Logic and the Foundations of Mathematics Vol. 102, (North-Holland, 1980).
  3. Peter Koepke. Turing computations on ordinals. Bulletin of Symbolic Logic 11:3 (2005), 377-397.
  4. Peter Koepke, Infinite Time Register Machines. In: Arnold Beckmann, Ulrich Berger, Benedikt Löwe, John V. Tucker (eds.), Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006, Proceedings. Lecture Notes in Computer Science Vol. 3988, (Springer, 2006), 257-266.
  5. Peter Koepke, Russell G. Miller. An Enhanced Theory of Infinite Time Register Machines. In: Arnold Beckmann, Costas Dimitracopoulos, Benedikt Löwe (eds.). Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008, Athens, Greece, June 15-20, 2008, Proceedings. Lecture Notes in Computer Science Vol. 5028, (Springer, 2008), 306-315.
  6. Merlin Carl, Tim Fischbach, Peter Koepke, Russell G. Miller, Miriam Nasfi, Gregor Weckbecker. The basic theory of infinite time register machines. Archive for Mathematical Logic 49:2 (2010), 249-273.
  7. Ralf Schindler. PNP for infinite time Turing machines, Monatshefte für Mathematik 139:4 (2003), 335-340.
  8. Joel David Hamkins, Philip D. Welch. PfNPf for almost all f. Mathematical Logic Quarterly 49:5 (2003), 536-540.
  9. Vinay Deolalikar, Joel David Hamkins, Ralf Schindler. PNPco-NP for Infinite Time Turing Machines. Journal of Logic and Computation 15:5 (2005), 577-592.
  10. Merlin Carl, Benedikt Löwe, Benjamin G. Rin. Koepke Machines and Satisfiability for Infinitary Propositional Languages. In: Jarkko Kari, Florin Manea, Ion Petre (eds.). Unveiling Dynamics and Complexity, 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12-16, 2017, Proceedings. Lecture Notes in Computer Science Vol. 10307, (Springer, 2017), 187-197.

Schedule.

Tuesday 31 October 2017 17-19
F1.15 (ILLC Seminar Room)
Introduction and distribution of topics.
Thursday 16 November 2017 17-19
F1.15 (ILLC Seminar Room)
Benedikt Löwe Infinite Time Turing Machines. Basics. Hamkins & Lewis, 2000, Sections 1 & 2.
Friday 17 November 2017 13-15
F1.15 (ILLC Seminar Room)
CANCELLED
Tuesday 21 November 2017 17-19
F1.15 (ILLC Seminar Room)
Tim Henke Infinite Time Turing Machines. Clockables & writables. Hamkins & Lewis, 2000, Sections 3 & 8.
Wednesday 22 November 2017 15-17
F1.15 (ILLC Seminar Room)
Davide Emilio Quadrellaro Infinite Time Turing Machines. Halting problems & the Lost Melody Theorem. Hamkins & Lewis, 2000, Section 4.
Thursday 23 November 2017 17-19
F1.15 (ILLC Seminar Room)
Chase Ford Infinite Time Turing Machines. Oracles. Hamkins & Lewis, 2000, Section 5.
Friday 24 November 2017 13-15
F1.15 (ILLC Seminar Room)
Claudio Agostini Basic theory of constructibility. Kunen, 1980, Chapter VI.
Tuesday 28 November 2017 17-19
F1.15 (ILLC Seminar Room)
Max Bohnet Koepke machines. Koepke, 2005.
Wednesday 29 November 2017 15-17
F1.15 (ILLC Seminar Room)
Ethan Lewis Infinite Time Register Machines. Koepke, 2006; Koepke & Miller, 2008; Carl et al., 2010.
Tuesday 12 December 2017 17-19
F1.15 (ILLC Seminar Room)
Raja Damanik & Kristoffer Kalavainen Infinite Time Complexity Theory, Part I. Schindler, 2003; Hamkins & Welch, 2003; Deolalikar, Hamkins, & Schindler, 2005.
Wednesday 13 December 2017 15-17
F1.15 (ILLC Seminar Room)
Raja Damanik & Kristoffer Kalavainen Infinite Time Complexity Theory, Part II. Schindler, 2003; Hamkins & Welch, 2003; Deolalikar, Hamkins, & Schindler, 2005.
Thursday 14 December 2017 17-19
F1.15 (ILLC Seminar Room)
Sam Adam-Day Infinite Time Complexity Theory, Part III. Carl, Löwe, & Rin, 2017.
Friday 15 December 2017 13-15
F1.15 (ILLC Seminar Room)
Overspill session
Last update: 17 November 2017.