Post’s problem for ordinal register machines
| Authors |
|
|---|---|
| Publication date | 2007 |
| Host editors |
|
| Book title | Computation and Logic in the Real World |
| Book subtitle | Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007 : proceedings |
| ISBN |
|
| ISBN (electronic) |
|
| Series | Lecture Notes in Computer Science |
| Event | Third Conference of Computability in Europe CiE 2007 |
| Pages (from-to) | 358-367 |
| Publisher | Berlin: Springer |
| Organisations |
|
| Abstract | We study Post’s Problem for the ordinal register machines defined in [6], showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors the results in [3] for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time. |
| Document type | Conference contribution |
| Language | English |
| Published at |
https://doi.org/10.1007/978-3-540-73001-9_37
(Final published version)
|
| Permalink to this page | |