Automat komórkowy drugiego rzędu

Przeszłe komórki wpływające na stan komórki w czasie t w automacie komórkowym drugiego rzędu

Podstawowy przepis CA 18 (po lewej) i jego odpowiednik drugiego rzędu przepis 18R (po prawej). Czas biegnie w dół. Zwróć uwagę na asymetryczne trójkąty góra/dół w regule nieodwracalnej.

Automat komórkowy drugiego rzędu to rodzaj odwracalnego automatu komórkowego (CA) wynalezionego przez Edwarda Fredkina , w którym stan komórki w chwili t zależy nie tylko od jej sąsiedztwa w chwili t − 1 , ale także od jej stanu w chwili t − 2 .

Ogólna technika

Ogólnie regułę ewolucji dla automatu drugiego rzędu można opisać jako funkcję f , która odwzorowuje sąsiedztwo komórki na permutację stanów automatu. W każdym kroku czasowym t , dla każdej komórki c automatu, funkcja ta jest stosowana do otoczenia c , dając permutację σ _c . Następnie ta permutacja σ _c jest stosowana do stanu komórki c w chwili t − 1 , a wynikiem jest stan komórki w chwili t + 1 . W ten sposób konfiguracja automatu w każdym kroku czasowym jest obliczana na podstawie dwóch poprzednich kroków czasowych: krok bezpośrednio poprzedzający określa permutacje, które są stosowane do komórek, a krok czasowy poprzedzający ten podaje stany, w których działają te permutacje .

Odwróconą dynamikę czasu automatu drugiego rzędu można opisać innym automatem drugiego rzędu z tym samym sąsiedztwem, w którym funkcja g odwzorowująca sąsiedztwa na permutacje daje permutację odwrotną do f . Oznacza to, że w każdym możliwym sąsiedztwie N , f ( N ) i g ( N ) powinny być permutacjami odwrotnymi. Przy tej odwrotnej regule automat opisany funkcją g poprawnie oblicza konfigurację w czasie t − 1 z konfiguracji w czasie t i t + 1 . Ponieważ każdy automat drugiego rzędu może być odwrócony w ten sposób, wynika z tego, że wszystkie są odwracalnymi automatami komórkowymi , niezależnie od tego, która funkcja f jest wybrana do określenia reguły automatu.

Dla automatów dwustanowych

Jeśli automat komórkowy ma tylko dwa stany, to są również tylko dwie możliwe permutacje stanów: permutacja tożsamości , która odwzorowuje każdy stan na siebie, oraz permutacja, która odwzorowuje każdy stan na inny stan. Możemy utożsamiać te dwie permutacje z dwoma stanami automatu. W ten sposób każdy automat komórkowy drugiego rzędu (zdefiniowany przez funkcję od sąsiedztwa do permutacji) odpowiada jednoznacznie zwykłemu (pierwszego rzędu) automatowi komórkowemu, zdefiniowanemu przez funkcję bezpośrednio z sąsiedztwa do stanów. Dwustanowe automaty drugiego rzędu są symetryczne przy odwróceniu w czasie: odwrócona w czasie dynamika automatu może być symulowana przy użyciu tej samej reguły, co oryginalna dynamika.

Jeśli postrzegamy te dwa stany jako wartości logiczne , to zgodność między automatem zwykłym a automatem drugiego rzędu można opisać po prostu: stan komórki automatu drugiego rzędu w chwili t + 1 jest stanem wyłącznym lub jej stanem w chwili t − 1 ze stanem, który obliczy dla niego zwykła reguła automatu komórkowego. W rzeczywistości wszystkie reguły drugiego rzędu dwóch stanów mogą być tworzone w ten sposób. Powstały automat drugiego rzędu będzie jednak generalnie mało podobny do zwykłego CA, z którego został zbudowany. Reguły drugiego rzędu skonstruowane w ten sposób są nazywane przez Stephena Wolframa przez dodanie „R” do numeru lub kodu Wolframa reguły podstawowej.

Aplikacje

Automaty drugiego rzędu mogą być używane do symulacji komputerów z kulami bilardowymi i modelu ferromagnetyzmu Isinga w mechanice statystycznej . Mogą być również wykorzystywane do kryptografii .