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.

neighborhood.png
2D model sąsiedztwa

Wizualizacje

ants.pngants_black.png
Cztery aktywne mrówki Langtona

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

magic_square_1.png magic_square_2.png magic_square_3.png
Magiczny kwadrat

Figury – przetwarzanie bitmapy

circle.png icicle.png surface.png apple.png
Koło, sople lodu, krajobraz, jabłko

Litera “E”

letter_e_1.png letter_e_2.png
Litery “E”

Labirynty

labyrinth_2.png labyrinth_3.png snake.png
Labirynt

Autostrady

highway_1.png highway_3d_2.png highway_4.pnghighway_2.pnghighway_3.pnghighway_3d_1.png
Autostrady 2D i 3D

Trójkąty

kite.png highway_3d_3.png triangles_1.png
Latawiec, autostrada, seria trójkątów

Bryły

block_1.png block_2.png triangles_2.png
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.


Podobne artykuły

Komentarze

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *