Stan
Kroki
Symbole na taśmie
Status

W stanie Czyta Pisze Ruch Następny stan

Więcej o maszynach Turinga

Symulator maszyny Turinga

Maszyna Turinga to najprostszy możliwy komputer: głowica, która czyta jeden symbol z nieskończonej taśmy, zapisuje symbol, przesuwa się o jedną komórkę w lewo lub w prawo i zmienia stan zgodnie z krótką tabelą reguł. Alan Turing wymyślił ją w 1936 roku i wszystko, co robi twój komputer, można w zasadzie zrobić w ten sposób. Napisz własne reguły albo wczytaj przykład, naciśnij Uruchom i obserwuj, jak taśma zmienia się krok po kroku, a pod nią diagram całej jej historii. Wybierz program albo napisz własny, wpisz dane wejściowe i naciśnij Uruchom albo Krok, aby śledzić po jednej regule naraz; Wstecz cofa krok. Każdy wiersz programu to jedna reguła: stan, odczytany symbol, symbol do zapisania, ruch (L, R lub N, gdy bez ruchu) i następny stan, na przykład A 0 -> 1 R B. Użyj _ dla pustej komórki. Maszyna zaczyna w stanie z pierwszej reguły, na pierwszym symbolu wejścia, i zatrzymuje się w H, accept lub reject albo wtedy, gdy żadna reguła nie pasuje. Diagram pokazuje taśmę po każdym kroku, od góry do dołu.

Jak to działa

  1. Wybierz przykładowy program albo napisz reguły takie jak A 0 -> 1 R B, po jednej w wierszu, i wpisz dane wejściowe.
  2. Naciśnij Uruchom, aby zobaczyć ruch głowicy, albo Krok, aby śledzić po jednej regule naraz; Wstecz cofa krok.
  3. Odczytaj stan, kroki i symbole na taśmie z kafelków, a historię taśmy z diagramu.

Jak działa maszyna

W każdej chwili maszyna jest w jednym z kilku stanów, a jej głowica stoi na jednej komórce taśmy. Reguła dla tego stanu i symbolu pod głowicą mówi trzy rzeczy: jaki symbol zapisać w komórce, czy przesunąć się w lewo, w prawo, czy wcale, i do jakiego stanu przejść dalej. To cała maszyna. Zatrzymuje się, gdy dojdzie do stanu końcowego, takiego jak H, accept lub reject, albo gdy żadna reguła nie pasuje. Program dodający 1 do liczby binarnej potrzebuje tylko dziewięciu takich reguł.

Pracowite bobry

Która maszyna z n stanami, uruchomiona na pustej taśmie, zapisze najwięcej jedynek, zanim się zatrzyma? To pytanie zadał Tibor Radó w 1962 roku. Mistrzów nazywa się pracowitymi bobrami (busy beavers), a ich wyniki rosną szybciej niż jakakolwiek funkcja, którą potrafi obliczyć komputer. Dwa stany dają 4 jedynki w 6 krokach, trzy stany 6 jedynek, cztery stany 13 jedynek w 107 krokach. Mistrz z pięcioma stanami, znaleziony w 1989 roku, zapisuje 4098 jedynek w 47 176 870 krokach, a w 2024 roku internetowa współpraca udowodniła za pomocą matematyki sprawdzonej komputerowo, że żadna inna zatrzymująca się maszyna z pięcioma stanami nie działa dłużej.

Często zadawane pytania

Jak napisać regułę?

Jedna reguła w wierszu: bieżący stan, odczytywany symbol, symbol do zapisania, ruch (L, R lub N) i następny stan, na przykład A 0 -> 1 R B. Strzałka i przecinki są opcjonalne. Użyj _ dla pustej komórki i # dla komentarza. Maszyna zaczyna w stanie z pierwszej reguły; następny stan o nazwie H lub halt zatrzymuje ją, a accept i reject zatrzymują ją z werdyktem.

Czy maszyna Turinga naprawdę może obliczyć wszystko?

Wszystko, co może obliczyć jakikolwiek komputer, jeśli ma dość taśmy i czasu: to teza Churcha–Turinga. Maszyna Turinga nie ma limitu pamięci, więc w tym sensie jest potężniejsza od każdego prawdziwego komputera, choć znacznie wolniejsza. Nie potrafi natomiast odpowiedzieć na każde pytanie: Turing udowodnił, że żadna maszyna nie rozstrzygnie dla każdego programu i każdego wejścia, czy program się zatrzyma.

Dlaczego licznik nigdy się nie zatrzymuje?

Jego reguły nigdy nie prowadzą do stanu końcowego. Ciągle dodaje 1 do liczby binarnej na prawym końcu taśmy i wraca, więc liczba rośnie bez końca. Problem stopu Turinga mówi, że żadna ogólna metoda nie rozstrzygnie dla każdej maszyny, czy się zatrzyma; w przypadku tego prostego licznika to widać, ale dla niektórych maszyn z zaledwie sześcioma stanami nikt jeszcze tego nie wie.

Jak pracowity bóbr z pięcioma stanami może tu wykonać 47 milionów kroków?

Taśma jest przechowywana jako zwarta tablica, która rośnie w obu kierunkach, a przy najszybszym ustawieniu aplikacja wykonuje setki tysięcy kroków między odświeżeniami ekranu, więc cały przebieg trwa kilka sekund w nowoczesnej przeglądarce. Diagram zapisuje tylko pierwsze 400 kroków, bo obraz z 47 milionami wierszy nie zmieściłby się na żadnym ekranie.

Czy coś jest wysyłane na serwer?

Nie. Program działa w twojej przeglądarce, a twój program i dane wejściowe zostają w lokalnej pamięci tej przeglądarki.

Chcesz wypróbować?

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

Przejdź do edytora