728 x 90

A gdyby tak zbudować maszynę Turinga z LEGO?

A gdyby tak zbudować maszynę Turinga z LEGO?

Czym jest maszyna Turinga? W zasadzie jest to model matematyczny, ale możemy ją rozumieć jako bardzo abstrakcyjny model dzisiejszych komputerów. W tym artykule zbudujemy ją, a w kolejnym zaprogramujemy.

Poniższy tekst powstał na podstawie pracy magisterskiej wykonanej na Wydziale Matematyki i Informatyki UMK pod opieką  prof. dr hab. Macieja M. Sysło.

Czym jest maszyna Turinga.

Maszyna Turinga to model matematyczny, który można także przełożyć na rzeczywiste urządzenie. Można ją rozumieć jako abstrakcyjny model dzisiejszego komputera, choć nim nie jest. Początkowo służyła przede wszystkim do rozstrzygania, jakie problemy można algorytmicznie rozwiązać. Jest kilka rodzajów maszyny Turinga, lecz my skupimy się na jednym, tzw. jednotaśmowej determonistycznej maszynie Turinga. Na jej fizyczny opis składa się nieskończona taśma podzielona na komórki, głowica odczytująco-zapisująca oraz urządzenie sterujące wraz z programem i stanem. W komórkach znajdują się symbole, które są zrozumiałe dla maszyny – głowica może je odczytać, jak i zapisać. Urządzenie sterujące w zależności od odczytanego symbolu oraz własnego stanu podejmuje akcje:

  • może zmienić swój stan,
  • może zmienić symbol w aktualnie odczytywanej komórce,
  • nakazuje przesunięcie głowicy w prawo lub lewo.

Maszynę Turinga nazywamy deterministyczną, gdy jej program jest deterministyczny, czyli gdy jednej parze znak i stan odpowiada jedna instrukcja. Używając określenia maszyna Turinga zawsze będziemy mieli na myśli jednotaśmową deterministyczną maszynę Turinga. Innymi słowy wiadomo, jaki będzie miała stan po wykonaniu kolejnych operacji na stanie aktualnym.

Po formalną definicję odsyłam do źródeł (np. Wikipedii).

Popatrzmy na elementy maszyny.

Taśma – w założeniach teoretycznych nieskończona, a w praktyce powinna być na tyle długa, aby nie zaburzyć pracy maszyny, tzn. głowica nigdy nie może wyjść poza taśmę. Jest podzielona na komórki, w których zapisany jest dokładnie jeden symbol ze zbioru Г. Podział następuje wzdłuż taśmy, czyli każda komórka ma sąsiada po lewej i prawej stronie. Komórki zapisane symbolami z Σ stanowią dane dla maszyny Turinga, a pozostałe komórki powinny zawierać symbol pusty B. Początkowy układ symboli na taśmie jest odpowiednikiem danych wejściowych, a taśma odpowiada pamięci we współczesnych komputerach. W implementacji maszyny Turinga na klockach Lego, będziemy posługiwać się znakiem 1 i znakiem pustym 0 ( Г = {0, 1}). W ten sposób wykorzystamy unarny zapis liczb, czyli pięć jedynek oddzielonych znakami pustymi 0111110, będzie oznaczało liczbę 5. Taką maszynę nazywamy unarną maszyną Turinga. Za pomocą zbioru Г = {0, 1} możemy również stosować inne zapisy, ale nie będziemy ich rozważać.

Głowica – jest ustawiona dokładnie nad jedną komórką i może z niej odczytywać jak i zapisywać. Wartość odczytanego symbolu z taśmy przekazuje urządzeniu sterującemu i na jego polecenie może zmienić zawartość obserwowanej komórki oraz przesunąć się na sąsiadującą komórkę z prawej lub lewej strony. Podczas rozpoczynania pracy programu głowica powinna być ustawiona na odpowiednim symbolu zależnym od danego programu. Głowica jest odpowiednikiem elementów odczytujących i zapisujących we współczesnych komputerach.

