▸Programowanie▸Automaty komórkowe – Mrówka Langtona

lip

2013

Automaty komórkowe – Mrówka Langtona

Programowanie

Maszyna Turinga

Brak komentarzy

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	β		δ		σ
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.

Automaty komórkowe – Mrówka Langtona