Rice-like theorems for automata networks

1 février 2021

Guilhem Gamard (laboratoire d’Informatique et Systèmes, Aix-Marseille)

An automata network (AN for short) is a finite digraph where each node holds a state, chosen among a finite set,
that evolves in function of the states of its inbound neighbors.
Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in an cellular automaton.
In other terms, the differences between a cellular automaton and an automata network is that the
« grid » is an arbitrary finite digraph, and that different nodes may have different update functions.
ANs have been used to model neural networks, dynamics of expression and inhibition of genes,
distributed algorithms, and more.

Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory.
Still, they are subject to some kind of « Rice theorems », i.e., results along the lines of:
« any nontrivial property of the function computed by an automata network is computationally hard to test ».
In this talk, we will review several results that fit this pattern,
as well as pieces of proof that hopefully may be reused in other contexts.