Résume | We 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. |