# 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–-CiE 2007, Siena, Italy, 2007, pp. 358-367.
[Bibtex]
@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---CiE 2007}",
YEAR = "2007",
editor = "B. Cooper and B. Löwe and A.~Sorbi",
volume = "4497",
number = "",
series = "Proc. LNCS",
month = "",
organization = "",
publisher = "",
note = "",
abstract = "",
keywords = "",
pages = {358-367},
doi = {10.1007/978-3-540-73001-9_37},
ee = {},
file = F,
url = {http://wp.me/p5M0LV-39},
}

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.