Automaty komórkowe – Mrówka Langtona
Wizualizacja nawet prostego algorytmu dwu-wymiarowej maszyny Turinga może utworzyć imponujÄ…ce obrazy. Ruch takiej maszyny może być niepozorny – przybierajÄ…c chaotycznÄ… formÄ™ w poczÄ…tkowej fazie, i dopiero po milionach iteracji, zacząć tworzyć charakterystyczne wzory. W tym wpisie pokażę jak zdefiniować przykÅ‚adowÄ… regułę przejść maszyny Turinga dla prostego automatu komórkowego jakim jest mrówka Langtona oraz przykÅ‚adowe wizualizacje prac innych maszyn.
Model maszyny Turinga w przetwarzaniu obrazów
Model maszyny Turinga służy do wykonywania algorytmów. Możemy zdefiniować następujące atrybuty tego modelu:
- Zbiór stanów – możliwe stany jakie może przyjąć gÅ‚owica
- Zbiór wejść – możliwy alfabet wejÅ›ciowy
- Zbiór wyjść – możliwy alfabet wyjÅ›ciowy
- Stan poczÄ…tkowy
W przetwarzaniu obrazów przez maszyny Turinga, “taÅ›mÄ…” bÄ™dzie bitmapa. Maszyna na podstawie stanu gÅ‚owicy oraz wartoÅ›ci piksela na bieżącej pozycji, zgodnie ze zdefiniowanÄ… regułą przejść, ustawi wyjÅ›ciowÄ… wartość piksela, nowy stan gÅ‚owicy i przesunie jÄ… na odpowiednie miejsce w przestrzeni. Aby ograniczyć wielkość alfabetu wejÅ›ciowego, można posÅ‚użyć siÄ™ operacjÄ… modulo na wartoÅ›ci RGB danego piksela.
Mrówka Langtona
Mrówka Langtona jest prostym automatem komórkowym. Porusza się po nieskończonej planszy podzielonej na kwadratowe pola. Na jej przykładzie pokażę jak można zdefiniować jej ruchy na model dwuwymiarowej maszyny Turinga.
Algorytm ruchu
- jeśli mrówka znajduje się na czarnym polu:
- zmiana koloru pola na biały
- obrót w prawo i przejście do nastepnęgo pola
- jeśli znajduje się na białym polu:
- zmiana koloru pola na czarny
- obrót w lewo i przejście do następnego pola
Jak można zauważyć, mrówka zmienia bieżący kolor pola na przeciwny oraz porusza się tylko ortogonalnie. Algorytm ten można bardzo prosto zapisać dla maszyny Turinga.
Funkcja przejść dla 2D maszyny Turinga
Stan | β | δ | σ | |||
---|---|---|---|---|---|---|
0 | 1 | 0 | 1 | 0 | 1 | |
0 | 3 | 1 | 1 | 0 | 3 | 4 |
1 | 0 | 2 | 1 | 0 | 2 | 5 |
2 | 1 | 3 | 1 | 0 | 4 | 3 |
3 | 2 | 0 | 1 | 0 | 5 | 2 |
- Stan: bieżący stan głowicy
- β: wyjściowy stan głowicy
- δ: wyjściowa wartość pola
- σ: wyjściowa pozycja głowicy
Wartość każdego atrybutu jest zależna od wartości pola na bieżącej pozycji głowicy. Należy więc w każdym atrybcie maszyny Turinga, uwzględnić warunki dla wszystkich symboli alfabetu wejściowego. Wartość atrybutu σ odnosi się do indeksu pola w zdefiniowanym modelu sąsiedztwa.
Model sÄ…siedztwa
Mrówka z danego pola może poruszyć się na tylko w dwa możliwe pozycje, położone bezpośrednio obok niej. Bez uwzględnienia zwrotu mrówki w dwuwymiarowym modelu sąsiędztwa daje nam to cztery możliwości ruchu. Poniższy rysunek przedstawia dwuwymiarowy model sąsiedztwa, wykorzystany w definicji algorytmu ruchu mrówki oraz w pozostałych wizualizacjach w galerii.

Wizualizacje


Galeria maszyn Turinga
W tej sekcji przedstawię przykładowe efekty przetwarzania bitmap dla różnych reguł maszyn Turinga. Wygenerowane obrazy pochodzą z mojego autorskiego programu do wizualizacji prac maszyn Turinga.
“Magiczny” kwadrat – przetwarzanie bitmapy



Figury – przetwarzanie bitmapy




Litera “E”


Labirynty



Autostrady






Trójkąty



Bryły



Podsumowanie
Bardzo prosta reguÅ‚a ruchu, po upÅ‚ywie setek tysiÄ™cy lub milionów iteracji błądzenia i chaotycznych ruchów, może utworzyć zadziwiajÄ…ce wzory i ksztaÅ‚ty. Przedstawione w galerii wizualizacje sÄ… tylko częściÄ… z możliwych. JeÅ›li znasz innÄ… ciekawÄ… regułę, której nie przedstawiÅ‚em – napisz.
Strona Internetowa
Potrzebujesz ładnej strony internetowej? Zobacz demo na: tej stronie
Komentarze