Oggi voglio riparlare della Formica di Langton (qui la puntata
precedente). Per il numero infinitesimo di persone che possano
trovare la cosa interessante, vi racconto la dimostrazione del teorema
di Cohen-Kong (o Kung). All'epoca non ero riuscito a trovare una dimostrazione
in rete (che in realtà c'era, ma non sempre si trovano neanche le cose
che ci sono). Grazie anche al gentile aiuto di Delio (che mi ha fatto
capire che quello che credevo un articolo era un libro), adesso sono in
possesso di "Further Travel with my Ant" di David Gale e posso
procedere (può essere che a nessuno interessi, ma questo vale per tutto
quello che scrivo).
Teorema di Cohen-Kong [la dimostrazione, secondo David Gale, è dovuto a Bunimovitch e Troubetskoy]:
La traiettoria della formica di Langton (classica) è non limitata
La prima cosa è notare che la regola
della formica è reversibile. L'insieme di celle nere e bianche, assieme
alla posizione e l'orientazione della formica determinano da dove
viene. Supponiamo (per assurdo) che la traiettoria della formica sia
limitata.
Allora, per reversibilità il cammino della formica deve essere
periodico (*), cioè la formica deve percorrere sempre la stessa
traiettoria (che eventualmente si sovrappone a se stessa anche più
volte).
E' necessario notare che (per come è fatta la regola) la formica si
muove alternativamente in maniera orizzontale e verticale, quindi le
celle possono essere divise in celle orizzontali e celle verticali come
le caselle di una scacchiera. La formica entra sempre in maniera
orizzontale in una cella orizzontale (e esce in verticale, verso l'alto
o verso il basso) e entra sempre in maniera verticale in una cella
verticale.
Prendiamo adesso in considerazione la cella più in alto fra quelle più
a destra della regione (limitata) che percorre la formica. Per
costruzione la traiettoria periodica non passa a destra e in alto a
questa cella. Supponiamo che sia una cella orizzontale (naturalmente
vale un ragionamento analogo se è una cella verticale). In tal caso la
traiettoria deve necessariamente entrare da sinistra e uscire dal basso
della cella. Cioè la cella è nera. Ma il passaggio della formica la
trasforma in una cella bianca, quindi al prossimo passaggio, entrando
da sinistra la formica uscirà dall'alto, occupando una cella che per
costruzione non è sulla traiettoria. Questo è impossibile quindi il
teorema è dimostrato.
(*) la parte contrassegnato da un asterisco è quella che mi ha causato
più problemi (sul libro non è spiegata, immagino che per un matematico
vero sia evidente). La mia dimostrazione del fatto che la reversibilità
implichi che il cammino è periodico (cosa peraltro intuitiva) non
è molto elegante. La metto qui sotto. Se qualcuno trova una
dimostrazione meno goffa la lasci nei commenti e aggiornerò il
post.
Supponiamo che la traiettoria non sia
periodica. Se la traiettoria è limitata (quindi rinchiusa da un
rettangolo M*N), esiste almeno una cella che la formica dovrà visitare
un numero K (grande a piacere) di volte. Dopo infatti K*(M*N)
passi della formica, le celle sono o tutte visitate K volte, o alcune
visitate più di K volte e altre meno.
Prendiamo una cella visitata K volte (o più). Il comportamento
della formica è determinato da M*N + 1 variabili binarie (le celle e
l'orientazione della formica). Se la formica si ripresenta nella cella
scelta con tutte le variabili nello stesso stato (per reversibilità) non può
comportarsi in maniera diversa da prima quindi la traiettoria è
periodica. Questo vuol dire che le variabili dovranno essere ogni volta
diverse. Ma basta prendere K più grande delle combinazioni possibili
delle variabili (cioè K > 2(M*N +1) ) che questo non è
possibile. La traiettoria è quindi periodica.
Ci sono altri articoli sulla formica, nel libro di Gale. Magari trovo qualcos'altro di interessante.
9:49:42 PM
|
|