The Length of Infinite Time Turing Machine Computations
PHILIP D. WELCH · Bulletin of the London Mathematical Society · 2000
We show that the halting times of infinite time Turing machines (considered as ordinals coded by sets of integers) are themselves all capable of being halting outputs of such machines. This gives a clarification of the nature of ‘supertasks’ or infinite time computations. The proof further yields that the class of sets coded by outputs of halting computations coincides with a level of Gödel's constructible hierarchy: namely that of Lλ where λ is the supremum of halting times. A number of other open questions are thereby answered. 1991 Mathematics Subject Classification 03D10, 03D60, 03E45.