Abstract:
Finite automata have been recently used as alternative, discrete models in theoretical physics,
especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/
extrinsic perception (see, for instance [15, 18, 16, 7, 17, 4]). These studies deal with Moore
experiments; the main result states that it is impossible to determine the initial state of an automaton,
and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For
this aim the classical theory of finite automata{which considers automata with initial states{is not
adequate, and a new approach is necessary. A study of finite deterministic automata without initial
states is exactly the aim of this paper. We will define and investigate the complexity of various types
of simulations between automata. Minimal automata will be constructed and proven to be unique
up to an isomorphism. We will build our results on an extension of Myhill-Nerode technique; all
constructions will make use of “automata responses" to simple experiments only, i.e., no information
about the internal machinery will be considered available.