Urządzenie sterujące – zawiera pamięć stanu i program. Decyduje o działaniu maszyny na podstawie otrzymanego od głowicy symbolu i własnego stanu. Urządzenie zawsze jest w jakimś z dozwolonych stanów. Do podejmowania decyzji o działaniu wykorzystuje program. Na pojedynczy ruch składają się akcje:

  • odebranie od głowicy symbolu s, z komórki nad którą znajduje się głowica,
  • odczytanie aktualnego stanu q z własnej pamięci stanów, będącej częścią urządzenia sterującego,
  • na podstawie aktualnego stanu i symbolu odczytuje z programu jaką akcję ma podjąć δ(q, s) = (q’, s’, d),
  • jeśli zmienił się symbol s ≠ s’ to przekazywana jest informacja do głowicy, że ma zmienić wartość w aktualnie obserwowanej komórce taśmy na symbol s’,
  • jeśli zmienił się stan q ≠ q’ to zmieniamy wartość w pamięci stanów na stan q’,
  • przekazywana jest informacja do głowicy, że ma zmienić położenie o jedną komórkę w kierunku d, jeśli obecny stan jest stanem końcowym, maszyna kończy pracę.

Stan urządzenia sterującego identyfikujemy ze stanem maszyny Turinga i używamy tych określeń zamiennie. Wybór instrukcji urządzenia sterującego zależy od aktualnego stanu i odczytanego symbolu. Dla danego programu maszyna Turinga na początku powinna być ustawiona na stanie początkowym i odpowiednim miejscu na taśmie. Urządzenie sterujące odpowiada procesorowi we współczesnych komputerach.

Działanie maszyny.

Zasadniczo działanie zależy od programu. Przed rozpoczęciem działania należy dokładnie przygotować maszynę Turinga:

  • taśma powinna zawierać odpowiednie dane wejściowe, a pozostałe komórki powinny być wypełnione symbolami pustymi,
  • głowica powinna być w położeniu nad zdefiniowaną dla programu odpowiednią komórką na taśmie (najczęściej na krańcowej komórce z danymi z prawej lub lewej strony),
  • urządzenie sterujące powinno być ustawione na stan początkowy q0 oraz mieć zdefiniowany poprawny program.
    Tak przygotowana maszyna Turinga może zostać uruchomiona i będzie działać według zadanego programu. Gdy ustawiony zostanie jeden ze stanów końcowych, zakończy swoje działanie. W zależności od zadanego programu wynikiem może być:
  • stan w jakim znajduje się maszyna np. akceptujący lub odrzucający,
  • wartość zapisana na taśmie, najczęściej z jednej konkretnej strony.

Zapis programów

Jak już wcześniej powiedzieliśmy program odgrywa ważną rolę w maszynie Turinga i od niego właściwie zależy, czy dobrze wykonany zostanie algorytm. Aby program był poprawny, należy zdefiniować funkcję przejścia dla każdej możliwej pary stan-symbol. Najczęściej definiuje się funkcję dla każdej pary stan-symbol. Taka para nasuwa nam na myśl zapis programu w postaci tabeli. Wiersze będą odpowiadać kolejnym symbolom ze zbioru Г, a kolumny kolejnym stanom ze zbioru Q. Taka tabela ma o jeden wiersz więcej od liczby symboli i analogicznie o jedną kolumnę więcej od liczby stanów. Komórki tabeli nie będące w pierwszym wierszu lub kolumnie, zawierają wynik funkcji przejścia dla odpowiadającego w wierszu symbolu i w kolumnie stanu. Taką tabelę nazywamy tabelą stanów.

Przykładowy program

Powyższy program neguje bity w zapisie binarnym. W pierwszym wierszu zapisane są kolejne stany, a w pierwszej kolumnie wszystkie dozwolone symbole wraz z symbolem pustym. Komórki dla stanu końcowego zawierają instrukcję stop, która po prostu oznacza iż maszyna Turinga ma zakończyć pracę. Taki zapis pokazuje, że odczyt programu polega na odczytaniu odpowiedniej komórki pamięci. Funkcję przejścia może zapisać jeszcze na inny sposób, ale nie będziemy się nimi posługiwać, więc nie będziemy ich tutaj przedstawiać.

Więcej programów możecie znaleźć w sieci. Tymczasem przejdźmy do setna artykułu.

Co z tym Lego?

Do konstrukcji posłuży nam zestaw Lego Mindstorms EV3 wraz klockami Lego Technic. Projekt został zainspirowany konstrukcją przedstawioną na stronie http://www.cs.cmu.edu/~soonhok/building-a-lego-turing-machine.html. Jednak nasz projekt ma inne założenia i dlatego maszyna ma inną budowę. Taśma maszyny jak już wspominaliśmy wcześniej zawiera komórki, w których można zapisać jedynie dwa symbole. Głowica wraz z całym urządzeniem sterującym może się przesuwać w prawo i lewo. Mechanizm zmieniający wartość w komórce koliduje z urządzeniem odczytującym wartość komórki, dlatego urządzenie odczytujące jest wysuwane, aby wykonać odczyt i chowane, aby uniknąć kolizji. Poniżej przedstawiona jest instrukcja budowy całej maszyny.

