Abstract
• We produce a classification of the pointclasses of sets of reals produced by infinite time turing machines with 1-tape. The reason for choosing this formalism is that it apparently yields a smoother classification of classes defined by algorithms that halt at limit ordinals.
• We consider some relations of such classes with other similar notions, such as arithmetical quasi-inductive definitions.
• It is noted that the action of many steps of such a machine can correspond to the double jump operator (in the usual Turing sense): a a
• The ordinals beginning gaps in the clockable ordinals are admissible ordinals, and the length of such gaps corresponds to the degree of reflection those ordinals enjoy.
Translated title of the contribution | The transfinite action of 1 tape turing machines |
---|---|
Original language | English |
Pages (from-to) | 532 - 539 |
Number of pages | 8 |
Journal | Lecture Notes in Computer Science |
Volume | 3526 |
DOIs | |
Publication status | Published - Mar 2005 |
Bibliographical note
Publisher: Springer-Verlag, BerlinOther identifier: IDS Number: BCP14