| W stanie | Czyta | Pisze | Ruch | Następny stan |
|---|
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
- Wybierz przykładowy program albo napisz reguły takie jak A 0 -> 1 R B, po jednej w wierszu, i wpisz dane wejściowe.
- Naciśnij Uruchom, aby zobaczyć ruch głowicy, albo Krok, aby śledzić po jednej regule naraz; Wstecz cofa krok.
- 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