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. Myran visar att en mekanism med enkla regler kan leda till ett mycket komplext beteende, ett fenomen kallat emergens.

Tabell över myrans första 100 steg, och vad som händer efter c:a 10000 respektive 12000 steg.

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:

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

• 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.
  Bilder & media