Formiga de Langton: diferència entre les revisions
m afegir categoria |
Expansió del contingut |
||
| Línia 9: | Línia 9: | ||
La formiga de Langton també es pot descriure com un [[autòmat cel·lular]], on la graella es pinta de blanc o negre i la formiga es pinta d'un de vuit colors diferents, depenent del color del quadrat al que es troba i de la direcció a la que està mirant.<ref name="Complexity"/> |
La formiga de Langton també es pot descriure com un [[autòmat cel·lular]], on la graella es pinta de blanc o negre i la formiga es pinta d'un de vuit colors diferents, depenent del color del quadrat al que es troba i de la direcció a la que està mirant.<ref name="Complexity"/> |
||
==Comportament== |
|||
Tot i la simplicitat de les normes de moviment, els comportaments de la formiga són tan complexos que han estat objecte de múltiples investigacions.<ref name="3D"/> |
|||
Començant per una graella totalment blanca, la versió clàssica presenta tres tipus de comportament aparents:<ref>{{ref-llibre |cognom=Practchett |nom=Terry |títol=The Science of Discworld |any=1999}}</ref> |
|||
* '''Simplicitat''': Durant els primers centenars de passos, la formiga crea patrons senzills i freqüentment simètrics. |
|||
* '''Caos''': Després d'aquesta primera fase apareix un patró gran i irregular. La formiga segueix un camí aparentment atzarós fins a aproximadament 10.000 passos. |
|||
* '''Ordre emergent''': Finalment la formiga comença a construir una "xemeneia", un patró [[atractor]] de 104 passos que es va repetint indefinidament. |
|||
La '''conjectura de Cohen-Kong''' estipula que independentment del patró original a la graella, sempre s'acaba arribant a la distribució necessària perquè la formiga construeixi la "xemeneia". Aquesta hipòtesi encara no ha estat demostrada ni refutada; l'únic que es coneix és que la trajectòria de la formiga no té un límit, independentment de l'estat inicial. Aquesta demostració es coneix com el '''Teorema de Bunimovitch-Troubetzkoy'''.<ref name="bounded">{{ref-publicació |autor=Bunimovich, Leonid A.|autor2=Troubetzkoy, Serge E. |títol=Recurrence properties of Lorentz lattice gas cellular automata |publicació=Journal of Statistical Physics |data=1992 |pàgines=289-302 |volum=67 |exemplar=1-2 |doi=10.1007/BF01049035}}</ref> |
|||
===Teorema de Bunimovitch-Troubetzkoy=== |
|||
[[File:Clasificacion de las celdas.png|thumb|Classificació de les cel·les de la graella segons la direcció d'entrada.]] |
|||
Els moviments de la formiga s'alternen entre verticals i horitzontals. Això permet classificar les cel·les de la graella en dos conjunts: cel·les a les que s'entra horitzontalment i es surt verticalment (cel·les H) i cel·les a les que s'entra verticalment i es surt horitzontalment (cel·les V). |
|||
Suposant que existís una formiga amb trajectòria [[Acotat|acotada]], aquesta formiga només podria visitar un nombre finit d'estats (fins a 4 direccions i 2 colors per cada cel·la en la trajectòria). Per tant, degut a que la formiga es mou infinitament, en algun moment ha de repetir un estat i a partir d'aquest moment quedarà atrapada infinitament en un cicle. A més, com que aquest cicle és de longitud finita, ha de ser acotat i per tant té "cantonades"; en particular ha de tenir cantonades inferiors-esquerres, és a dir, cel·les les quals les seves veïnes inferior i esquerra no formen part del cicle. |
|||
A l'agafar una d'aquestes cantonades és possible veure que la segona vegada que el cicle passa per ella (hi passa infinits cops) el seu color és blanc si és una cel·la H (només hi pot haver entrat per la dreta per sortir per la part superior) o negre si és una cel·la V (només hi pot haver entrat per la part superior per sortir per la dreta). Al passar per la cel·la el seu color canvia, per tant la pròxima vegada que hi passi el color serà el contrari d'abans; negre si és H i blanc si és V, lo qual és una contradicció perquè llavors la formiga aniria a una cel·la que queda fora del cicle. Aquesta contradicció permet concloure que aquest cicle no pot existir, i per tant la formiga no pot tenir una trajectòria [[Acotat|acotada]].<ref name="bounded"/> |
|||
== Universalitat == |
== Universalitat == |
||
Revisió del 19:06, 30 març 2020
En computació, la formiga de Langton és una màquina de Turing bidimensional amb un conjunt de normes molt simple, que tot i això dóna lloc a comportaments emergents complexes.[1] La formiga de Langton clàssica opera sobre una graella espacial quadrada, en la que cada cel·la pot tenir un de dos estats (blanca o negra). Va ser inventada per Chris Langton l'any 1986 i la seva universalitat va ser demostrada l'any 2000.[2] La idea ha estat generalitzada de diverses maneres, entre elles turmites que agreguen més estats, normes per afegir més colors, graelles tridimensionals[3] o finites, entre d'altres.
Versió clàssica
Cada quadrat de l'entramat es pinta de blanc o negre. S'identifica arbitràriament un quadrat com la «formiga». La formiga sempre està mirant en una de les quatre direccions cardinals i es mou un quadrat cada vegada, d'acord amb les següents normes:
- Si està sobre un quadrat blanc, canvia el color del quadrat, gira 90 graus a l'esquerra i avança un quadrat.
- Si està sobre un quadrat negre, canvia el color del quadrat, gira 90 graus a la dreta i avança un quadrat.
La formiga de Langton també es pot descriure com un autòmat cel·lular, on la graella es pinta de blanc o negre i la formiga es pinta d'un de vuit colors diferents, depenent del color del quadrat al que es troba i de la direcció a la que està mirant.[2]
Comportament
Tot i la simplicitat de les normes de moviment, els comportaments de la formiga són tan complexos que han estat objecte de múltiples investigacions.[3]
Començant per una graella totalment blanca, la versió clàssica presenta tres tipus de comportament aparents:[4]
- Simplicitat: Durant els primers centenars de passos, la formiga crea patrons senzills i freqüentment simètrics.
- Caos: Després d'aquesta primera fase apareix un patró gran i irregular. La formiga segueix un camí aparentment atzarós fins a aproximadament 10.000 passos.
- Ordre emergent: Finalment la formiga comença a construir una "xemeneia", un patró atractor de 104 passos que es va repetint indefinidament.
La conjectura de Cohen-Kong estipula que independentment del patró original a la graella, sempre s'acaba arribant a la distribució necessària perquè la formiga construeixi la "xemeneia". Aquesta hipòtesi encara no ha estat demostrada ni refutada; l'únic que es coneix és que la trajectòria de la formiga no té un límit, independentment de l'estat inicial. Aquesta demostració es coneix com el Teorema de Bunimovitch-Troubetzkoy.[5]
Teorema de Bunimovitch-Troubetzkoy
Els moviments de la formiga s'alternen entre verticals i horitzontals. Això permet classificar les cel·les de la graella en dos conjunts: cel·les a les que s'entra horitzontalment i es surt verticalment (cel·les H) i cel·les a les que s'entra verticalment i es surt horitzontalment (cel·les V).
Suposant que existís una formiga amb trajectòria acotada, aquesta formiga només podria visitar un nombre finit d'estats (fins a 4 direccions i 2 colors per cada cel·la en la trajectòria). Per tant, degut a que la formiga es mou infinitament, en algun moment ha de repetir un estat i a partir d'aquest moment quedarà atrapada infinitament en un cicle. A més, com que aquest cicle és de longitud finita, ha de ser acotat i per tant té "cantonades"; en particular ha de tenir cantonades inferiors-esquerres, és a dir, cel·les les quals les seves veïnes inferior i esquerra no formen part del cicle.
A l'agafar una d'aquestes cantonades és possible veure que la segona vegada que el cicle passa per ella (hi passa infinits cops) el seu color és blanc si és una cel·la H (només hi pot haver entrat per la dreta per sortir per la part superior) o negre si és una cel·la V (només hi pot haver entrat per la part superior per sortir per la dreta). Al passar per la cel·la el seu color canvia, per tant la pròxima vegada que hi passi el color serà el contrari d'abans; negre si és H i blanc si és V, lo qual és una contradicció perquè llavors la formiga aniria a una cel·la que queda fora del cicle. Aquesta contradicció permet concloure que aquest cicle no pot existir, i per tant la formiga no pot tenir una trajectòria acotada.[5]
Universalitat
L'ant 2000, Gajardo et al. van mostrar una construcció que calcula qualsevol circuit binari utilitzant la trajectòria d'una única formiga de Langton.[2] En termes de la teoria de la computació, i referint-se concretament en la complexitat de la computació, això vol dir que el problema de saber si la trajectòria d'una formiga de Langton clàssica passa per una determinada cel·la, és P-hard (redueix un problema P-complet, el càlcul d'un circuit binari). Per tant, seria possible simular una màquina de Turing utilitzant la trajectòria de la formiga. Això significa que la formiga, tot i tenir unes normes tan bàsiques, és capaç de realitzar computació universal, cosa que implica que hi ha problemes indecidibles sobre el comportant de la formiga de Langton clàssica.
Referències
- ↑ Langton, Chris «Studying artificial life with cellular automata». Physica D: Nonlinear Phenomena, 22, 1-3, 1986, pàg. 120-149. DOI: 10.1016/0167-2789(86)90237-X.
- ↑ 2,0 2,1 2,2 Gajardo, A.; Moreira, A.; Goles, E. «Complexity of Langton's ant». Discrete Applied Mathematics, 117, 1-3, 2002, pàg. 41-50. DOI: 10.1016/S0166-218X(00)00334-6.
- ↑ 3,0 3,1 Hamann, Heiko «Definition and Behavior of Langton’s Ant in Three Dimensions». Complex Systems, 14, 2008, pàg. 263–268.
- ↑ Practchett, Terry. The Science of Discworld, 1999.
- ↑ 5,0 5,1 Bunimovich, Leonid A.; Troubetzkoy, Serge E. «Recurrence properties of Lorentz lattice gas cellular automata». Journal of Statistical Physics, 67, 1-2, 1992, pàg. 289-302. DOI: 10.1007/BF01049035.