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.


Strona Internetowa

Potrzebujesz ładnej strony internetowej? Zobacz demo na: tej stronie strona internetowa


Podobne artykuły

Komentarze

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *