Complete Simulation of Automata Networks

Abstract

Consider a finite set $A$ and an integer $n\ge 1$. This paper studies the concept of complete simulation in the context of semigroups of transformations of $A^n$, also known as finite state-homogeneous automata networks. For $m\ge n$, a transformation of $A^m$ is \emph{$n$-complete of size $m$} if it may simulate every transformation of $A^n$ by updating one coordinate (or register) at a time. Using tools from memoryless computation, it is established that there is no $n$-complete transformation of size $n$, but there is such a transformation of size $n+1$. By studying the the time of simulation of various $n$-complete transformations, it is conjectured that the maximal time of simulation of any $n$-complete transformation is at least $2n$. A transformation of $A^m$ is \emph{sequentially $n$-complete of size $m$} if it may sequentially simulate every finite sequence of transformations of $A^n$; in this case, minimal examples and bounds for the size and time of simulation are determined. It is also shown that there is no $n$-complete transformation that updates all the registers in parallel, but that there exists a sequentally $n$-complete transformation that updates all but one register in parallel. This illustrates the strengths and weaknesses of parallel models of computation, such as cellular automata.

arXiv commentVastly updated version of the paper previously known as "Universal simulation of automata networks." Florian Bridoux has joined the paper, thanks to his significant contribution