Going Beyond Turing with P Automata: Regular Observer omega-Languages and Partial Adult Halting

摘要

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 omega-languages as observer languages to the infinite runs of a P automaton on finite inputs. Special subclasses of regular omega-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.