Turingi masina simulaator

Turingi masin on arvutuse formaalne matemaatiline mudel, mis koosneb lõpmatust lindist, lindipeast ja olekute üleminekute tabelist. See määratleb arvutatavuse piirid (Church-Turingi tees). Staatiliselt tõestab see peatumisprobleemi lahendamatust, näidates, et ükski üldine algoritm ei suuda prognoosida, kas programm töötab igavesti või peatub.

Turingi masinas pole peaaegu midagi: lint, pea, mis loeb üht lahtrit, ja lühike reeglitabel. Igal sammul vaatab ta ainult oma praegust olekut ja pea all olevat sümbolit, seejärel kirjutab sümboli, liigub ühe lahtri võrra vasakule või paremale ja vahetab olekut. Käivita kahendarvu inkrementimise eelseade ja jälgi, kuidas ta libiseb paremale lõpuni ning kannab +1 tagasi vasakule — täpselt nagu käsitsi liites.

Küsi kõige väiksem küsimus — kui kaua saab pisike masin töötada, enne kui ta peatub? — ja arvutus plahvatab. Masin, millel on 5 olekut ja 2 sümbolit, teeb enne peatumist täpselt 47,176,870 sammu; see väärtus tõestati alles 2024. Kuue oleku puhul ületab teadaolev rekord (busy beaver) juba 2↑↑↑5 — astmetorn, mille kõrval kahvatub iga aatom universumis. Seepärast piiravad sellised simulaatorid iga käivitust: käputäis olekuid võib kesta kauem kui igavik.