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
Fingerprint
Dive into the research topics of 'The transfinite action of 1 tape turing machines'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver