728 x 90

Programowanie maszyny Turinga z klocków LEGO

Programowanie maszyny Turinga z klocków LEGO

W poprzednim artykule stworzyliśmy maszynę Turinga. Teraz zaprezentuję kilka przykładowych implementacji. Do utworzenia programu wykorzystuję 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.

Jeśli chcesz przeczytać o budowie, zajrzyj tutaj.

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 na łatwość reprezentacji w systemie, symbol pusty będzie reprezentować 0, a jedyny symbol niepusty 1.

Sprawdzanie parzystości liczby

Sprawdzanie parzystości liczby polega na przechodzeniu po kolejnych symbolach niepustych, przestawianiu ich na symbol pusty wraz ze zmianą stanu, aż dojdziemy do symbolu 0. W zależności czy skończyliśmy na stanie q0, czy q1, odpowiednio zapisujemy symbol 1 lub pozostawiamy bez zmian obserwowaną komórkę. Jeśli taśma zostanie pusta, to liczba jest nieparzysta, a jeśli wartość w komórce po lewej jest 1, to oznacza to że liczba jest parzysta. W czasie działania programu liczba jest usuwana. Stan początkowy maszyny to q0, a końcowy to q2 i głowica może znajdować się nad komórką z dowolnym symbolem (komórkę z symbolem niepustym rozumiemy jako liczbę 0).

Tabela stanów

Program algorytmu parzystości

Dodawanie dwóch liczb

Dodawanie dwóch liczb oddzielonych symbolem pustym polega na wstawieniu symbolu 1 w komórkę oddzielającą liczby i zamianę w ostatniej komórce liczby na symbol 0. Początkowo maszyna przechodzi przez kolejne symbole pierwszej liczby w stanie q1 (tylko przy pierwszej komórce jest w stanie q0). Gdy dojdzie do końca liczby, tzn. symbolu pustego, zamienia go na 1 i zmienia swój stan na q2, po czym przechodzi całą drugą liczbę w tym stanie. Gdy dojdzie do końca zawraca zmieniając swój stan na q3 i po napotkaniu pierwszej komórki z symbolem niepustym zamienia go na symbol 0 i przechodzi do stanu końcowego. Stan początkowy maszyny to q0, a końcowy to q4 i głowica powinna znajdować się nad komórką z symbolem niepustym.

Tabela stanów

Program dodawania dwóch liczb

Odejmowanie dwóch liczb

Podany algorytm trochę różni się od zwyczajowo nam znanego odejmowania. Polega on na odjęciu liczby mniejszej od większej niezależnie od układu. Zasadniczo jest on po części wprowadzeniem do obliczania największego wspólnego dzielnika. Polega on na zdejmowaniu jedynek z zewnętrznych komórek, aż któraś z liczb wyzeruje się.

Na początku maszyna, będąca w stanie q0, zmienia symbol w pierwszej komórce i przechodzi w stan q1. W tym stanie przechodzi aż do końca liczby i jak natrafi na symbol pusty, to zmienia stan na q2 i przechodzi do końca drugiej liczby. Na znaku 0 maszyna zmienia swój stan na q3 i wraca, czyli przesuwa głowicę w drugą stronę. Gdy trafi na znak pusty oznacza to, że druga liczba została wyzerowana w poprzedniej iteracji i można zakończyć algorytm. Głowica zmienia stan komórki na 1 aby wyrównać wcześniej usunięty znak z pierwszej liczby i maszyna przechodzi w stan końcowy q9. Jeśli jednak odczytamy symbol niepusty, to zmieniamy go na 0 i zmieniamy stan na q4 i w tym stanie przechodzimy na początek drugiej liczby. Na komórce z symbolem pustym zmieniamy stan na q5 i przechodzimy dalej w lewo. Jeśli trafiliśmy na symbol pusty oznacza to, że pierwsza liczba została wyzerowana i możemy zakończyć algorytm. Przechodzimy w stan q7, a następnie przechodzimy przez drugą liczbę w stanie q8, po to aby według założeń wynik mieć po lewej stronie od głowicy. Na pierwszej komórce z zapisanym stanem 0 maszyna przechodzi w stan końcowy q9. Jeśli jednak w stanie q5 trafimy na symbol 1, to zmieniamy stan na q6 i przechodzimy na początek pierwszej liczby. Po trafieniu na symbol pusty zmieniamy stan na q0 i algorytm wykonuje się od początku. Liczba iteracji programu jest równa mniejszej z odejmowanych liczb. Stan początkowy maszyny to q0, a końcowy to q9 i głowica powinna znajdować się nad komórką z symbolem niepustym.

Tabela stanów

Obliczanie największego wspólnego dzielnika

Jako ostatni opiszę algorytm Euklidesa wyznaczania największego wspólnego dzielnika przez unarną maszynę Turinga. Jest to najbardziej złożone z przedstawionych tu zagadnień, jednak wcześniejszy algorytm odejmowania ułatwi jego zrozumienie. W tym algorytmie podczas odejmowania zapisujemy też jego wynik. W ten sposób zawsze mamy dwie liczby, które odejmujemy od siebie, aż do uzyskania pojedynczej liczby, która jest wynikiem.

Podobnie jak w odejmowaniu zaczynamy w stanie q0 na pierwszej niepustej komórce, zmieniamy go na q1 i przechodzimy pierwszą liczbę. Po napotkaniu symbolu 0 zmieniamy stan na q2 i przechodzimy drugą liczbę. Symbol pusty za liczbą zmieniamy na 1 i przechodzimy w lewo. Powinniśmy napotkać symbol niepusty (napotkanie symbolu pustego jest niemożliwe), zamieniamy go na 0 i przesuwamy głowicę dalej w lewo zmieniając stan na q4. Jeśli napotkamy symbol 1, to zmieniamy stan na q5 i przechodzimy drugą liczbę w lewo. Po napotkaniu symbolu pustego, zmieniamy stan na q6. Jeśli trafimy na symbol pusty (co oznacza, że pierwsza liczba została wyzerowana), to zmieniamy stan na q12. Na symbolu 0 (tylko taki możemy natrafić) zmieniamy stan na q0, po czym rozpoczynamy algorytm od początku. Jeśli w stanie q6 trafimy na symbol niepusty, to zmieniamy stan na q7 i przechodzimy pierwszą liczbę w lewo. Gdy natrafimy na symbol pusty, to zmieniamy stan na q0 i rozpoczynamy algorytm od początku. Jeśli w stanie q4 jednak napotkamy symbol pusty (oznacza to, że druga liczba została wyzerowana i powstała dwu komórkowa przerwa), to zmieniamy symbol na 1, przechodzimy w stan q8 (robimy to w celu przesunięcia pierwszej liczby o jeden w prawo). Jeśli trafimy na symbol 1, to maszyna zmienia stan na q11 i w tym stanie przechodzimy na początek pierwszej liczby. Na symbolu pustym maszyna zmienia stan na q12 i przechodzi w prawo na komórkę, która zawiera niepusty symbol, i zeruje go jednocześnie zmieniając swój stan na q0, po czym rozpoczynamy algorytm od początku. Jeśli jednak w stanie q8 trafimy na symbol 0 (oznacza to że pierwsza liczba także została wyzerowana), to zmieniamy stan na q9. W tym stanie wchodzimy na komórkę z wcześniej dodanym symbolem 1 i go zerujemy, a następnie trafiamy na komórkę z symbolem 0 i maszyna zmienia stan na q10. W stanie q10 przechodzimy na koniec jedynej pozostałej liczby i kończymy program. Stan początkowy maszyny to q0, a końcowy to q13 i głowica powinna znajdować się nad komórką z symbolem niepustym.

Tabela stanów

Podsumowanie projektu

Model maszyny Turinga, który jest opisem dość abstrakcyjnym i nie znajduje stricte zastosowania we współczesnych komputerach, można jednak przedstawić jako działające urządzenie. W tym projekcie zakładaliśmy przede wszystkim jego wartość edukacyjną i staraliśmy się, aby jego wykonanie było tak ukierunkowane. Zastosowanie klocków Lego wraz z układami logicznymi i urządzeniami wejścia/wyjścia sprawia, że maszyna Turinga staje się bliższa młodemu użytkownikowi. Także specyficzne środowisko programowania pozwala na łatwiejsze zrozumienie problemu. Daje to możliwość poznania maszyny Turinga i zmniejszenia bariery pomiędzy trudną do zdobycia wiedzą teoretyczną, a człowiekiem.

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

Źródło obrazów i tabel: opracowanie własne autora

Leave a Comment

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

Cancel reply

Inne artykuły