Logical Approaches to Computational Barriers

Computing the Recursive Truth Predicate on Ordinal Register Machines

Author(s): |
Peter Koepke and Ryan Siders |

Slot: |
Array, 14:50-15:10, col. 3 |

Ordinal Register Machines increment and erase a finite number of registers containing ordinals; the number of necessary registers can eventually be reduced to four. They exemplify abstract model-theoretic computation. The ordinals they store can refer to the timesteps of a hyper-computation. We prove that the classes of sets computable from ordinal parameters by infinite-time ordinal-storing register machines and infinite-time ordinal-tape Turing machines (presented at CIE 2005 by our first author) agree. Infinitary Turing machines' states (assuming the machine began with constructible input) are always constructible sets of ordinals. A single ordinal can code the ordinal parameters and the construction. We show that register machines can manipulate such codes. We focus on algorithmic properties of ordinal register machines, describing their data types, varying the number of registers, describing their well-founded programming, and computing run-time complexities: solving the truth predicate is ordinal-exponential time on a register machine, and ordinal-polynomial time on a Turing machine.

websites: Arnold Beckmann | 2006-04-19 |