Viermii lui Paterson

Viermii lui Paterson sunt o  familie de automate celulare de tip tyurmit , inventate în 1971 de omul de știință britanic Mike Paterson pentru a simula comportamentul și hrănirea unor viermi preistorici . În ciuda unui set simplu de reguli, comportamentul automatelor poate fi foarte complex, iar pentru unul dintre seturile de reguli soarta acestuia este necunoscută.  

Fundal

Viermii preistorici s-au hrănit cu sedimente de pe fundul iazurilor și au evitat să-și repete căile pentru că era puțină hrană. Cu toate acestea, mâncarea a fost întâlnită în grămezi, așa că aveau tendința să rămână aproape de căile pe care le parcurseseră deja. În același timp, diferite tipuri de viermi aveau reguli diferite care determinau cât de aproape de căile trecute să rămână, când și cum să se întoarcă brusc [1] .

În 1969, David Raup și Adolf Zeilacher au creat  o simulare pe computer a urmelor de viermi fosili, care i-a inspirat pe Paterson și John Conway să caute modele simple de automate celulare pentru a studia viermii idealizați pe o rețea [2] . Conway a propus să studieze viermii pe o rețea pătrată , dar existau doar trei tipuri de viermi cu un comportament destul de plictisitor, iar Paterson a sugerat folosirea unei rețele triunghiulare.

Descriere

În acest model, viermele se târăște de-a lungul unei rețele triunghiulare , ale cărei margini înfățișează hrana, iar când trece de margine, este pictat peste („mâncat”) [3] . La fiecare vârf, viermele alege pe ce față să se deplaseze în funcție de care dintre cele șase fețe adiacente vârfului sunt umplute. Direcțiile se numără din punctul de vedere al viermelui [1] . Viermele moare dacă vârful nu are fețe neumplute („nemâncate”), ceea ce, totuși, este posibil doar în starea inițială din considerente de paritate [4] .

Regulile sunt predeterminate și definesc un automat celular specific din familie („ tipul de vierme”), cu toate acestea, adesea se presupune că viermele ia o decizie la fiecare pas, dar dacă a întâlnit deja o situație similară, trebuie luați aceeași decizie.

Numerotarea regulii

Regulile pot fi clasificate prin precizarea direcțiilor pe care le ia viermele atunci când „întâlnește” pentru prima dată o situație necunoscută, în ordinea în care apar aceste situații. Direcțiile sunt de obicei numerotate în sensul acelor de ceasornic, începând de la 0 - direcția înainte, vezi imaginea din stânga [5] . În acest caz, viermele nu poate alege direcția 3 - întoarce-te. De asemenea, de obicei nu există alegeri pe care viermele să nu fie nevoit să le facă, din moment ce acesta moare mai devreme și se consideră că viermele face prima viraj la dreapta, întrucât cazul virajului la stânga este simetric [1] .

De exemplu, regula {2, 2, 0}, care specifică viermele afișat în dreapta, spune că în primele două opțiuni (toate cele 5 direcții sunt neumbrite) viermele se întoarce spre dreapta, iar în a treia (dreapta). -direcția înapoi este umbrită și direcțiile din stânga sunt umbrite) înainte, stânga-înapoi și, respectiv, dreapta-înapoi) selectează mișcarea înainte. Alte alegeri nu sunt indicate, deoarece viermele revine la început pentru a treia oară și moare. Dacă ne limităm la cazurile în care viermele face prima întoarcere la dreapta, atunci există potențial 1296 de reguli posibile [6] . Totuși, ținând cont de faptul că viermele moare adesea înainte de a avea timp să facă toate alegerile posibile și, prin urmare, nu are rost să distingem aceste reguli, există doar 412 dintre ele [4] . Dintre acestea, 336 sunt finite, 73 sunt infinite și repetate ciclic cu o schimbare, pentru doi, infinitul nu a fost dovedit, dar se presupune (acestea sunt regulile {1,0,4,2,0,2,0} și {1,0,4,2,0 ,1,5}), iar comportamentul altuia este necunoscut (regula {1,0,4,2,0,1,5}) [4] .

Note

1. ↑ 1 2 3 Beeler, Viermele lui Michael Paterson . Massachusetts Institute of Technology (iunie 1973). Preluat la 15 august 2008. (nedefinit)
2. ↑ Viermii lui Paterson . lumea wolframmath. Preluat la 15 august 2008. (nedefinit)
3. ↑ Hayes, Brian. În căutarea alimentatorului de fund optim de suge  // Om de știință  american  :revistă. — Sigma Xi, Societatea de Cercetare Științifică. — Vol. 95 , nr. 5 . - P. 392-396 . - doi : 10.1511/2003.5.392 .
4. ↑ 1 2 3 Chaffin, Viermele lui Benjamin Paterson . Arhivat din original pe 7 iunie 2011. (nedefinit)
5. ↑ Pegg Jr., Ed Math Games: Paterson's Worms Revisited . MAA Online (27 octombrie 2003). Consultat la 15 august 2008. Arhivat din original la 23 martie 2004. (nedefinit)
6. ↑ Gardner, Martin (1986), Gogoși înnodate și alte divertismente matematice , W. H. Freeman, ISBN 978-0-7167-1799-7