Un automat celular bloc este o clasă de automate celulare în care rețeaua este împărțită în blocuri, iar funcția de tranziție este aplicată fiecărui bloc separat. Automatele celulare bloc sunt utile pentru modelarea fenomenelor fizice, deoarece adesea nu este dificil să alegeți funcții de tranziție, astfel încât automatul celular rezultat să fie reversibil și să respecte legile de conservare alese . [unu]
Un automat celular este o rețea obișnuită de celule, fiecare dintre ele având o stare luată dintr-un set finit de stări și o funcție de tranziție necesară pentru a actualiza stările celulei pe baza stărilor vecinilor săi. Se numește bloc dacă rețeaua este împărțită în blocuri egale care nu se intersectează și funcția de tranziție își folosește blocul ca vecinătate a fiecărei celule. În acest caz, automatul trebuie să aibă un număr finit de partiții în blocuri utilizate pe rând: de exemplu, o partiție poate fi deplasată într-o direcție. [1] [2]
Astfel, pe parcursul fiecărei etape a automatului, funcția de tranziție este aplicată simultan tuturor celulelor, care schimbă fiecare bloc independent de celelalte, apoi partiția se schimbă la următoarea și pasul se repetă. Acest lucru face posibilă efectuarea de calcule non-triviale folosind funcții de tranziție destul de simple.
Cel mai simplu exemplu al unei astfel de scheme este cartierul Margolus , în care celulele unei rețele pătrate sunt împărțite în blocuri 2 × 2 prin linii verticale și orizontale, iar după fiecare pas, diviziunea în blocuri este deplasată cu o celulă orizontal și vertical. ; astfel, toate cele patru celule ale oricărui bloc ajung în blocuri diferite în pasul următor. [3] Acest cartier poartă numele lui Norman Margolus ( în engleză. Norman Margolus ), unul dintre primii cercetători ai automatelor celulare bloc. [unu]
Un exemplu de automat bloc celular folosind un cartier Margolus este „The Critters” . Funcția de tranziție Critters inversează starea fiecărei celule dacă numărul de celule vii din bloc nu este două și rotește întregul bloc cu 180° dacă acest număr este trei. Deoarece numărul de celule vii se schimbă în numărul de celule moarte, iar funcțiile de tranziție sunt reversibile pentru fiecare valoare a numărului de celule, un astfel de automat celular este reversibil pe fiecare bloc și, prin urmare, este reversibil în ansamblu. [4] Cu toate acestea, prezintă un comportament dinamic complex similar cu Jocul vieții al lui Conway ; în special, este Turing complet , vezi articolul aferent pentru detalii .