DETERMINISTIC AUTOMATA - SIMULATION, UNIVERSALITY AND MINIMALITY

Finite automata have been recently used as alternative, discrete model s in theoretical physics, especially in problems related to the dichot omy between endophysical/intrinsic and exophysical/ extrinsic percepti on (see, for instance [3, 6, 18-21]). These studies deal with Moore ex periments; the main result states that it is impossible to determine t he initial state of an automaton, and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For this aim the classic al theory of finite automata - which considers automata with initial s tates - is not adequate, and a new approach is necessary. A study. of finite deterministic automata without initial states is exactly the ai m of this paper. We will define and investigate the complexity of vari ous types of simulations between automata. Minimal automata will be co nstructed and proven to be unique up to an isomorphism. We will build our results on an extension of Myhill-Nerode technique; all constructi ons will make use of ''automata responses'' to simple experiments only , i.e., no information about the internal machinery will be considered available.