Metanavigation
Universität Hamburg - der Forschung, der Lehre, der Bildung, zur Homepage
Department of Mathematics
Suche
Search
Inhalt
Photo: UHH/Denstorf
This page:UHH > MIN > Department of Mathematics > Homepages

Homepages

(hier geht es zur ggf. vollständigeren Homepage im alten Layout)
(this way to the possibly more complete Homepage in the old layout)
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. P ≠ NP for infinite time Turing machines, Monatshefte für Mathematik 139:4 (2003), 335-340.
  8. Joel David Hamkins, Philip D. Welch. Pf ≠ NPf for almost all f. Mathematical Logic Quarterly 49:5 (2003), 536-540.
  9. 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.
  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.