The complexity of quickly decidable ORM-decidable sets

  • J. D. Hamkins, D. Linetsky, and R. Miller, “The Complexity of Quickly Decidable ORM-Decidable Sets,” in Computation and Logic in the Real World – Third Conference of Computability in Europe CiE 2007, Siena, Italy, 2007, pp. 488-496.  
    @INPROCEEDINGS{HamkinsLinetskyMiller2007:ComplexityOfQuicklyDecidableORMSets,
    AUTHOR = "Joel David Hamkins and David Linetsky and Russell Miller",
    TITLE = "The Complexity of Quickly Decidable {ORM}-Decidable Sets",
    BOOKTITLE = "Computation and Logic in the Real World - Third Conference of Computability in Europe CiE 2007",
    YEAR = "2007",
    editor = "Barry Cooper and Benedikt {L\"owe} and Andrea Sorbi",
    volume = "4497",
    number = "",
    series = "Proceedings, Lecture Notes in Computer Science",
    pages = "488--496",
    address = "Siena, Italy",
    month = "",
    organization = "",
    publisher = "",
    note = "",
    abstract = "",
    keywords = "",
    doi = {10.1007/978-3-540-73001-9_51},
    ee = {http://dx.doi.org/10.1007/978-3-540-73001-9_51},
    bibsource = {DBLP, http://dblp.uni-trier.de},
    file = F
    }

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 $\omega^\omega$. Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than $\omega_1^{CK}$.

Post's Problem for Ordinal Register Machines

  • J. D. Hamkins and R. Miller, “Post’s Problem for Ordinal Register Machines,” in Computation and Logic in the Real World—Third Conference of Computability in Europe CiE 2007, Siena, Italy, 2007, pp. 358-367.  
    @INPROCEEDINGS{HamkinsMiller2007:PostsProblemForORMs,
    AUTHOR = "Joel David Hamkins and Russell Miller",
    TITLE = "Post's Problem for Ordinal Register Machines",
    BOOKTITLE = "Computation and Logic in the Real World---Third Conference of Computability in Europe CiE 2007",
    YEAR = "2007",
    editor = "Barry Cooper and Benedikt {L\"owe} and Andrea Sorbi",
    volume = "4497",
    number = "",
    series = "Proceedings, Lecture Notes in Computer Science",
    address = "Siena, Italy",
    month = "",
    organization = "",
    publisher = "",
    note = "",
    abstract = "",
    keywords = "",
    pages = {358-367},
    doi = {10.1007/978-3-540-73001-9_37},
    ee = {http://dx.doi.org/10.1007/978-3-540-73001-9_37},
    file = F
    }

We study Post’s Problem for ordinal register machines, showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors earlier results for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time.