Sendai Logic - 仙台ロジック Mathematical Institute, Graduate School of Science, Tohoku University

2018.07.27. Paul-Elliot Anglès D'Auriac

On Infinite Time Turing Machine and and its related ordinals.

  • Date/Time: July 27, 2018 (Friday) / 16:00 - 17:00

  • Speaker: Paul-Elliot Anglès D’Auriac 氏 (パリ・エスト・クレテイユ大学)

  • Venue: Rm 1201, Science Complex A, Tohoku Univ.

  • Abstract: In 1998, Hamkins and Lewis introduced Infinite Time Turing Machines (ITTMs), a version of Turing Machines where time is allowed to run through the ordinals instead of the integers. This model of computation revealed itself to have interesting connections with set theory and in particular Godel’s constructible hierarchy. In this talk, we will be interested in the properties of the ordinals that naturally arises in the study of ITTMs, such as those that correspond to halting time, or that have a code that can be written on the tape of an ITTM. If time allows, we will prove the λ-ζ-Σ-Theorem from Welch, and the fact that supremum of halting times and writable ordinals are the same.