Seminar on Mathematical Logic
2017/2018; 1st Semester
Institute for Logic, Language & ComputationUniversiteit van Amsterdam
Instructor: Prof. Dr. Benedikt
Löwe
ECTS: 3
Topic: Transfinite Computation.
Literature:
- Joel David Hamkins & Andy Lewis. Infinite Time Turing Machines. Journal of Symbolic Logic 65:2 (2000), 567-604.
- Kenneth Kunen. Set theory, An introduction to independence proofs. Studies in Logic and the Foundations of Mathematics Vol. 102, (North-Holland, 1980).
- Peter Koepke. Turing computations on ordinals. Bulletin of Symbolic Logic 11:3 (2005), 377-397.
- 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.
- 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.
- 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.
- Ralf Schindler. P ≠ NP for infinite time Turing machines, Monatshefte für Mathematik 139:4 (2003), 335-340.
- Joel David Hamkins, Philip D. Welch. Pf ≠ NPf for almost all f. Mathematical Logic Quarterly 49:5 (2003), 536-540.
- Vinay Deolalikar, Joel David Hamkins, Ralf Schindler. P ≠ NP∩co-NP for Infinite Time Turing Machines. Journal of Logic and Computation 15:5 (2005), 577-592.
- 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 | |