The transfinite action of 1 tape turing machines

Research output: Contribution to journalArticle (Academic Journal)peer-review

4 Citations (Scopus)

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 contributionThe transfinite action of 1 tape turing machines
Original languageEnglish
Pages (from-to)532 - 539
Number of pages8
JournalLecture Notes in Computer Science
Volume3526
DOIs
Publication statusPublished - Mar 2005

Bibliographical note

Publisher: Springer-Verlag, Berlin
Other 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