Turmite
Inom datavetenskap är en turmite en Turing-maskin som har en orientering förutom ett aktuellt tillstånd och ett "band" som består av ett oändligt tvådimensionellt rutnät av celler. Termerna myra och vant används också. Langtons myra är en välkänd typ av turmite som definieras på cellerna i ett kvadratiskt rutnät. Patersons maskar är en typ av turmite som definieras på kanterna av ett isometriskt rutnät .
Det har visat sig att turmiter i allmänhet är exakt likvärdiga i kraft med endimensionella Turing-maskiner med en oändlig tejp, eftersom båda kan simulera den andra.
Historia
Langtons myror uppfanns 1986 och förklarades "likvärdiga med Turing-maskiner". Självständigt, 1988, övervägde Allen H. Brady idén med tvådimensionella Turing-maskiner med en orientering och kallade dem "TurNing-maskiner".
Tydligen oberoende av båda dessa undersökte Greg Turk samma typ av system och skrev till AK Dewdney om dem. AK Dewdney döpte dem till "tur-mites" i sin kolumn "Computer Recreations" i Scientific American 1989. Rudy Rucker berättar historien på följande sätt:
Dewdney rapporterar att han, för att hitta ett namn på Turks varelser, tänkte, "Ja, de är Turing-maskiner som studerats av Turk, så de borde vara tur-något. Och de är som små insekter eller kvalster, så jag" Jag ska kalla dem turkvalster! Och det låter som termiter!" Med Turks och Dewdneys vänliga tillåtelse, tänker jag utelämna bindestrecket och kalla dem turmites.
— Rudy Rucker, Artificiellt Liv Lab
Relativ vs absoluta turmites
Turmiter kan kategoriseras som antingen relativa eller absoluta . Relativa turmiter, alternativt kända som "svarvmaskiner", har en inre orientering. Langton's Ant är ett sådant exempel. Relativa turmiter är per definition isotropa ; Att rotera turmiten påverkar inte resultatet. Relativa turmiter heter så eftersom riktningarna är kodade i förhållande till den aktuella orienteringen, vilket motsvarar att använda orden "vänster" eller "bakåt". Absoluta turmitor, i jämförelse, kodar sina riktningar i absoluta termer: en viss instruktion kan styra turmiten att röra sig "nord". Absoluta turmiter är tvådimensionella analoger till konventionella Turing-maskiner, så de kallas ibland helt enkelt för "Tvådimensionella Turing-maskiner". Resten av denna artikel handlar om det relativa fallet.
Specifikation
Följande specifikation är specifik för turmiter på ett tvådimensionellt kvadratiskt rutnät, den mest studerade typen av turmit. Turmiter på andra galler kan specificeras på liknande sätt.
Som med Langtons myra utför turmiter följande operationer varje tidssteg:
- vrid på platsen (med någon multipel av 90°)
- ändra färgen på fyrkanten
- flytta fram en ruta.
Liksom med Turing-maskiner specificeras åtgärderna av en tillståndsövergångstabell som visar turmitens aktuella interna tillstånd och färgen på cellen den för närvarande står på. Till exempel specificeras turmiten som visas i bilden överst på denna sida av följande tabell:
| Nuvarande färg | |||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| Skriv färg | Sväng | Nästa stat | Skriv färg | Sväng | Nästa stat | ||
| Nuvarande tillstånd | 0 | 1 | R | 0 | 1 | R | 1 |
| 1 | 0 | N | 0 | 0 | N | 1 | |
Riktningen att svänga är en av L (90° vänster), R (90° höger), N (ingen sväng) och U (180° U-sväng ).
Exempel
- Exempel på turmiter i två tillstånd i två färger på ett fyrkantigt rutnät , allt från en tom konfiguration:
Spiral tillväxt.
Produktion av en motorväg efter en period av kaotisk tillväxt.
Kaotisk tillväxt med en distinkt textur.
Tillväxt med en distinkt struktur inuti en expanderande ram.
Konstruera en Fibonacci-spiral .
Konstruera en växande diamant
- Exempel på turmiter med fler tillstånd och färger och på icke-fyrkantiga rutnät:
Tre-stats tvåfärgad turmite som producerar ett snöflingaliknande fraktalmönster .
Trefärgad tretillståndsturmit på ett hexagonalt rutnät , växer kaotiskt med en distinkt struktur innan den fastnar i en periodisk loop efter cirka 194150 steg.
Med utgångspunkt från ett tomt rutnät eller andra konfigurationer är de vanligast observerade beteendena kaotisk tillväxt, spiraltillväxt och "motorvägskonstruktion". Sällsynta exempel blir periodiska efter ett visst antal steg.
Upptaget Beaver-spel
Allen H. Brady sökte efter terminerande turmiter (motsvarande upptagna bävrar ) och hittade en 2-tillstånds 2-färgsmaskin som skrev ut 37 1:or innan den stannade, och en annan som tog 121 steg innan den stannade. Han övervägde också turmiter som rör sig på ett triangulärt rutnät och hittade flera upptagna bävrar här också.
Ed Pegg, Jr. övervägde en annan inställning till det upptagna bäverspelet. Han föreslog turmiter som kan vända till exempel både vänster och höger, dela sig i två delar. Turmitor som senare möts förintar varandra. I det här systemet är en Busy Beaver en som från ett startmönster av en enda turmite varar längst innan alla turmiter utplånar varandra.
Andra rutnät
Efter Allen H. Bradys första arbete med turmiter på ett triangulärt rutnät, har sexkantiga plattor också utforskats. Mycket av detta arbete beror på Tim Hutton, och hans resultat finns i Rule Table Repository. Han har också betraktat Turmites i tre dimensioner, och samlat in några preliminära resultat. Allen H. Brady och Tim Hutton har också undersökt endimensionella relativa turmites på heltalsgittret, som Brady kallade simfötter . (Endimensionella absoluta turmiter är naturligtvis helt enkelt kända som Turing-maskiner.)
Se även
- Cellulär automat – Diskret modell studerad inom datavetenskap
- Langtons myra – Tvådimensionell Turingmaskin med emergent beteende
- Patersons maskar – Familj av cellulära automater för att modellera matningsbeteende
- ^ Langton, Chris G. (1986). "Studerar konstgjort liv med cellulära automater" (PDF) . Physica D: Icke-linjära fenomen . 22 (1–3): 120–149. Bibcode : 1986PhyD...22..120L . doi : 10.1016/0167-2789(86)90237-X . hdl : 2027.42/26022 .
- ^ Brady, Allen H. (1988). "Det upptagna bäverspelet och meningen med livet". I Rolf Herken (red.). The Universal Turing Machine: A Half-Century Survey . Springer-Verlag. ISBN 0-19-853741-7 .
- ^ a b Brady, Allen H. (1995). "Det upptagna bäverspelet och meningen med livet" . I Rolf Herken (red.). The Universal Turing Machine: A Half-Century Survey (2nd ed.). Springer-Verlag. s. 237–254. ISBN 3-211-82637-8 .
- ^ a b Rucker, Rudy. "Artificiellt livslab" . Hämtad 16 oktober 2009 .
-
^
Dewdney, AK (september 1989). "Computer Recreations: Tvådimensionella Turing-maskiner och Turmites gör spår på ett plan". Scientific American . 261 : 180–183. doi : 10.1038/scientificamerican0989-180 .
- ^ Pegg, Jr., Ed. "Mattepussel" . Hämtad 15 oktober 2009 .
externa länkar
- "Webbsida som visar flera turmiter" . Arkiverad från originalet 2013-12-21.
- Pegg Jr., Ed (7 juni 2004). "Math Games: 2D Turing Machines" . MAA Online. Arkiverad från originalet 2013-05-16.
- Pegg Jr., Ed (27 oktober 2003). "Math Games: Patersons Worms Revisited" . MAA Online. Arkiverad från originalet 2004-03-23.
- Turmite , på MathWorld .
- Golly script för att generera godtyckliga turmites
- Turmites och upptagna bävrar med absolut och relativ rörelse på kvadratiska, kubiska, triangulära och sexkantiga rutnät