Sistemi Discreti con
Dinamica Indecidibile
Marco Giunti
Università di Cagliari
[email protected]
http://edu.supereva.it/giuntihome.dadacasa
Sommario
 Per molti sistemi discreti, dato uno stato iniziale
arbitrario, non sarebbe possibile determinarne il
comportamento dinamico a lungo termine
(Wolfram 1984a, 2002);
 farò vedere come si possa render conto in modo
rigoroso dell'intuizione di Wolfram, fondandomi su
un risultato molto generale che classifica i diversi
tipi possibili di dinamica di un sistema discreto
(Giunti 2005).
Un Automa Cellulare Finito
Dodici celle disposte in circolo. Ciascuna
cella può assumere i valori 0 o 1. Quindi,
l’AC ha 212 = 4096 stati possibili.
Regola
111
110
101
100
011
010
001
000
0
1
0
1
1
0
1
0
Numero della regola
010110102 = 9010
Tempo 0
0
1 0
0
1 0
1 0
1
1 1
1
Tempo 1
0
0 1
1
0 0
0 0
1
0 0
1
Costituenti dello spazio degli stati dell’AC regola
90 (con 12 celle disposte in circolo)
64 stati – 60 copie
32 stati – 6 copie
16 stati – 4 copie
Totale: 4096 = 212 stati
I primi studi di Wolfram sugli AC

Negli anni ’80 Wolfram (1983a) studiò sistematicamente i
256 AC più semplici (modimensionali, con 2 valori, e
intorno di raggio 1);

li classificò secondo 4 tipi di comportamento
qualitativamente simile (Wolfram 1983b, 1984b) e cioè:

AC la cui evoluzione porta a
1. uno stato omogeneo;
2. un insieme di strutture separate semplici, stabili o
periodiche;
3. un andamento caotico;
4. strutture localizzate complesse, spesso di lunga
durata.
Le ipotesi di Wolfram
 Wolfram ipotizzò che i sistemi di tipo 4 fossero
computazionalmente universali (1984b, 31);
 egli ha poi dimostrato (2002, 675-689) che la regola 110 (di
tipo 4, monodimensionale, 2 valori, raggio 1) è universale;
 infine, sulla base di studi estensivi della dinamica di molti
tipi di sistemi discreti, Wolfram è arrivato a formulare il
seguente principio estremamente generale:
 Principio di Equivalenza Computazionale (PEC)
Quasi tutti i processi che non sono ovviamente semplici
possono essere visti come computazioni di
sofisticazione equivalente (2002, 716-717)
Il significato dell’ipotesi dell’universalità
 Per quanto riguarda l’ipotesi dell’universalità dei
sistemi di tipo 4, essa significa che un tale sistema
è capace di emulare, cioè riprodurre esattamente,
il comportamento di tutta una classe di sistemi che
si sa essere computazionalmente universale;
 per es., la dimostrazione dell’universalità della
regola 110 fa vedere che, con opportune
condizioni iniziali, essa può emulare un qualsiasi
tag system (la classe dei tag system è universale
perché ogni macchina di Turing può a sua volta
essere emulata da un opportuno tag system).
Un esempio di emulazione fra due AC

AC 18 emula AC 90, in due passi, con condizioni
iniziali 00 per 0 e 01 per 1 (Wolfram 1983b, 20)
111
110
101
100
011
010
001
000
0
0
0
1
0
0
1
0
Numero della regola
000100102 = 1810
010101 010100 010001 010000 000101 000100 000001
000000
0000
0001
0101
0100
0100
0101
0001
0000
00
01
00
01
01
00
01
00
111
110
101
100
011
010
001
000
0
1
0
1
1
0
1
0
Numero della regola
010110102 = 9010
Conseguenze del Principio di
Equivalenza Computazionale (PEC)
 Ubiquità dell’universalità computazionale
– “Quasi ogni sistema il cui comportamento non sia
ovviamente semplice deve essere capace di
raggiungere lo stesso livello di sofisticazione
computazionale, e quindi deve in effetti essere
universale.” (Wolfram 2002, 718)
– A rigore, però, questo non segue dalla formulazione
precedente del principio. E’ piuttosto una diversa
formulazione del principio stesso.
 Ubiquità della complessità
– In base al PEC, “gli osservatori tendono ad essere
computazionalmente equivalenti ai sistemi che essi
osservano, con l’inevitabile conseguenza che essi
considereranno complessi quei sistemi.” (Wolfram 2002,
737)
Altre conseguenze del Principio di
Equivalenza Computazionale (PEC)
 Irriducibilità computazionale
