Wstęp
Maszyna Turinga jest najprostszym matematycznym modelem komputera. Czyli, pomimo swojej prostoty, jest w stanie wykonać dokładnie te same czynności, które może wykonać komputer. Wniosek: jeśli da się coś zrobić na maszynie turinga, da się to zrobić na komputerze, a jeśli się udowodni że na maszynie turinga czegoś nie można zrobić, na komputerze też się tego nie da, czyli maszyna przydaje się do badania obliczalności.
Sama maszyna składa się z nieskończonej taśmy, zawierającej komórki z danymi, po której przesuwa się głowica. Jeśli znajduje się w danej komórce taśmy, może wczytać z niej znajdujący się tam symbol, zamienić go na inny, oraz poruszać się w lewo i w prawo wzdłuż taśmy. Dodatkowo głowica ma komórkę pamięci – tam pamięta swój stan, który może oczywiście zmieniać.
Głowica działa według listy tzw. rozkazów. Rozkaz polega na wczytaniu symbolu z miejsca w którym znajduje się głowica, i na podstawie tego symbolu oraz obecnego stanu głowicy wykonania instrukcji – wpisania w to miejsce na taśmie nowego symbolu (bądź też nie), aktualizacji stanu głowicy (bądź nie) i ruchu (w prawo, w lewo, albo pozostania w miejscu). Jeśli jest to koniec programu, może zwrócić TAK lub NIE.
Schemat rozkazu. Dla rozróżnienia symbolu od stanu, stan umieśćmy w kółku. Poniżej jest jeszcze demonstracja.
(Na wszelki wypadek przypomnę że na sprawdzianie instrukcje do maszyny mają być napisane w taki właśnie sposób)
Głowica na początku znajduje się w pierwszej komórce taśmy. Instrukcje do maszyny, czyli program, mogą znajdować się na taśmie, tak że taśma wygląda tak: <program><dane>. Wtedy po wczytaniu każdego symbolu z danych głowica śmiga do instrukcji żeby zobaczyć co z tym fantem należy zrobić. Istnieją też inne warianty maszyny. Taśma może być jednostronnie skończona lub też nie, i może być więcej niż jedna taśma, ale takie wariacje raczej nie grożą pojawieniem się na sprawdzianie.
Problemy rozwiązywalne za pomocą maszyny Turinga
Tutaj jest parę przykładów problemów rozwiązywalnych za pomocą maszyny Turinga. Istnieją oczywiście rozwiązania inne. Rozkazy prezentuję tylko dla pierwszego przypadku, gdyż łatwo napisać je dla reszty.
Dodawanie
Mamy liczbę w zapisie binarnym, i chcemy dodać do niej 1. Umówmy się, że głowica już znajduje się na pierwszym znaku liczby, na k-tym polu taśmy.
Musimy więc ustalić rozkazy:
Najpierw musimy sprawdzić gdzie nasza liczba się kończy. Więc niech nasz stan początkowy informuje nas o tym że jeszcze nie osiągnęliśmy końca liczby. Tak więc, dopóki nie napotkamy znaku pustego, przesuwamy głowicę w prawo i nie zmieniamy stanu ani symboli.
Skoro znaleźliśmy puste pole, to znaczy że wyszliśmy poza liczbę. Skoro cała liczba znajduje się na lewo od nas, wystarczy że w najbliższą komórkę na lewo od nas w której znajduje się zero wpiszemy jedynkę, a wszystkie komórki z jedynkami ‘po naszej stronie’ tamtej zamienimy na zera. To jest chyba zresztą zbyt oczywiste żeby o tym mówić. Musimy się do niej wrócić. Zmieniamy stan, bo jak tego nie zrobimy, to odpali się od ostatniej komórki z cyfrą liczby poprzedni rozkaz, i się zapętli. Stan 2 będzie informował o tym, że już przesuwamy się w lewo.
Jest też przypadek,w którym liczba w zapisie binarnym składa się z samych jedynek – wtedy najprościej jest zostawić trochę miejsca po lewej stronie liczby, żeby dało się tam wpisać 1.
Demonstracja wizualna:
Powiedzmy że mamy fragment taśmy, z zerami, jedynkami i pustymi symbolami (oznaczmy je _). Niech głowica ma stan początkowy 1. Zaczynamy więc od takiej sytuacji. (Ta liczba w kółku to stan głowicy). Oznaczmy puste pola jako _ .
Blok rozkazów wygląda tak:
I co się stanie? Najpierw, zgodnie z pierwszymi dwoma rozkazami, głowica przesunie się aż do miejsca gdzie kończą się zera i jedynki. Wyląduje w komórce k+6, a stan będzie dalej 1.
Teraz wykona trzeci rozkaz, przesuwając się w lewo i zmieniając stan na 2.
Głowica jest w k+5 i tam napotyka jedynkę. Ponieważ następny symbol po lewej też jest jedynką, więc dwa razy wykona rozkaz czwarty od góry, wpisując w miejsce jedynek zera, aż osiągnie k+3. Wczytawszy zero wpisze tam jeden i zakończy swe działanie.
Analogicznie można zaimplementować odejmowanie. A skoro potrafimy dodawać do liczby 1, możemy to wykonać ile chcemy. Jeśli chcemy dodać n jedynek do liczby A, możemy po prostu gdzieś dalej na taśmie napisać binarnie liczbę n, i dopóki jest większa od zera, odejmujemy od niej 1 i 1 dodajemy do A.
Mnożenie
Możemy postąpić analogiczne do dodawania. Żeby pomnożyć liczby A i B, gdzieś dalej na taśmie umieszczamy początek liczby C, i wpisujemy 0. Teraz, dopóki A jest większe niż 0, od A odejmujemy 1, i do liczby C jeden raz dodajemy liczbę B. W ten sposób A razy dodajemy do siebie B.
Dopisanie liczby do siebie
Mamy na taśmie liczbę A. Chcemy dopisać jej cyfry obok siebie, żeby wyszła liczba AA. Długość liczby A nazwijmy n.
Porównywanie dwóch liczb
Mamy liczby A i B w zapisie binarnym. Muszą być napisane na taśmie: najpierw jedna, potem odstęp, i druga. Teraz odległość (ilość komórek taśmy) początku pierwszej od początku drugiej nazwijmy n. Teraz, zaczynając od pierwszej cyfry liczby A, robimy tak: oznaczamy obecną liczbę jako odwiedzoną,śmigamy n komórek do przodu, w ten sposób osiągamy pierwszą cyfrę liczby B. oznaczamy ją jako odwiedzoną, i porównujemy pierwszą cyfrę A i pierwszą cyfrę B. Możemy ustalić specjalny stan który pamięta czy w liczbie A mieliśmy 0 czy 1. Jeśli cyfry są te same, wracamy do pierwszej nieodwiedzonej cyfry w A, oznaczamy ją jako odwiedzoną, znów idziemy n pól do przodu aż do pierwszej nieodwiedzonej cyfry B, porównujemy, i powtarzamy to dopóki porównywane cyfry są takie same. Jeśli są różne – a wiemy że są to pierwsze które się różnią - to znaczy że jedna z cyfr jest większa, albo któraś z liczb się już skończyła. Teraz już możemy łatwo stwierdzić która z liczb A, B jest większa.
Rozpoznawanie palindromów
Mamy jakieś słowo A i chcemy sprawdzić czy jest palindromem. Jego długość oznaczmy jako n. Skoro jest palindromem, to pierwszy znak jest taki sam jak ostatni, drugi jest identyczny z przedostatnim, itd… Zaczynamy od pierwszej lirery, idziemy do ostatniej, sprawdzamy czy są identyczne. Jeśli są, zaznaczamy je jako odwiedzone. Potem robimy tak samo z każdą parą: pierwszą i ostatnią z nieodwiedzonych liter, dopóki wszystkie nie są odwiedzone. Jeśli gdzieś po drodze okaże się że dwie porównywane liczby są różne, słowo nie jest palindromem.
Rozpoznawanie, czy dane słowo jest w danym języku.
To też może zrobić maszyna Turinga. Przykład: Jak sprawdzić, czy słowo jest napisane w języku anbn ? Możemy, na przykład, sprawdzić czy jest tyle samo znaków a i znaków b.
Czego maszyna turinga nie jest w stanie zrobić?
Maszyną turinga nie jesteśmy, oczywiście, w stanie rozwiązać problemu na który nie można udzielić jednoznacznej odpowiedzi po wykonaniu skończonej liczby kroków. Takie problemy zwą się nierozstrzygalnymi.
Problem stopu
Czy, wczytawszy jakiś kod, maszyna turinga/komputer może stwierdzić czy on się wiesza nie odpalając go?
Nie, nie może. Dlaczego nie? Dowód jest następujący (mam nadzieję że nic nie pokręciłem):
Przypuśćmy że istnieje taka maszyna, nazwijmy ją A (jak Athina). Jej działanie niech będzie następujące: wczytuje kod programu <p>, sprawdza czy się wiesza, i jeśli się nie wiesza zwraca TAK, a jeśli się wiesza zwraca NIE. Teraz, przypuśćmy że istnieje maszyna B – złośliwa wersja Athiny. Niech ona działa tak: Gdy dany jest program <p>, zaczyna od jego podwojenia, tak że mamy <p><p>. Teraz każe maszynie A odpalić się na danych <p><p>. I jeżeli A zwróci na tych danych TAK, B się złośliwie zawiesi, a jeżeli A zwróci NIE, B zwróci TAK. No to teraz rozważmy, co się stanie jeśli B odpalimy na jej własnym kodzie <B>. Są dwie możliwości – albo B się na danych <B><B> wiesza, albo nie. Jeśli tak, to A zwróci NIE, i wtedy B zwróci tak, czyli twierdzi że się nie zapętla, co jest sprzecznością. Jeśli na swoim kodzi B się nie wiesza, A zwróci TAK, i B się zawiesi, co jest sprzecznością. Czyli B nie może odpowiedzieć dobrze. A ponieważ B wykonuje operacje możliwe do wykonania maszyną Turinga, wnioskujemy że nie może istnieć A.
Inne problemy nierozstrzygalne – Problem Posta, Dywany Wanga. Opisy wkrótce.
Złożoność
Złożoność czasową maszyny Turinga jest ilość ruchów, jakie wykona głowica, rozwiązując dany problem. Na przykład rozpoznanie palindromu ma złożoność O(n2).
