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.

Leave a Reply