Momoblog
Il mio web log in italiano


Subscribe to "Momoblog" in Radio UserLand.

quaranta

Click to see the XML version of this web page.

Click here to send an email to the editor of this weblog.



 3/1/05
 2/28/05
 2/27/05
 2/25/05
 2/25/05
 2/22/05
 2/21/05
 2/20/05
 2/19/05
 2/18/05
 2/17/05
 2/15/05
 2/13/05
 2/12/05
 2/11/05
 2/10/05
 2/9/05
 2/8/05
 2/7/05
 2/6/05
 2/6/05
 2/4/05
 2/3/05
 2/3/05
 2/1/05
 2/1/05

miniXmlCoffeeMug.gif miniXmlButton.gif


lunedì 7 febbraio 2005
 

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      comment [] trackback []



Click here to visit the Radio UserLand website. © Copyright 2005 Massimo Morelli.
Last update: 01/03/2005; 0.11.31.site index

Febbraio 2005
Dom Lun Mar Mer Gio Ven Sab
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28          
Gen   Mar



Top 5 hits for Cohen Kong on..
Google
1.Cohen -Kung Theorem -- from MathWorld
2.Mathematical Recreations
3.phorum - Herman Cohen - RIP Actress Fay Wray (KING KONG , CRIME OF ...
4.phorum - Herman Cohen - Re: RIP Actress Fay Wray (KING KONG , CRIME ...
5.phorum - Herman Cohen - Re: RIP Actress Fay Wray (KING KONG , CRIME ...

Help link 01/03/2005; 0.04.31.