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

Relatore
Tullio Ceccherini Silberstein - Università del Sannio
Data e ora
giovedì 25 settembre 2014 alle ore 15.00 - 14:45 rinfresco; 15:00 inizio seminario
Referente
Giandomenico Orlandi
Referente esterno
Data pubblicazione
10 settembre 2014
Dipartimento
Informatica  

Riassunto

 

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.

 






© 2002 - 2021  Universit√† degli studi di Verona
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234