Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-30T22:13:37.172Z Has data issue: false hasContentIssue false
  • English
  • Français

THE LENGTH OF INFINITE TIME TURING MACHINE COMPUTATIONS

Published online by Cambridge University Press:  01 March 2000

P. D. WELCH
P. D. WELCH
Affiliation:
Graduate School of Science & Technology, Kobe University, Rokko-dai, Nada-ku, Kobe 657, Japan School of Mathematics, University of Bristol, Bristol BS6 6BH
Get access

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 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.

Type
NOTES AND PAPERS
Information
Bulletin of the London Mathematical Society , Volume 32 , Issue 2 , March 2000 , pp. 129 - 136
Copyright
© The London Mathematical Society 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)