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.

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.

Post's problem for supertasks has both positive and negative solutions

  • J. D. Hamkins and A. Lewis, “Post’s problem for supertasks has both positive and negative solutions,” Arch.~Math.~Logic, vol. 41, iss. 6, pp. 507-523, 2002.  
    @article{HamkinsLewis2002:PostProblem,
    AUTHOR = {Hamkins, Joel David and Lewis, Andrew},
    TITLE = {Post's problem for supertasks has both positive and negative solutions},
    JOURNAL = {Arch.~Math.~Logic},
    FJOURNAL = {Archive for Mathematical Logic},
    VOLUME = {41},
    YEAR = {2002},
    NUMBER = {6},
    PAGES = {507--523},
    ISSN = {0933-5846},
    CODEN = {AMLOEH},
    MRCLASS = {03D10 (68Q05)},
    MRNUMBER = {1923194 (2003f:03052)},
    MRREVIEWER = {Robert M.~Baer},
    DOI = {10.1007/s001530100112},
    URL = {http://dx.doi.org/10.1007/s001530100112},
    eprint = {math/9808128},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Recently we have introduced a new model of infinite computation by extending the operation of ordinary Turing machines into transfinite ordinal time. In this paper we will show that the infinite time Turing machine analogue of Post’s problem, the question whether there are supertask degrees between $0$ and the supertask jump $0^\triangledown$, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between $0$ and $0^\triangledown$, but in the context of sets of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to oracles.