Langtons myra
Langtons myra (eng. Langton's ant) är en tvådimensionell Turingmaskin med en mycket enkel uppsättning regler, uppfunnen av den amerikanska datorvetaren Chris Langton 1986.[1] Myran visar att en mekanism med enkla regler kan leda till ett mycket komplext beteende, ett fenomen kallat emergens.
Algoritm
En myra befinner sig på ett rutnät med till en början endast vita rutor. Myran kontrollerar vilken färg rutan den för tillfället står på har, och utför följande:
- är rutan vit, måla den svart och vrid dig 90 grader till höger
- är rutan svart, måla den vit och vrid dig 90 grader till vänster
Därefter tar myran ett kliv till nästa ruta och utför ovanstående på den nya rutan, och så vidare.
De cirka 10 000 första stegen uppstår ett kaotiskt virrvarr, men plötsligt faller myran in i en loop om 104 steg, och en symmetrisk "myrväg" uppstår. Även om principerna för myran är strängt deterministiska, vore det i princip omöjligt att förutsäga detta beteende.
Animationer
- Långsam animation av myrans 200 första steg
- Snabb animation av tre olika myror på samma rutnät.
Se även
- Game of Life
Wikimedia Commons har media som rör Langtons myra.
Referenser
- ^ Langton, Chris G. (23 september 1986). ”Studying artificial life with cellular automata”. Physica D: Nonlinear Phenomena "22": ss. 120-149. http://hdl.handle.net/2027.42/26022.