How to Go Beyond Turing with P Automata: Time Travels, Regular Observer !-Languages, and Partial Adult Halting

Abstract

In this paper we investigate several variants of P automata having in nite runs on nite inputs. By imposing speci c conditions on the in nite evolution of the systems, it is easy to nd ways for going beyond Turing if we are watching the behavior of the systems on in nite runs. As speci c variants we introduce a new halting variant for P automata which we call partial adult halting with the meaning that a speci c prede ned part of the P automaton does not change any more from some moment on during the in nite run. In a more general way, we can assign !-languages as observer languages to the in nite runs of a P automaton. Speci c variants of regular !-languages then, for example, characterize the red-green P automata.