Taśma

Elementy w środku taśmy powtarzają się i z pomocą strzałek można złożyć fragment konstrukcji taśmy.

Na rysunku 2 widać wszystkie elementy potrzebne do budowy taśmy. Dodatkowo u góry widać elementy służące do budowy komórek i odpowiadają one elementowi 1 na rysunku 3. Ten element przechodzi przez kolejne elementy 2, 3, 2, 4, itd. przez widoczne otwory. Element 4 odpowiada elementowi konstrukcyjnemu, który jest widoczny na wcześniejszych rysunkach. Na rysunku 4 widać już kompletną taśmę z komórkami. Symbole w komórkach są ustawiane przez przesunięcie klocka na jedną lub drugą stronę taśmy.

Rusztowanie Taśmy

Taśma jest umieszczona na rusztowaniu, które zapewnia odpowiednią wysokość umiejscowienia taśmy. Na rysunku 5 widać jeden z dwóch identycznych fragmentów rusztowania. Składamy je według narysowanych strzałek i podłączamy do taśmy za pomocą czarnego łącznika widocznego u góry. Po prawej stronie mamy jeszcze dodatkowe wzmocnienie, które łączymy z szarym elementem, widocznym na rysunku 6, w miejscu czarnej strzałki. Cała konstrukcja jest widoczna na rysunku 7. Połączenie z taśmą jest dodatkowo zaznaczone czerwonym zakreśleniem.

Maszyna Turinga jest połączona z taśmą (połączenie rozłączne) za pomocą zębatki. Umożliwia to przesuwanie się głowicy o poprawną odległość wzdłuż taśmy. Na rysunku 8 są pokazane wszystkie elementy potrzebne do złożenia zębatki. Zębatka jest wczepiona do rusztowania taśmy w taki sposób, jak jest to widoczne na rysunku 9. W ten sposób zakończyliśmy budowę całej taśmy i możemy przejść do złożenia głowicy z jednostką logiczną.

Głowica z jednostką logiczną.

Poniższe instrukcje z ilustracjami posłużą do złożenia konstrukcji, na którą będą się składać: jednostka logiczna, mechanizmy odczytu i zapisu symbolu w komórce oraz poruszania całej konstrukcji o komórkę wzdłuż taśmy. Zaczniemy od konstrukcji przyłączenia jednostki logicznej, która w naszym wypadku odpowiada urządzeniu sterującemu.

Na rysunku 10 widać mały fragment przyłącza, który łączymy według strzałek. Budowę drugiej części tego przyłącza widać na rysunku 11. Na obu rysunkach częścią wspólną są czarne elementy numer 1. Oprócz tego przyłącza potrzebne jest drugie, które widać na rysunku 12. Jednostka logiczna wraz z przyłączami jest przedstawiona na rysunku 13 potem zostanie połączona z pozostałymi częściami.

Podwozie.

Na rysunku 16 są przedstawione elementy składające się na urządzenie odczytujące symbol z komórki. Łączymy je według czerwonych strzałek podobnie jak to wykonywaliśmy w poprzednich przykładach. Na czarny długi element numer 1 nakładamy elementy idące wzdłuż widoczne nad nim, kolejno dwa czarne i dwa szare ślimaki i na koniec dwie żółte zatyczki. Po złożeniu urządzenie powinno wyglądać jak na rysunku 17.

Połączenie

Do podwozia przyłączymy jednostkę logiczną i duży silnik. Jednak aby wszystko było stabilne potrzebujemy łącznika, który wzmocni całą konstrukcję. Elementy do łącznika widzimy na rysunku 18. Z podwoziem łączy się duży silnik widoczny u góry oraz czarny element po prawej stronie (ten, który nie ma połączenia od dołu). Elementy przy numerze 1 (połączone w kolumnie) łączą się za pomocą czarnego elementu w miejscu czarnej strzałki z resztą konstrukcji. Zaś za pomocą niebieskiego elementu budują połączenie z jednostką logiczną. Całość zbudowanego łącznika jest widoczna na dwóch zdjęciach ujętych z różnych stron, przedstawionych na rysunku 19. Silnik widoczny na rysunku odpowiada za przesuwanie głowicy w prawo i lewo, a tak właściwie przesuwa on cały mechanizm.

