Guilhem Gamard
LIS, Marseille
http://www.mlir.info/gamard/
Date(s) : 03/11/2020 iCal
11 h 00 min - 12 h 00 min
Titre : Rice-like theorems for automata networks
Résumé :
An automata network (AN for short) is a finite digraph where each node holds a state, choosen 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.
VIRTUAL EVENT: https://bbb-test.univ-amu.fr/b/sar-xmr-npe
Emplacement
Site Sud, Luminy, TPR2, Salle de Séminaire 304-306 (3ème étage)
Catégories