Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
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