– In base al PEC, “non ci possiamo aspettare che i
sistemi che usiamo per fare predizioni possano fare
computazioni più sofisticate delle computazioni che si
trovano in molti dei sistemi di cui cerchiamo di predire il
comportamento. E da ciò segue che per molti sistemi
non si può fare alcuna predizione sistematica, così che
non c’è alcun modo di cortocircuitare il loro processo di
evoluzione, e di conseguenza il loro comportamento
deve essere considerato computazionalmente
irriducibile.” (Wolfram 2002, 741)
 Libero arbitrio (segue dall’irriducibilità computazionale)
– “E quindi, in conclusione, che cosa ci fa pensare che ci
sia libertà in ciò che un sistema fa? In pratica, il criterio
principale sembra essere che non possiamo predire con
facilità il comportamento del sistema.” (Wolfram 2002,
751)
Ultima conseguenza del Principio di
Equivalenza Computazionale (PEC)
 Indecidibilità dinamica (segue
dall’irriducibilità computazionale)
– “E ciò che sospetto è che, per quasi tutti i
sistemi il cui comportamento ci sembra
complesso, quasi tutte le domande nontriviali che riguardano ciò che il sistema
farà in un numero infinito di passi saranno
indecidibili.” (Wolfram 2002, 755)
Un Sistema Dinamico (DS) è un modello
matematico che esprime l’idea di un sistema
deterministico arbitrario (discreto/continuo,
revers./irrevers.)

Un Sistema Dinamico (DS) è un modello (M, (gt)tT)
tale che:
1. l’insieme M non è vuoto; M è detto lo spazio degli
stati del sistema;
2. l’insieme T è Z, Z+ (interi), oppure R, R+ (reali); T è
detto l’insieme tempo;
3. (gt)tT è una famiglia di funzioni da M a M; ciascuna
funzione gt è detta una transizione di stato o un tavanzamento del sistema;
4. per ogni t e w T, per ogni x M,
a. g0(x) = x;
b. gt+w(x) = gw(gt(x)).
Significato intuitivo della definizione
di sistema dinamico
gt
x
gt(x)
t
t0
t0+t
g0
gt+w
x
x
gt
gw
Emulazione fra due DS – Intuizione
ed esempi
 Intuitivamente, un DS emula un secondo
DS quando il primo riproduce
esattamente tutta la dinamica del
secondo.
 Esempi – (i) una macchina di Turing
universale emula tutte le MT; (ii) per ogni
MT c’è un AC che emula MT e viceversa;
(iii) si ha emulazione fra i due semplici
AC considerati prima (AC 18 emula AC
90).
Emulazione fra due DS – Definizione
(Giunti 1997 equivalente a questa)
DS1 = (M, (gt)tT) emula DS2 = (N, (hv)vV) sse:
esiste D M , esiste u: D  N, biiettiva, tale che
1. per ogni a, b  D, per
ogni t  T+, c’è v  V+
tale che, se gt(a) = b,
allora hv(u(a)) = u(b);
M
N
D
b
M
u-1
hv
u
N
D
u
gt
a
2. per ogni c, d  N, per
ogni v  V+, c’è t  T+
tale che, se hv(c) = d,
allora gt(u1(c)) = u1(d).
gt
d
hv
u-1
c
Due definizioni importanti
 Un costituente di un sistema dinamico DS =
(M, (gt)tT) è un sottosistema di DS il cui
spazio degli stati N  M è temporalmente
connesso e contiene tutto il suo passato
(nonché il suo futuro).
 Un sistema dinamico è indecomponibile sse
ha un solo costituente (cioè, sé stesso).
Due risultati generali (Giunti 2005)
Teorema di decomposizione (per sistemi dinamici
in generale)
Ogni sistema dinamico è identico alla composizione di
tutti i suoi costituenti.
Teorema di classificazione (per sistemi discreti
indecomponibili)
Il grafo dello spazio degli stati di un qualunque sistema
dinamico discreto indecomponibile è di una delle
seguenti forme (i) – (vii). In particolare, (i) e (ii) sono le
possibili forme generali del grafo di un sistema
reversibile; (iii) e (iv) quelle di un sistema logicamente
reversibile; (v), (vi) e (vii) di un sistema logicamente
irreversibile.
Sistemi Reversibili
Finiti
Infiniti
(ii) Sistemi Aperiodici Non-confluenti – una linea biorientata, infinita in ambedue i sensi
(i) Sistemi Periodici – un ciclo biorientato
di n nodi (n ≥ 1)
Sistemi Logicamente Reversibili
Finiti
(iii) Sistemi periodici – un ciclo orientato
di n nodi (n ≥ 1)
Infiniti
(iv) Sistemi Aperiodici Non-confluenti – una linea
orientata, infinita in uno solo o in ambedue i
sensi
Sistemi Logicamente Irreversibili (Finiti o Infiniti)
(v) Sistemi Eventualmente Periodic Non-confluenti –
un ciclo orientato a cui si attacca una
semplice linea possibilmente infinita
Sistemi Logicamente Irreversibili (Finiti o Infiniti)
(vi) Sistemi Eventualmente Periodici Confluenti –
un ciclo orientato a cui si attaccano le
radici di un numero finito di alberi
possibilmente infiniti (sia in altezza che
in ramificazione); o al ciclo si attaccano
almeno due alberi, oppure l’unico
albero ad esso attaccato ha diverse
diramazioni (cioè, non è una semplice
linea)
Sistemi Logicamente Irreversibili (Infiniti)
(vii) Sistemi Aperiodici Confluenti – una linea orientata infinita in uno
solo o in ambedue i sensi, a cui si attaccano le radici di un
numero possibilmente infinito di alberi possibilmente infiniti
(sia in altezza che in ramificazione)
Ancora una definizione
 Due stati x e y sono dinamicamente
