Going Beyond Turing with P Automata: Regular Observer ω-Languages and Partial Adult Halting
Rudolf Freund, Sergiu Ivanov and Ludwig Staiger
In this paper we investigate several variants of P automata having infinite runs on finite inputs. By imposing specific conditions on the infinite evolution of the systems, it is easy to find ways for going beyond Turing if we are watching the behavior of the systems on infinite runs. In a similar way, we can assign ω-languages as observer languages to the infinite runs of a P automaton on finite inputs. Special subclasses of regular ω-languages then, for example, characterize the red-green P automata. Moreover, we introduce a new halting variant for P automata which we call partial adult halting, with the meaning that a specific predefined part of the P automaton does not change any more from some moment on during the infinite run.
Keywords: Arithmetical hierarchy, observer languages, partial adult halting, P automata, red-green automata, ω-languages