ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

1. Logic

1991 MS Classification: 3,4,68 Welch, Philip, Kobe University, Japan The Length of Infinite Time Turing Machine Computations We show that the halting times of infinite time Turing Machines (considered as ordinals) are themselves all 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 Goedel’s constructible hierarchy: namely that of L_{λ} where λ is the supremum of halting times. A number of other open questions are thereby answered.