Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
An Enhanced Theory of Infinite Time Register Machines

Edit abstract data

Author(s): Peter Koepke and Russell Miller
Slot: Tue, 11:00-11:20, Amphitheater B (col. 2)


Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times a register content is defined as a lim inf of previous register contents, if that limit is finite; otherwise the register is reset to 0. (A previous weaker version of infinitary register machines would halt without a result in case of such an overflow). The theory of infinite time register machines has similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. Indeed ITRMs can decide all Pi-1-1 sets, yet they are strictly weaker than ITTMs.

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