The power of writing, a pebble hierarchy and a narrative for the teaching of Automata Theory

Abstract

In this work we study pebble automata. Those automata constitute an infinite hierarchy of discrete models of computation. The hierarchy begins at the level of finite state automata (0-pebble automata) and approaches the model of onetape Turing machines. Thus, it can be argued that it is a complete hierarchy that covers, in a continuous way, all the models of automata that are important in the theory of computation. We investigate the use of this hierarchy as a narrative for the teaching of automata theory. We also investigate some fundamental questions concerning the power of pebble automata.