Langtons myre er en 2D cellulær automat med meget enkle regler opfundet af Chris Langton [1] . Myren kan også betragtes som en 2-symbol, 4-stats 2D Turing-maskine [2] .
Overvej et uendeligt plan opdelt i celler, farvet på en eller anden måde i sort og hvid. Lad der være en "myre" i en af cellerne, som ved hvert trin kan bevæge sig i en af fire retninger til cellen, der støder op til siden. Myren bevæger sig efter følgende regler [1] [3] :
Disse enkle regler forårsager ret kompleks adfærd: efter en periode med ret tilfældig bevægelse, ser myren ud til at begynde at bygge en 104-trins vej, der gentages i det uendelige, uanset feltets indledende farve. Dette tyder på, at "pivot"-adfærden er en stabil tiltrækning af Langtons myre [1] . Er "motorvejen" den eneste tiltrækkende, når myren bevæger sig? [fire]
Langtons myre kan også beskrives som en cellulær automat , hvor næsten hele feltet er farvet sort og hvid, og cellen med "myren" har en af otte forskellige farver, der henholdsvis koder for alle mulige kombinationer af sort/hvid farve af cellen og myrens bevægelsesretning.
Der er en simpel udvidelse af Langtons myre, der bruger mere end to cellefarver. Farver ændrer sig cyklisk. Der er også en simpel navneform for sådanne myrer: bogstavet L eller R ( L og R ) bruges for hver efterfølgende farve, afhængigt af om myren drejer til højre eller venstre. Langtons myre er således RLs myre .
Nogle af disse generaliserede Langtons myrer tegner mønstre, der bliver mere og mere symmetriske . Et enkelt eksempel er RLLR- myren . En tilstrækkelig betingelse for dette er, at myrens navn, betragtet som en cyklisk liste, består af på hinanden følgende par af gentagne bogstaver LL eller RR (en cyklisk liste betyder, at det sidste bogstav kan parres med det første).
Bogstavet N er også tilføjet, hvilket betyder, at myren ikke vil vende sig om og bare gå frem.
RLR: Kaotisk vækst
LLRR: Symmetrisk vækst
LRRRRRLLR: Fylder rummet i en firkant omkring sig selv
LLRRRLRLRLLR: Skaber en snoet motorvej
RRLLRLLLRRR
L2NNL1L2L1: Sekskantet felt , ringvækst
L1L2NUL2L1R2: Sekskantet felt, spiralvækst
R1R2NUR2R1L2: Animation
LN: Horisontal vækst
Der er 6 forskellige drejninger på det sekskantede felt, som her er betegnet som N (ingen ændring), R1 (60° med uret), R2 (120° med uret), U (180°), L2 (120° mod uret), L1 ( 60° mod uret).
spiral vækst
Semi-kaotisk vækst
| Conways Game of Life og andre cellulære automater | |||||
|---|---|---|---|---|---|
| Konfigurationsklasser | |||||
| Konfigurationer |
| ||||
| Vilkår | |||||
| Andre rumfartøjer på et todimensionelt gitter |
| ||||
| Et-dimensionelt rumfartøj | |||||
| Software og algoritmer |
| ||||
| KA-forskere | |||||