Higher Type ITTM-recursion and Determinacy of Infinite games

P.D. Welch · 2026

Read Higher Type ITTM-recursion and Determinacy of Infinite games by P.D. Welch (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24640.txt.

Description

P. D. Welch outlines a theory of higher type recursion for infinite time Turing machines. Infinite time machines run through transfinite steps and can settle questions about real numbers. Kleene's classic type two recursion let machines take functions as inputs and outputs. Welch builds the matching theory for the infinite time setting. The aim is a bridge between this computability theory and classical descriptive set theory.

The bridge is built by computing the complexity of the machine's halting problem. Welch shows it matches exactly a complete game quantifier set at the third level of the Borel style hierarchy. That mirrors what Kleene and Moschovakis achieved for ordinary type two recursion and open determinacy. He also identifies the least ordinal not reachable by this generalised recursion. Its characterisation uses infinite nestings inside Gödel's constructible hierarchy. No large cardinal axioms are needed; everything is provable within analysis.

Catalog record

CREATORP.D. Welch
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE239 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24640

Browse the full library · About the Tower of Babel