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

[bibtex key=HamkinsMiller2009:PostsProblemForORMsExplicitApproach]

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

Your email address will not be published. Required fields are marked *