Aspetti algebrici, analitici e logico-informatici della teoria degli automi cellulari sui gruppi.

Speaker:  Tullio Ceccherini Silberstein - Università del Sannio
  Thursday, September 25, 2014 at 3:00 PM 14:45 rinfresco; 15:00 inizio seminario

 

Gli automi cellulari sono stati introdotti da J.von Neumann 

nella prima meta' del secolo scorso per modellizzare macchine
auto-replicantisi. In poche parole, un AUTOMA CELLULARE (su Z^2 con
alfabeto un insieme finito A) e' una applicazione continua
t : A^(Z^2) ---> A^(Z^2) che commuta con l'azione naturale di Z^2 su
A^(Z^2) dotato della topologia prodiscreta.
Negli anni '60 il celebre Teorema del Giardino dell'Eden (dovuto a
E.F.Moore e J.Myhill) dava una caratterizzazione della suriettivita' degli
automi cellulari su Z^2. Il risultato e' stato esteso agli automi
cellulari t : A^G ---> A^G con G un gruppo AMENABILE (un'altra nozione
introdotta da von Neumann nello studio del paradosso di Banach-Tarski: G
e' amenabile se ammette una misura di probabilita' finitamente additiva invariante per
l'azione di G su se stesso) da TCS, A.Machi e F.Scarabotti nel 1997.
Un conseguenza del Teorema del Giardino dell'Eden per gruppi amenabili
e' che i gruppi amenabili sono SURGIUNTIVI (una nozione dovuta a W.
Gottschalk in teoria ergodica e dinamica topologica: G e' surgiuntivo
se ogni automa cellulare  t : A^G ---> A^G iniettivo e' suriettivo).
Tale risultato e' stato generalizzato da M.Gromov e B.Weiss alla classe
dei gruppi SOFICI (che comprende i gruppi amenabili e residualmente
finiti) nel 1999. La versione "lineare" del teorema di Giardino dell'Eden
e del Teorema di surgiuntivita' e' stata dimostrata da TCS e M.Coornaert
nel 2006-7 e come corollario si deduce una nuova dimostrazione della
congettura di Kaplansky sulla STABILITA' FINITA delle algebre di gruppi
(dato un gruppo G ed un campo K, l'algebra di gruppo K[G] e' detta
stabilmente finita se, per ogni naturale n, date due matrici n per n A e B
a coefficienti in K[G] tali che AB = I, si ha necessariamente BA = I)
per i gruppi sofici.
Da un punto di vista logico, ci si puo' chiedere se sia DECIDIBILE il
problema della suriettivita' (o della iniettivita') di un automa cellulare
t : A^G ---> A^G. Amoroso e Patt nel 1970 hanno dimnostrao che per G = Z
il problema e' decidibile. J.Kari nel 1990 ha dimostrato che per G = Z^d
con d =2,3,... NON e' decidibile. Recentemente, M.Morgenstern ha
dimostrato che per G = S_g (il gruppo fondamentale di una superficie
compatta orientabile di genere g=2,3,...) NON e' decidibile.
Segue invece dalla teoria sui context-free groups/graphs di D.Muller e
P.Schupp che se G e' virtualmente libero (cioe' ammette un sottogruppo
libero di indice finito) il problema e' decidibile. TCS, Coornaert,
F.Fiorenzi e Z.Sunic hanno recentement (2013) esibito un esplicito
algoritmo per la suriettivita' per G = F_d (il gruppo libero di rango
d=1,2,3,...) basato sulla nozione di Automi di Rabin.

 


Programme Director
Giandomenico Orlandi

External reference
Publication date
September 10, 2014

Studying

Share