Mechanizm zapisu mocujemy do wcześniej opisywanego silnika przesuwania głowicy. Na rysunku 20 widać elementy dołączanie do silnika przesuwania głowicy. Łączymy według czerwonych strzałek, a niebieskie elementy przy numerze 1 przechodzą przez szare na wylot i łączą się jeszcze z białym klockiem w miejscu pokazywanym przez czarne strzałki. Połączenie z silnikiem odbywa się za pomocą niebieskich elementów widocznych u góry zdjęcia. Połączone elementy są widoczne na rysunku 22 po lewej stronie wraz z silnikiem. Druga część konstrukcji jest widoczna na rysunku 21 i jest połączona z silnikiem zmieniającym symbol w komórce za pomocą szarego elementu widocznego u góry zdjęcia. Całość jest widoczna na rysunku 22 po prawej stronie. Na tym rysunku widzimy też, jak połączyć oba silniki w jedną konstrukcję, która jest już widoczna na rysunku 24.

Mechanizm wysuwania urządzenia odczytującego jest także przyłączony do silnika przesuwającego głowicę. Na rysunku 25 widać wystający jeden niebieski element, który łączymy z elementem czarnym widocznym na dole rysunku 26. Ponadto szary łącznik po lewej stronie na środku rysunku 26 wczepiamy od góry w środkowy otwór w silniku przesuwającym głowicę. Cały zamontowany mechanizm przesuwający urządzenie odczytujące wraz z częścią wcześniejszego połączenia widać na rysunku 28.

Zostały nam już tylko dwie małe części do złożenia widoczne na rysunku 27 przed i po złożeniu w całość. Po lewej mamy element przytrzymujący urządzenie odczytujące, który wczepiamy do silnika przesuwającego głowicę zaraz obok zamontowanego silnika przesuwającego urządzenie odczytujące. Po prawej mamy przedłużkę, którą wczepiamy do silnika umożliwiającego zmianę symbolu w komórce

Na rysunku 29 widać całą maszynę Turinga złożoną z klocków Lego przedstawioną z boku, z przodu i z tyłu. Oprócz poszczególnych elementów, które trzeba było połączyć w całość, należy jeszcze połączyć silniki z jednostką logiczną: silnik przesuwania głowicy łączymy przewodem krótkim do portu D, silnik zmiany symbolu w komórce łączymy przewodem średniej długości do portu C, silnik przesuwania urządzenia odczytującego łączymy przewodem średniej długości do portu B, urządzenie odczytujące łączymy długim przewodem do portu 1.

Element zmieniający w silniku zapis symbolu do komórki powinien być ustawiony na tej samej pozycji co urządzenie odczytujące. Podobnie koło zębate przesuwające urządzenie odczytujące. Maszyna musi być odpowiednio skalibrowana przed rozpoczęciem pracy, czyli urządzenie odczytujące jak i zapisujące symbol na taśmie musi znajdować się nad konkretną komórką, a nie w przestrzeni pomiędzy.

Maszyna zbudowana. W kolejnej części zaprogramujemy ją.

Jak zaprogramować maszynę?

Do utworzenia programu wykorzystujemy oprogramowania Lego Mindstorms EV3. Programowanie w nim polega na układaniu ikon modułów, bloków i ich łączeniu. Oparte jest na oprogramowaniu LabView i jest do niego bardzo podobne. Taki sposób zapisu programów jest często bardziej zrozumiały dla młodych użytkowników.

Programowanie polega na układaniu odpowiednich bloków i ich łączeniu. Do wykorzystania mamy trzy silniki oraz czujnik kolorów. Poza tym, możemy zapisywać w pamięci jednostki logicznej. Dodatkowo będziemy wykorzystywać bloki odpowiedzialne za pętle i warunki logiczne. Ze względu łatwość reprezentacji w systemie, symbol pusty będzie reprezentować 0, a jedyny symbol niepusty 1.

