Séminaires : Séminaire Général de Logique

Equipe(s) : lm,
Responsables :S. Anscombe, A. Khélif, A. Vignati
Email des responsables : sylvy.anscombe@imj-prg.fr, vignati@imj-prg.fr
Salle : 1013
Adresse :Sophie Germain

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion

Orateur(s) Philip Welch - University of Bristol,
Titre Transfinite Computational Models and Low levels of Determinacy
Horaire16:00 à 17:15
Diffusion https://u-paris.zoom.us/rec/share/0SqvOEgWuCCvy2PJXLohc_UI-7CbxGF0fc4HDy0SJquh0e9CPQyGJxUMn_1MYf5V.kUL2k-7SOmEpefxZ
RésumeWe sketch the theory of higher type Infinite Time Turing machine (ITTM) theory in the style of Kleene's type-2 recursion theory on reals, replacing ordinary turing machines by ITTM's. Besides being an interesting theory itself with many open questions, it turns out that there is a pencil and paper algorithm, i.e. a recursive isomorphism, for converting indices for such halting computations into a listing of games won by Player 1 with G_delta_sigma payoff set - in other words considering Determinacy(Sigma^0_3) for games on Cantor or Baire space. (In more formal terms the Halting Problem for this kind of computation is recursively isomorphic to a complete G-Sigma^0_3-set of integers.) One feature of this is that the ordinal where such machines crash is precisely the level in the constructible hierarchy over which strategies for such games are all definable.
AdresseSophie Germain