Worms of Paterson

Patersonovi červi jsou rodinou  buněčných automatů tyurmitového typu vynalezených v roce 1971 britským vědcem Mikem Patersonem k simulaci chování a krmení některých prehistorických červů . Navzdory jednoduchému souboru pravidel může být chování automatů velmi složité a pro jeden ze souborů pravidel je jeho osud neznámý.  

Pozadí

Prehistoričtí červi se živili usazeninami na dně rybníků a vyhýbali se opakování svých cest, protože bylo málo potravy. Potravy se však scházely v hromadách, takže měli tendenci zůstávat blízko cest, po kterých už prošli. Různé druhy červů přitom měly různá pravidla, která určovala, jak blízko u projetých cest se zdržovat, kdy a jak ostře odbočit [1] .

V roce 1969 vytvořili David Raup a Adolf Zeilacher počítačovou simulaci stop fosilních červů, která inspirovala Patersona a Johna Conwaye k hledání jednoduchých modelů buněčných automatů ke studiu idealizovaných červů na mřížce [2] . Conway navrhl studovat červy na čtvercové mřížce , ale existovaly pouze tři typy červů s poněkud nudným chováním a Paterson navrhl použití trojúhelníkové mřížky.  

Popis

V tomto modelu se červ plazí po trojúhelníkové mřížce , jejíž okraje znázorňují potravu, a když přechází přes okraj, je přetřen („sežrán“) [3] . V každém vrcholu si červ vybírá, kterou plochou se bude pohybovat, podle toho, která ze šesti ploch sousedících s vrcholem je vyplněna. Směry se počítají z pohledu červa [1] . Červ umírá, pokud vrchol nemá žádné nevyplněné („nenažrané“) plochy, což je však možné pouze v počátečním stavu z důvodu paritních úvah [4] .

Pravidla jsou předem daná a definují konkrétní buněčný automat v rodině („ druh červa“), často se však předpokládá, že se červ rozhoduje na každém kroku, ale pokud se již s podobnou situací setkal, musí učinit stejné rozhodnutí.

Číslování pravidel

Pravidla lze klasifikovat určením směrů, kterými se červ vydá, když se poprvé „setká“ s neznámou situací, v pořadí, v jakém se tyto situace vyskytují. Směry jsou obvykle číslovány ve směru hodinových ručiček, počínaje 0 - směr vpřed, viz obrázek vlevo [5] . V tomto případě červ nemůže zvolit směr 3 - otočit se zpět. Také obvykle neexistují žádné volby, které červ nebude muset udělat, protože zemře dříve, a má se za to, že červ udělá první zatáčku doprava, protože případ zatáčky doleva je symetrický [1] .

Například pravidlo {2, 2, 0}, které specifikuje červa zobrazeného vpravo, říká, že v prvních dvou možnostech (všech 5 směrů není zastíněno) se červ otočí vpravo dozadu a ve třetí (vpravo -směr dozadu je stínovaný a směry doleva jsou stínované) vpřed, vlevo-vzad a vpravo-vzad, v daném pořadí) volí pohyb vpřed. Další možnosti nejsou uvedeny, protože červ se potřetí vrátí na začátek a zemře. Pokud se omezíme na případy, kdy červ udělá první zatáčku doprava, pak existuje potenciálně 1296 možných pravidel [6] . S přihlédnutím k faktu, že červ často umírá dříve, než stihne udělat všechny možné volby, a proto nemá smysl tato pravidla rozlišovat, je jich pouze 412 [4] . Mezi nimi je 336 konečných, 73 nekonečných a cyklicky se opakujících s posunem, u dvou se nekonečno neprokázalo, ale předpokládá se (to jsou pravidla {1,0,4,2,0,2,0} a {1,0,4,2,0 ,1,5}) a chování jiného je neznámé (pravidlo {1,0,4,2,0,1,5}) [4] .

Poznámky

1. ↑ 1 2 3 Beeler, Červ Michaela Patersona . Massachusetts Institute of Technology (červen 1973). Staženo 15. srpna 2008. (neurčitý)
2. ↑ Patersonovi červi . wolframmath svět. Staženo 15. srpna 2008. (neurčitý)
3. ↑ Hayes, Briane. In Search of the Optimal Scumsucking Bottomfeeder  //  American Scientist  :časopis. — Sigma Xi, Společnost pro vědecký výzkum. — Sv. 95 , č. 5 . - str. 392-396 . - doi : 10.1511/2003.5.392 .
4. ↑ 1 2 3 Chaffin, Červi Benjamina Patersona . Archivováno z originálu 7. června 2011. (neurčitý)
5. ↑ Pegg Jr., Ed Math Games: Paterson's Worms Revisited . MAA Online (27. října 2003). Získáno 15. srpna 2008. Archivováno z originálu dne 23. března 2004. (neurčitý)
6. ↑ Gardner, Martin (1986), Vázané koblihy a jiné matematické zábavy , W. H. Freeman, ISBN 978-0-7167-1799-7