The basic theory of infinite time register machines |
| |
Authors: | Merlin Carl Tim Fischbach Peter Koepke Russell Miller Miriam Nasfi Gregor Weckbecker |
| |
Institution: | 1. Mathematisches Institut, Universit?t Bonn, Bonn, Germany 2. Queens College and The Graduate Center, City University of New York, New York, NY, USA
|
| |
Abstract: | 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 register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}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 register contents are defined by appropriate
limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic
and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous
register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several
similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all P11{\Pi^1_1} sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore
we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n ? r{n \in r} with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not
reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond
much better to ITTMs we hold that in future the resetting register machines should be called ITRMs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|