Abstract
The Infinite Time Turing Machine model [8] of Hamkins and Kidder is, in an essential sense, a “Σ₂-machine” in that it uses a Σ₂ Liminf Rule to determine cell values at limit stages of time. We give a generalisation of these machines with an appropriate Σn rule. Such machines either halt or enter an infinite loop by stage ζ(n) =df μ ζ(n) [∃ Σ(n) > ζ(n) Lζ(n) ≺Σn LΣ(n)], again generalising precisely the ITTM case.
The collection of such machines taken together computes precisely those reals of the least model of analysis.
Sy-David Friedman. P. D. Welch. "Hypermachines." J. Symbolic Logic 76 (2) 620 - 636, June 2011. https://doi.org/10.2178/jsl/1305810767
Information