The hierarchy of equivalence relations on the natural numbers under computable reducibility

  • S. Coskey, J. D. Hamkins, and R. Miller, “The hierarchy of equivalence relations on the natural numbers under computable reducibility,” Computability, vol. 1, iss. 1, pp. 15-38, 2012.  
    @ARTICLE{CoskeyHamkinsMiller2012:HierarchyOfEquivalenceRelationsOnN,
    AUTHOR = {Samuel Coskey and Joel David Hamkins and Russell Miller},
    TITLE = {The hierarchy of equivalence relations on the natural numbers under computable reducibility},
    JOURNAL = {Computability},
    YEAR = {2012},
    volume = {1},
    number = {1},
    pages = {15--38},
    month = {},
    note = {},
    url = {http://iospress.metapress.com/content/96X98U84V504G456},
    eprint = {1109.3375},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    doi = {10.3233/COM-2012-004},
    abstract = {},
    keywords = {},
    source = {},
    }

We define and elaborate upon the notion of computable reducibility between equivalence relations on the natural numbers, providing a natural computable analogue of Borel reducibility, and investigate the hierarchy to which it gives rise. The theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain.

See Sam’s post on this article

Post's problem for ordinal register machines: an explicit approach

  • J. D. Hamkins and R. G. Miller, “Post’s problem for ordinal register machines: an explicit approach,” Ann.~Pure Appl.~Logic, vol. 160, iss. 3, pp. 302-309, 2009.  
    @ARTICLE{HamkinsMiller2009:PostsProblemForORMsExplicitApproach,
    AUTHOR = {Hamkins, Joel David and Miller, Russell G.},
    TITLE = {Post's problem for ordinal register machines: an explicit approach},
    JOURNAL = {Ann.~Pure Appl.~Logic},
    FJOURNAL = {Annals of Pure and Applied Logic},
    VOLUME = {160},
    YEAR = {2009},
    NUMBER = {3},
    PAGES = {302--309},
    ISSN = {0168-0072},
    CODEN = {APALD7},
    MRCLASS = {03D60 (03D10)},
    MRNUMBER = {2555781 (2010m:03086)},
    MRREVIEWER = {Robert S.~Lubarsky},
    DOI = {10.1016/j.apal.2009.01.004},
    URL = {http://dx.doi.org/10.1016/j.apal.2009.01.004},
    file = F
    }

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

Infinite time computable model theory

  • J. D. Hamkins, R. Miller, D. Seabold, and S. Warner, “Infinite time computable model theory,” in New Computational Paradigms: Changing Conceptions of What is Computable, S. B. \. Cooper, B. Löwe, and A. Sorbi, Eds., New York: Springer, 2008, pp. 521-557.  
    @INCOLLECTION{HamkinsMillerSeaboldWarner2007:InfiniteTimeComputableModelTheory,
    AUTHOR = {Hamkins, Joel David and Miller, Russell and Seabold, Daniel
    and Warner, Steve},
    TITLE = {Infinite time computable model theory},
    BOOKTITLE = "New Computational Paradigms: Changing Conceptions of What is Computable",
    PAGES = {521--557},
    PUBLISHER = {Springer},
    ADDRESS = {New York},
    YEAR = {2008},
    MRCLASS = {03C57 (03D10)},
    MRNUMBER = {2762096},
    editor = {S.B.\ Cooper and Benedikt L\"owe and Andrea Sorbi},
    isbn = "0-387-36033-6",
    file = F
    }

We introduce infinite time computable model theory, the computable model theory arising with infinite time Turing machines,  which provide infinitary notions of computability for structures built on the reals  $\mathbb{R}$. Much of the finite time theory generalizes to the infinite time context, but several fundamental questions, including the infinite time  computable analogue of the Completeness Theorem, turn out to be  independent of ZFC.

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.