The length of infinite time Turing machine computations

Authors
Citation
Pd. Welch, The length of infinite time Turing machine computations, B LOND MATH, 32, 2000, pp. 129-136
Citations number
6
Categorie Soggetti
Mathematics
Journal title
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY
ISSN journal
00246093 → ACNP
Volume
32
Year of publication
2000
Part
2
Pages
129 - 136
Database
ISI
SICI code
0024-6093(200003)32:<129:TLOITT>2.0.ZU;2-7
Abstract
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 th at the class of sets coded by outputs of halting computations coincides wit h a level of Godel's constructible hierarchy: namely that of L-lambda where lambda is the supremum of halting times. A number of other open questions are thereby answered.