Worms of Paterson

Patersons maskar är en  familj av cellulära automater av tyurmittyp som uppfanns 1971 av den brittiske vetenskapsmannen Mike Paterson för att simulera beteendet och matningen av vissa förhistoriska maskar . Trots en enkel uppsättning regler kan beteendet hos automater vara mycket komplext, och för en av regeluppsättningarna är dess öde okänt.  

Bakgrund

Förhistoriska maskar livnärde sig på sediment på botten av dammar och undvek att upprepa sina stigar eftersom det fanns lite mat. Maten möttes dock i högar, så de tenderade att hålla sig nära de stigar de redan färdats. Samtidigt hade olika typer av maskar olika regler som avgjorde hur nära de passerade stigarna man skulle stanna, när och hur man skulle svänga skarpt [1] .

1969 skapade David Raup och Adolf Zeilacher  en datorsimulering av fossila maskspår, vilket inspirerade Paterson och John Conway att söka efter enkla cellulära automatmodeller för att studera idealiserade maskar på ett gitter [2] . Conway föreslog att man skulle studera maskar på ett fyrkantigt rutnät , men det fanns bara tre typer av maskar med ganska tråkigt beteende, och Paterson föreslog att man skulle använda ett triangulärt rutnät.

Beskrivning

I denna modell kryper masken längs ett triangulärt galler , vars kanter visar mat, och när den passerar kanten målas den över ("äts") [3] . Vid varje vertex väljer masken vilket ansikte som ska röra sig längs baserat på vilken av de sex ytorna som gränsar till vertexen som är fyllda. Vägbeskrivningar räknas från maskens synvinkel [1] . Masken dör om vertexet inte har några ofyllda ("oåtta") ytor, vilket dock är möjligt endast i initialtillståndet på grund av paritetsskäl [4] .

Reglerna är förutbestämda och definierar en specifik cellulär automat i familjen (" sorten av mask"), men det antas ofta att masken fattar ett beslut vid varje steg, men om den redan har stött på en liknande situation måste den fatta samma beslut.

Regelnumrering

Regler kan klassificeras genom att ange de riktningar som masken tar när den först "stöter på" en obekant situation, i den ordning som dessa situationer inträffar. Vägbeskrivningar numreras vanligtvis medurs, med början från 0 - framåtriktningen, se bilden till vänster [5] . I det här fallet kan masken inte välja riktning 3 - vänd tillbaka. Dessutom finns det vanligtvis inga val som masken inte behöver göra, eftersom den dör tidigare, och det anses att masken gör första svängen till höger, eftersom fallet med en vänstersväng är symmetrisk [1] .

Till exempel, regeln {2, 2, 0}, som specificerar masken som visas till höger, säger att i de två första valen (alla 5 riktningar är oskuggade) vänder masken höger-bakåt, och i den tredje (den högra -bakåtriktningen är skuggad och vänsterriktningen är skuggad) framåt, vänster-bakåt respektive höger-bakåt) väljer framåtrörelse. Ytterligare val anges inte, eftersom masken återvänder till början för tredje gången och dör. Om vi ​​begränsar oss till fall där masken gör första svängen till höger, så finns det potentiellt 1296 möjliga regler [6] . Men med tanke på att masken ofta dör innan den hinner göra alla möjliga val, och det därför inte är någon idé att särskilja dessa regler, finns det bara 412 av dem [4] . Bland dem är 336 ändliga, 73 är oändliga och cykliskt upprepade med ett skifte, för två har oändlighet inte bevisats, men det antas (detta är reglerna {1,0,4,2,0,2,0} och {1,0,4,2,0 ,1,5}), och beteendet hos en annan är okänt (regel {1,0,4,2,0,1,5}) [4] .

Anteckningar

1. ↑ 1 2 3 Beeler, Michael Patersons mask . Massachusetts Institute of Technology (juni 1973). Hämtad 15 augusti 2008. (obestämd)
2. ↑ Patersons maskar . wolframmath världen. Hämtad 15 augusti 2008. (obestämd)
3. ↑ Hayes, Brian. In Search of the Optimal Scumsucking Bottomfeeder  //  American Scientist  :tidskrift. — Sigma Xi, Scientific Research Society. — Vol. 95 , nr. 5 . - s. 392-396 . - doi : 10.1511/2003.5.392 .
4. ↑ 1 2 3 Chaffin, Benjamin Patersons maskar . Arkiverad från originalet den 7 juni 2011. (obestämd)
5. ↑ Pegg Jr., Ed Math Games: Paterson's Worms Revisited . MAA Online (27 oktober 2003). Hämtad 15 augusti 2008. Arkiverad från originalet 23 mars 2004. (obestämd)
6. ↑ Gardner, Martin (1986), Knotted donuts and other matematical entertainments , W. H. Freeman, ISBN 978-0-7167-1799-7