equivalenti sse esiste t ≥ 0 tale che, per ogni
v ≥ t, gv(x) = gv(y).
 Ovviamente, due stati sono dinamicamente
equivalenti sse essi appartengono allo
stesso costituente.
Quando possiamo dire che il comportamento
dinamico a lungo termine di un sistema
discreto è decidibile?
 Le due seguenti condizioni sono ambedue
necessarie (e forse anche congiuntamente
sufficienti):
1. dati due stati qualunque x e y, esiste una
procedura meccanica che decide se x e y
sono o non sono dinamicamente
equivalenti;
2. dato un qualunque stato x, esiste una
procedura meccanica che stabilisce la
forma generale (i)-(vii) del costituente a cui
x appartiene.
La condizione 2 fallisce per tutti i
sistemi universali
 Sappiamo che, se DS è universale, il suo
problema della fermata è indecidibile, e cioè: non
esiste una procedura meccanica che decide, per
uno stato x arbitrario, se l’orbita di x è o non è
(eventualmente) periodica con periodo 1;
 ma è facile vedere che, se la condizione 2 è
soddisfatta, il problema della fermata di DS è
decidibile;
 ne segue che, per un sistema universale
qualunque, la condizione 2 è falsa, e cioè: non
abbiamo una procedura meccanica che ci
permette di stabilire la forma generale del
costituente di un suo stato arbitrario.
Conclusione: l’indecidibilità
dinamica nei sistemi discreti
 C’è dunque un senso ben preciso in cui la
dinamica di un sistema universale può
essere detta indecidibile (e cioè, il fallimento
della condizione 2);
 se l’ipotesi di Wolfram sull’ubiquità
dell’universalità computazionale risultasse
vera, allora la dinamica di quasi tutti i
sistemi il cui comportamento non sia
ovviamente semplice risulterebbe
indecidibile esattamente in questo senso.
E’ tutto
Grazie
Indicazioni bibliografiche
Giunti, Marco (1996), “Beyond Computationalism”, in Garrison W. Cottrel (ed.), Proceedings
of the 18th Annual Conference of the Cognitive Science Society. Mahwah, NJ: L.
Erlbaum Associates, 71-75.
——— (1997), Computation, Dynamics, and Cognition. New York: Oxford University Press.
——— (1998), “Is Computationalism the Hard Core of Cognitive Science?”, in Vito M. Abrusci,
Carlo Cellucci, Roberto Cordeschi, and Vincenzo Fano (eds.), Prospettive della logica
e della filosofia della scienza: Atti del convegno triennale della Società Italiana di
Logica e Filosofia delle Scienze, Roma, 3-5 gennaio 1996. Pisa: Edizioni ETS, 255267.
——— (2004), “Is Being Computational an Intrinsic Property of a Dynamical System?”,
forthcoming in Gianfranco Minati, and Eliano Pessa (eds.), Proceedings of the Third
National Conference on Systems Science (A.I.R.S.). New York: Kluwer
Academic/Plenum Publishers. URL =
<http://edu.supereva.it/giuntihome.dadacasa/download/papers/intcom-trentosubmitted1bis.doc>
——— (2005) “Toward a Theory of Intrinsic Computability”, draft. URL =
<http://edu.supereva.it/giuntihome.dadacasa/download/papers/intcom1.3.doc>
Wolfram, Stephen (1983a), “Statistical Mechanics of Cellular Automata”, Reviews of Modern
Physics 55, 3:601-644.
——— (1983b), “Cellular Automata”, Los Alamos Science 9:2-21.
——— (1984a), “Computer Software in Science and Mathematics”, Scientific American
56:188-203.
——— (1984b), “Universality and Complexity in Cellular Automata”, in Doyne Farmer,
Tommaso Toffoli, and Stephen Wolfram (eds.), Cellular Automata. Amsterdam:
North Holland Publishing Company, 1-35.
——— (2002), A New Kind of Science. Champaign, IL: Wolfram Media, Inc.