Maszyna Turinga | mysimulator.uk

Pięć części, nic więcej

Papier Alan Turinga z 1936 roku opisał najprostszą możliwą model liczącej maszyny, a okazało się, że jest ona wystarczająco mocna, aby określić, co oznacza "obliczalne". Maszyna Turinga ma nieskończoną tapecję podzieloną na komórki, każda z której zawiera symbol z ograniczonego alfabetu; głowicę, która czyta i pisanie jednej komórki za tym razem oraz może poruszać się w lewo lub prawo; skończony zestaw stanów wewnętrznych; oraz tabelę przejść, która dla każdego par (stan, symbol) mówi, który symbol należy napisać, w którą stronę poruszyć się i jaki stan wejśćowy powinien być.

transition rule:  (state, read) → (write, move, next_state)

example — binary increment, rightmost bit first:
(scan, 0) → (0, RIGHT, scan)
(scan, 1) → (1, RIGHT, scan)
(scan, _) → (_, LEFT,  carry)
(carry,1) → (0, LEFT,  carry)
(carry,0) → (1, LEFT,  halt)

demo na żywo · powiązana symulacja● LIVE

Dlaczego coś tak prostej może obliczyć wszystko

Maszyna nie ma wbudowanej arytmetyki, ani pamięci poza tapecją, a także nie ma pojęcia o liczbach, pętlach ani zmiennych — te wszystkie elementy muszą być zakodowane jako symbole i stanów. Jednak Turing pokazał, że ta podstawowa mechanizm może symulować dowolną inną maszynę Turinga, dając opis jej na tapecji (universalna maszyna Turinga), a Church i Turing niezależnie argumentowali, że wszystko, co mógłby obliczyć człowiek, wykonując algorytm, również mogłaby obliczyć maszyna Turinga — teza Churcha-Turinga. Nie znaleziono nigdy modelu obliczeniowego silniejszego; każda ogólnopurpose język programowania, niezależnie od toksycy, jest dowodowo równoważna w tym, co może obliczyć.

Problem zatrzymania

Papier Turiainga koncentruje się naprawdę na wyniku negatywnym. Udowodnił, że nie ma algorytmu, który mógłby dla każdego możliwego automatu i wejścia ustalić, czy automat zatrzyma się w końcu lub będzie działał nieskończenie dalej. Dowód jest argumentem przekątny: załóżmy, że istnieje decydent zatrzymania H, a następnie stwórz automat, który pyta H o siebie i robi przeciwko temu, co H zapewnia — to prowadzi do sprzeczności, więc H nie może istnieć. Ten pojedynczy wynik podstawia się za dlaczego kompilatory nie mogą zawsze wykrywać nieskończonych pętli, dlaczem niektóre pytania zweryfikowania programu są dowodowo niewzględne i dlaczego zachowanie długoterminowe Gry Życia jest wogóle nieokreślone (może symulować maszynę Turinga).

Jastrzębie zające: cena prostej struktury

Jeśli ograniczymy maszynę Turinga do małej liczby stanów, jak dużo jeszcze może zrobić przed zatrzymaniem się? Funkcja jastrzębia-zajacza BB(n) pyta o maksymalną liczbę kroków (lub 1s napisanych) jakie może wykonać maszyna o n stanach i 2 symbolach, która zatrzymuje się. BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107 są znane dokładnie; BB(5) została ustalona dopiero w 2024 roku po latach poszukiwań, wynosząc 47,176,870 kroków. Poza tym funkcja rośnie szybciej niż dowolna z liczebnie wyliczalnych funkcji — dokładne obliczenie jej wartości jest równoznaczne z rozwiązaniem problemu zatrzymania się, dlatego BB(n) jest formalnie niewyliczalny dla wystarczająco dużych n. Ilość dodatkowych stanów jest w stanie kupić prawie nieograniczoną liczbę możliwych zachowań.

Co symulator na tej stronie uruchamia

Pięć wbudowanych programów to małe, ręcznie zaprojektowane tabele przejść: inkrementacja binarna (propagacja carry po bitach, pokazana powyżej), dodawanie unarno (połączenie dwóch ciągów znaków w jeden), sprawdzacz palindromu (poruszający się z obu końców taśmy do środka i porównujący symbole), kopierowanie ciągu (przenoszenie markeru to i fro, aby podwójić blok) oraz trzystaetapowy beaver zajęty, który mimo tylko trzech etapów i dwóch symboli zapisuje sześć jedynek przed zatrzymaniem — maksymalny taki automat, dowolnie udowodniony jako optymalny w poszukiwaniach wy🙂ciornych kilkaset lat temu.

Często zadawane pytania

Czy prawdziwy komputer jest tylko dużym maszyną Churcha-Turinga?

Z punktu widzenia tego, co może obliczyć, tak — każdy fizyczny komputer z nieograniczonej pamięci jest równoważny w mocy Turingowi (tesis Churcha-Turinga). Prawdziwe komputery różnią się tylko prędkością i skończoną ilością pamięci, a nie tymi problemami, które mogą rozwiązać w zasadzie.

Dlaczego program nie może sprawdzić, czy inny program zatrzyma się?

Turing udowodnił, że to niemożliwe w ogólności poprzez kontradukcję self-referencyjną: gdyby istniała maszyna sprawdzająca zatrzymanie, mógłaby być użyta do stworzenia maszyny, która gwarantuje, że robi exact przeciwnie do prognozy sprawdzacza o własnym zachowaniu. Brak jest algorytmu, który mógłby rozwiązać każdą sytuację.

Co sprawia, że liczby bezezwodnika są tak trudne do obliczenia?

Znalezienie najdłuższej działającej maszyny zatrzymującej się z n stanami wymaga wykluczenia, że każdy inny kandydat na maszynę ma zatrzymanie wcześniej lub nigdy nie zatrzymuje się — a decydując o niezatrzymaniu, dokładnie jest problem zatrzymania nierozstrzygalny, więc funkcja rośnie szybciej niż dowolna obliczalna formuła wraz ze wzrostem n.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Turing Machine i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Turing Machine

Maszyna Turinga: Proste modelowanie wszystkich obliczeń