| Authors |
|
| Publication date |
2007
|
| Host editors |
-
S.B. Cooper
-
B. Löwe
-
A. Sorbi
|
| Book title |
Computation and Logic in the Real World
|
| Book subtitle |
Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007 : proceedings
|
| ISBN |
|
| ISBN (electronic) |
|
| Series |
Lecture Notes in Computer Science
|
| Event |
Third Conference of Computability in Europe CiE 2007
|
| Pages (from-to) |
488-496
|
| Publisher |
Berlin: Springer
|
| Organisations |
-
Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
|
| Abstract |
The Ordinal Register Machine (ORM) is one of several different machine models for infinitary computability. We classify, by complexity, the sets that can be decided quickly by ORMs. In particular, we show that the arithmetical sets are exactly those sets that can be decided by ORMs in times uniformly less than \ensuremathωω. Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than ωCK1.
|
| Document type |
Conference contribution
|
| Note |
Proceedings title: Computation and Logic in the Real World
Publisher: Springer
Editors: B. Cooper, B. Löwe, A. Sorbi
|
| Language |
English
|
| Published at |
https://doi.org/10.1007/978-3-540-73001-9_51
|
|
Permalink to this page
|