The Transfinite Action of 1 Tape Turing Machines
Author(s) -
Philip Welch
Publication year - 2005
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-26179-6
DOI - 10.1007/11494645_65
Subject(s) - transfinite number , computer science , turing machine , turing , arithmetic function , jump , mathematics , discrete mathematics , algorithm , programming language , physics , quantum mechanics , computation
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom