Maszyny Turinga wyjaśnione

W 1936 roku, zanim powstały komputery elektroniczne, 24-letni matematyk Alan Turing zapytał, co znaczy, że obliczenie jest mechaniczne. Jego odpowiedzią była wyobrażona maszyna tak prosta, że trudno, by robiła mniej: czyta i zapisuje symbole na taśmie, po jednej komórce naraz, według stałej tabeli reguł. Okazało się, że ta maszyna definiuje samo pojęcie obliczenia, a do tego pokazała, że na niektóre pytania żaden komputer nigdy nie odpowie.

Taśma z komórkami zawierającymi jedynki i puste pola, z głowicą odczytująco-zapisującą nad jedną komórką, opisaną swoim stanem
Taśma z komórkami zawierającymi jedynki i puste pola, z głowicą odczytująco-zapisującą nad jedną komórką, opisaną swoim stanem

Pytanie Turinga

W 1928 roku David Hilbert zapytał, czy istnieje mechaniczna procedura, która dla każdego zdania matematycznego rozstrzyga, czy da się je udowodnić: Entscheidungsproblem. Aby na to odpowiedzieć, ktoś musiał dokładnie powiedzieć, czym jest mechaniczna procedura. W swojej pracy On Computable Numbers z 1936 roku Turing wyobraził sobie urzędnika pracującego z ołówkiem i papierem i sprowadził tę pracę do najmniejszych kroków: spójrz na jeden symbol, zmień go, przejdź do sąsiedniego symbolu i zapamiętaj trochę o tym, co robiłeś. Wynikiem była maszyna Turinga.

Maszyna Bombe (po lewej) i portret Alana Turinga (po prawej)
Maszyna Bombe (po lewej) i portret Alana Turinga (po prawej)

Maszyna

Maszyna Turinga ma taśmę podzieloną na komórki, nieskończoną w obu kierunkach; każda komórka zawiera jeden symbol, zwykle pusty. Głowica stoi na jednej komórce, a maszyna jest w jednym ze skończenie wielu stanów. Tabela reguł podaje dla każdego stanu i każdego symbolu, który głowica może odczytać, symbol do zapisania, kierunek ruchu i następny stan. Maszyna stosuje jedną regułę na krok. Gdy wejdzie w stan końcowy, zatrzymuje się, a to, co zostało na taśmie, jest jej odpowiedzią.

Programy jako tabele reguł

Każda tabela reguł jest programem. Aby dodać 1 do liczby binarnej, maszyna idzie na prawy koniec liczby, a potem przesuwa się w lewo, zamieniając jedynki w zera, aż znajdzie 0 lub puste pole, które zamienia w 1. Aby sprawdzić, czy słowo jest palindromem, wymazuje pierwszy symbol, zapamiętuje go w swoim stanie, biegnie na drugi koniec i sprawdza, czy ostatni symbol się zgadza, po czym powtarza. Długie programy, na przykład mnożące lub sortujące, buduje się z tych samych kilku rodzajów reguł.

Maszyna uniwersalna

Najważniejszym pomysłem Turinga było to, że samą tabelę reguł można zapisać na taśmie. Uniwersalna maszyna Turinga czyta opis dowolnej innej maszyny i jej wejście, a potem naśladuje ją krok po kroku. Jedna stała maszyna może więc wykonać każdy program: na tej zasadzie działa każdy komputer z programem przechowywanym w pamięci, w którym oprogramowanie to po prostu dane. Każdy system, który potrafi naśladować uniwersalną maszynę Turinga, nazywa się zupełnym w sensie Turinga; należą do nich wszystkie języki programowania, Gra w życie Conwaya i automat komórkowy Reguła 110.

Teza Churcha–Turinga

W tym samym roku Alonzo Church opisał obliczenia za pomocą swojego rachunku lambda i okazało się, że obie definicje obliczają dokładnie te same funkcje. Tak samo było z każdym późniejszym modelem, od maszyn rejestrowych po nowoczesne procesory. Teza Churcha–Turinga głosi, że wszystko, co można obliczyć za pomocą procedury krok po kroku, może obliczyć maszyna Turinga. Nie da się jej udowodnić, bo „procedura krok po kroku” to pojęcie nieformalne, ale nigdy nie znaleziono kontrprzykładu.

Problem stopu

Następnie Turing pokazał, że na niektóre pytania nie ma mechanicznej odpowiedzi. Załóżmy, że jakaś maszyna potrafi rozstrzygnąć dla każdego programu i każdego wejścia, czy program w końcu się zatrzyma. Zbudujmy nowy program, który pyta ten rozstrzygacz o siebie samego, a potem robi odwrotnie: jeśli usłyszy, że się zatrzyma, zapętla się na zawsze, a jeśli usłyszy, że się zapętli, zatrzymuje się. Każda odpowiedź jest błędna, więc rozstrzygacz nie może istnieć. Problem stopu jest nierozstrzygalny, a wraz z nim Entscheidungsproblem: żaden algorytm nie rozstrzygnie każdego pytania matematycznego.

Pracowite bobry

W 1962 roku Tibor Radó zamienił problem stopu w grę: spośród wszystkich maszyn z n stanami i symbolami 0 i 1, które zatrzymują się po uruchomieniu na pustej taśmie, która zapisuje najwięcej jedynek i ile kroków może wykonać taka maszyna? Te liczby, wartości pracowitego bobra, rosną szybciej niż jakakolwiek funkcja obliczalna, bo sposób ich obliczania rozwiązałby problem stopu. Znane wartości to 6, 21 i 107 kroków dla dwóch, trzech i czterech stanów; dla pięciu stanów mistrz Heinera Marxena i Jürgena Buntrocka wykonuje 47 176 870 kroków, a wartość tę udowodniła w 2024 roku internetowa współpraca bbchallenge za pomocą dowodu sprawdzonego komputerowo. Dla sześciu stanów znane są maszyny, które wykonują więcej kroków, niż da się zapisać w zwykłej notacji.

Wypróbuj

Otwórz symulator maszyny Turinga, aby uruchomić osiem gotowych programów albo napisać własny. Śledź głowicę krok po kroku i patrz, która reguła zostaje użyta, obserwuj licznik, który nigdy się nie zatrzymuje, sprawdzaj palindromy i uruchamiaj pracowite bobry: 107 kroków mistrza z czterema stanami mieści się na diagramie, a 47 milionów kroków mistrza z pięcioma stanami zajmuje kilka sekund przy najwyższej prędkości.

Często zadawane pytania

Czy maszynę Turinga kiedykolwiek zbudowano?

Nie w takiej postaci, w jakiej opisał ją Turing, bo jej taśma jest nieskończona, ale za tą ideą szybko poszły prawdziwe komputery z programem przechowywanym w pamięci, które Turing sam pomagał projektować po II wojnie światowej. Od tamtej pory hobbyści zbudowali działające modele z drewna, z LEGO, a nawet w Grze w życie, wszystkie ze skończoną taśmą, co wystarcza do każdego obliczenia, które się kończy.

Czym różnią się liczby kroków 14 i 21 dla trzech stanów?

Istnieją dwa pytania o pracowite bobry: o najwięcej zapisanych jedynek i o najwięcej wykonanych kroków. Dla trzech stanów maszyna w symulatorze zapisuje maksymalnie sześć jedynek w 14 krokach, a inna maszyna z trzema stanami wykonuje maksymalnie 21 kroków, ale zostawia tylko pięć jedynek. Dla dwóch, czterech i pięciu stanów jedna maszyna wygrywa w obu kategoriach.

Czy zupełność w sensie Turinga oznacza dużą moc?

Oznacza zdolność do obliczenia wszystkiego, co obliczalne, przy dostatecznej ilości czasu i pamięci, co nic nie mówi o szybkości. Maszyna Turinga potrzebuje wielu kroków do prostej arytmetyki, a niektóre systemy są zupełne w sensie Turinga niemal przypadkiem, na przykład gry karciane, formuły arkuszy kalkulacyjnych i redstone w Minecrafcie.

Dlaczego komputer nie może po prostu uruchomić programu i sprawdzić, czy się zatrzyma?

Uruchomienie pokazuje, że program się zatrzymuje, jeśli tak jest, ale jeśli jeszcze się nie zatrzymał, nie wiadomo, czy nie zatrzyma się nigdy, czy po prostu potrzebuje więcej czasu. Dowód Turinga pokazuje, że żadna sprytniejsza metoda nie działa dla każdego programu, choć dla wielu konkretnych programów da się odpowiedzieć na to pytanie.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz symulator maszyny Turinga