Orateur(s)  Philip Welch  University of Bristol,

Titre  Transfinite Computational Models and Low levels of Determinacy 
Date  09/06/2021 
Horaire  16:00 à 17:15 

Diffusion  https://uparis.zoom.us/rec/share/0SqvOEgWuCCvy2PJXLohc_UI7CbxGF0fc4HDy0SJquh0e9CPQyGJxUMn_1MYf5V.kUL2k7SOmEpefxZ 
Résume  We sketch the theory of higher type Infinite Time Turing machine (ITTM) theory in the style of Kleene's type2 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 GSigma^0_3set 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. 
Salle  Contacter Sylvy Anscombe ou Alessandro Vignati 
Adresse  