Użyjemy więc następujących bloków:

  1. Rozpoczęcia i zakończenia programu
  2. Blok zapisu i odczytu zmiennej:Blok zapisu do zmiennej umożliwia zapisanie stanu. Zmienną nazwaliśmy w naszym przypadku słowem “state”. Jest ona używana na początku programu ustawiając maszynę w stan początkowy oraz przy wykonywaniu funkcji przejścia wtedy gdy jest wymagana zmiana stanu. Blok odczytu umożliwia sprawdzenia aktualnego stanu maszyny. Jest on wykorzystywany przy funkcji przejścia oraz na końcu pętli w celu sprawdzenia, czy pętla ma się zakończyć (od razu po zakończeniu pętli następuje koniec programu).
  3. Bloki dużego silnika:Mają one pola odpowiedzialne za port, do jakiego jest podłączone urządzenie, moc, jaka ma być użyta przez silnik co się wiąże z czasem wykonania i o jaką część ma być wykonany obrót. Blok po lewej stronie odpowiada silnikowi odpowiedzialnemu za przesuwanie głowicy w prawo i lewo. Parametry zostały tak dobrane, aby przesuwać się co komórkę w sensownym czasie: port D, moc 30, obrót ±0,31. Drugi silnik (po prawej) odpowiada za zmianę symbolu w komórce. W zależności od zmiany symbolu 0⟶1 lub 1⟶0, dokonywany jest obrót w prawo lub lewo. Podłączony jest do portu C, moc ustawiona na 17 i obrót odpowiednio ±0,5. Oba silniki wykorzystujemy w funkcji przejścia.
  4. Blok średniego silnika:Średni silnik jest wykorzystywany do wysuwania i cofania urządzenia czytającego symbol z komórki, czyli fizycznie sprawdzającego, czy kolor jest czarny, czy inny. Silnik przed odczytaniem wartości wysuwa czujnik. Po tym, jak dokonany zostanie odczyt, silnik wsuwa z powrotem czujnik, aby w razie potrzeby zmiany symbolu nie kolidował on z tym mechanizmem. Parametry, które ustawiamy w tym urządzeniu, odpowiadają już wcześniej opisanemu dużemu silnikowi i dla tego przypadku mamy: port B, moc 13, obrót ±0,18.
  5. Blok czujnika kolorów:Czujnik kolorów umożliwia odczyt do 10 różnych kolorów. My jednak potrzebujemy tylko rozpoznania, czy aktualnie mamy czarny widoczny klocek, czy też go nie ma (w tym celu tło, czyli klocek pod spodem, jest białe). Powyższy blok umożliwia porównanie reprezentacji liczbowej koloru przez nas wybranego z tym, który jest dany przez czujnik. Dla odczytanego czarnego koloru (reprezentacja liczbowa 1) wykonujemy funkcje przejścia jak dla symbolu niepustego 1, a dla innego koloru jak dla symbolu pustego 0.
  6. Blok odpowiedzialny za pętlę:Aby program wykonał się cały, potrzebujemy funkcję przejścia wykonać wiele razy. Pętla zapewnia nam wykonywanie kolejnych iteracji aż do uzyskania stanu końcowego.
  7. Blok instrukcji switch:Blok instrukcji switch umożliwia podejmowanie decyzji, jakie akcje mają być wykonane w zależności od stanu maszyny w jakiej obecnie jest.
  8. Blok odpowiedzialny za porównanie:Blok porównania służy do sprawdzenia na końcu pętli czy maszyna Turinga nie jest w stanie końcowym i przekazuje tę informację do pętli.
  9. Blok wstrzymujący na podany czas:Blok wstrzymujący wykorzystujemy po to, aby czujnik kolorów, który dopiero co został przesunięty do odczytu, ustabilizował się i odczytał poprawną wartość. Stosujemy go zaraz po przesunięciu czujnika kolorów. Wartość podajemy w sekundach.Do opisu każdego programu będzie przedstawiona tabela stanów, a do pierwszych dodatkowo zostanie dodana grafika przedstawiająca program. Trudniejsze programy zostaną w miarę możliwości wyjaśnione w swoim działaniu. Wynikiem będzie zawsze wartość na taśmie po lewej stronie od głowicy. Dwa trudniejsze algorytmy, z powodu braku przykładów w literaturze, są wymyślone na potrzeby tej pracy.

Program

Poniżej kompletny program inkrementacji liczby.

W naszym programie polega on na dodaniu na końcu ciągu jedynek dodatkowej jedynki i w ten sposób zwiększamy wartość o jeden. Stan początkowy maszyny to q0, a końcowy to q2 i głowica powinna znajdować się nad komórką z symbolem niepustym.

A jak to wygląda w Lego Mindstorms EV3?

I to by było na tyle. 

Więcej koncepcji na programy dla maszyny Turinga przyniesie jak zwykle internet! Miłej zabawy!

Źródło zdjęć, tabel i wykresów: opracowanie własne autora.

2 comments

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

2 Comments

Inne artykuły