Self-Modifying Finite Automata - Power and Limitations
John N. Shutt · 1995
The Self-Modifying Finite Automaton (SMFA) is a model of computation introduced in [RS93, RS94, RS95b]. Formal definitions appear in [RS95a]. This paper further investigates the computational power of the model, and introduces the concepts of path determinism and register complexity. Contents 1 Introduction 2 2 Preliminaries 2 3 Determinism 3 3.1 Basic criteria : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 3.2 Qualified criteria : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 3.3 Turing power : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 4 SMFAs without -transitions 15 5 Finite-order SMFAs 18 5.1 Single-addition SMFAs : : : : : : : : : : : : : : : : : : : : : : : : : : 19 5.2 Ultralinear languages : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 The pumping lemma 24 6.1 Priming the pump : : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 6.2 Single-register : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :...