Langtons myra

Från Wikipedia
Hoppa till: navigering, sök
Tabell över myrans första 100 steg, och vad som händer efter c:a 10000 respektive 12000 steg.

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[redigera | redigera wikitext]

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:

  1. är rutan vit, måla den svart och vrid dig 90 grader till höger
  2. ä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[redigera | redigera wikitext]

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

  1. ^ Langton, Chris G. (1986). ”Studying artificial life with cellular automata”. Physica D: Nonlinear Phenomena 22: ss. 120-149. http://hdl.handle.net/2027.42/26022.