============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Intrinsic Simulations between Stochastic Cellular 
             Automata   
            
Palestrante: Nicolas Schabanel
             Centre National de la Recherche Scientifique
             
Hora e Data: 14h00, sexta-feira, 19 de outubro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

Cellular Automata (CA) are  a key tool in simulating natural
phenomena.   This is  because they  constitute  a privileged
mathematical  framework  in  which  to  cast  the  simulated
phenomena,   and   they   describe  a   massively   parallel
architecture  in  which to  implement  the simulator.  Often
however, the  system that needs  to be simulated is  a noisy
system.  More embarrassingly  even, it  may happen  that the
system  that  is  used  as  a simulator  is  again  a  noisy
system. The latter is uncommon  if one thinks of a classical
computer as the simulator,  but quite common for instance if
one  thinks  of using  a  reduced model  of  a  system as  a
simulator for that system.

Fortunately   when  both  the   simulated  system   and  the
simulating  system  are noisy,  it  could  happen that  both
effects cancel out, i.e. that  the noise of the simulator is
made  to coincide  with that  of the  simulated.  In  such a
situation a model of noise  is used to simulate another, and
the simulation may even turn out to be ... exact. This paper
attempts to give  a formal answer to the  question: When can
it be said  that a noisy system is  able to exactly simulate
another?

This article  proposes a  simple formalism for  dealing with
deterministic,  non-deterministic  and  stochastic  cellular
automata  in a  unifying and  composable manner.  Armed with
this formalism, we extend the notion of intrinsic simulation
between    deterministic   cellular    automata,    to   the
non-deterministic and  stochastic settings. We  then provide
explicit tools to prove or  disprove the existence of such a
simulation  between two  stochastic cellular  automata, even
though  the intrinsic  simulation  relation is  shown to  be
undecidable  in dimension  two  and higher.  The key  result
behind this is the caracterization of equality of stochastic
global  maps by  the  existence of  a  coupling between  the
random  sources. We  then prove  that there  is  a universal
non-deterministic  cellular   automaton,  but  no  universal
stochastic  cellular automaton.  Yet  we provide  stochastic
cellular automata achieving optimal partial universality.

Joint work with Pablo Arrighi (Univ. de Grenoble (LIG) and
ENS de Lyon (LIP), France) and Guillaume Theyssier (CNRS,
Université de Savoie (LAMA), France)