Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Clockable Ordinals for Infinite Time Register Machines

Edit abstract data

Speaker: Miriam Nasfi
Author(s): Tim Fischbach, Peter Koepke, Miriam Nasfi and Gregor Weckbecker
Slot: Tue, 11:20-11:40, Amphitheater B (col. 2)


We do ordinal computability with the Infinite Time Register Machine
(ITRM) model of Miller and Koepke (Koepke, P., Miller, R.: An
enhanced theory of infinite time register machines. Logic and Theory
of Algorithms, Fourth Conference on Computability in Europe, CiE 2008,
Athens, Greece, June 2008, Proceedings, Lecture Notes in Computer
Science, volume 5028).

In analogy with the theory of Infinite Time Turing Machines (ITTM)
(Hamkins, J.D., Lewis, A.: Infinite time Turing machines. J. Symbolic
Logic 65(2),(2000), 567-604) we introduce a notion of ITRM-clockable
ordinal corresponding to the running time of some computation. In
contrast to the ITTM situation there are no gaps in the
ITRM-clockable ordinals:

Theorem: $CLOCK := \{ \alpha | \alpha ITRM-clockable \}$ is a transitive
initial segment of the ordinals and is properly contained in the
ITTM-clockable ordinals.

The proof involves a finite speed-up lemma and a simple halting
criterion for ITRMs: A program halts iff every machine configuration
occurs less than $\omega^\omega$ times in the corresponding
computation. We further derive some closure properties of
$CLOCK$ as well as:

Theorem: The class of ITRM-clockable ordinals coincides with the
class of ITRM-computable ordinals.

websites: Arnold Beckmann 2008-05-28 Valid HTML 4.01! Valid CSS!