Turingi masina simulaator

Vaata, kuidas Turingi masin loeb, kirjutab ja liigub mööda lõpmatut linti, järgides üleminekureegleid.

Näidisarvutus — Turingi masina simulaator

Loe	'0'
Pea asukoht	0

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Üks lint teeb palindroomid ruutkasvuliseks 🖖

Palindroomi eelseade aktsepteerib 1,0,1,0,1 kahekümne ühe sammuga ja lükkab 1,0,1,1 tagasi kolmeteistkümnega. Masin ei saa kahte otsa korraga võrrelda, nii et see kustutab kõige vasakpoolsema sümboli, kannab seda oma olekus, kõnnib kogu lindi läbi, et kontrollida kõige parempoolsemat, kustutab selle ja kõnnib tagasi — üks kord paari kohta. n ühest koosneva lindi puhul kulub sellel programmil täpselt (n+1)(n+2)/2 sammu: 21 kui n = 5, 55 kui n = 9, 253 kui n = 21. Anna samale masinale teine lint ja töö muutub lineaarseks; Hennie tõestas 1965. aastal, et ühe lindiga see võimalik ei ole. Kulu ei peitu tähestikus ega olekute arvus — see peitub kõndimises.

Kuidas mõni reegel juhib kõike 🖖

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.

Töökas kobras kestab kauem kui universum 🖖

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.

Ülesanne täielikult lahendatud

Konfiguratsioonid, mida palindroomiprogramm läbib sisendil 1 0 1 0 1 5 sammu
Palindroomiprogramm alustab lindil 1 0 1 0 1, pea lahtril 0, olekus q0. Loenda reeglitabeli alusel — ilma programmi samm-sammult käitamata — iga konfiguratsioon, mille see enne peatumist läbib, ning ötle seejärel, mida see loendus teeb sisendi pikenemisel.
1. Loe tabelit voorudena, mitte käikude loendina. Ainult üks reegel saab vooru alustada: q0 kustutab vasakpoolseima sümboli ja hargneb vastavalt hiljuti kustutatule olekusse q1 sümboli 1 korral ja olekusse q2 sümboli 0 korral. See hargnemine ongi kogu võrdlusmehhanism. Masin ei salvesta sümbolit kunagi lindile; see salvestab selle olekusse, milles see viibib, mistõttu hilisem teise otsa kontrollimine selle suhtes ei nõua lisakäike.
  
  $q_{0} : 1 \mapsto (_, R, q_{1}), 0 \mapsto (_, R, q_{2})$
2. Arvuta ühe vooru kulu m sümboli pikkusel plokil. Vasaku otsa kustutamine on 1 käik. Pea läbib seejärel m − 1 allesolevat sümbolit ja kulutab 1 lisakäigu nendest tagapool asuval tühikul, et ümber pöörata. Parema otsa kustutamine on 1 käik, tagasiliikumine üle m − 2 ülejäänu on m − 2 käiku ning 1 viimane käik vasaku otsa tühikul suunab masina taas paremale olekus q0.
  
  $1 + (m - 1) + 1 + 1 + (m - 2) + 1 = 2 m + 1$
3. Meie lint annab 5-sümbolise ploki, seejärel 3-sümbolise ning siis üheainsa sümboli — ja üksik sümbol ei moodusta vooru. q0 kustutab selle, q1 liigub paremast otsast välja ja pöörab ümber ning q1c leiab tühiku sealt, kus peaks olema paariline. Paaritu pikkusega palindroomil on paariliseta keskoht ja selle tühiku leidmine viibki vastuvõtmiseni.
  
  $m = 5 : 11, m = 3 : 7, m = 1 : 3$
4. Liida need kolm kokku ja pea silmas aiapostiviga. 21 on käikude arv; üleminek loendab konfiguratsioone ning 21 käiku külastavad neist 22, kui lisada see, millest alustati.
  
  $11 + 7 + 3 = 21 ⟹ 21 + 1 = 22$
5. Üldista mis tahes paaritule pikkusele n. Plokid on pikkusega n, n − 2 ja nii edasi kuni 3-ni, igaüks kulukusega 2m + 1, kusjuures keskoht maksab 3. Selle loendi summeerimine annab ruutsõltuvuse n suhtes, mitte lineaarse.
  
  $(2 n + 1) + (2 n - 3) + \dots + 7 + 3 = \frac{( n + 1 ) ( n + 2 )}{2}$
Vastus

22 konfiguratsiooni — 21 käiku. Ruutsõltuvus on see osa, mida tasub meeles pidada. 21-sümboliline palindroom nõuab 253 käiku: 12 korda rohkem tööd 4,2 korda pikema sisendi korral. Põhjus on pigem geomeetriline kui nutikas — kaks võrreldavat sümbolit asuvad alati ülejäänud osa vastasotstes ning lugemispeasid on vaid üks, seega maksab iga paar ülejäänud lindi ühe täieliku läbimise. Anna masinale teine lint ja sama töö muutub lineaarseks: kopeeri sisend lugemise käigus teisele lindile, käita seejärel kahte pead vastassuundades ning võrdle ühe läbimisega, umbes 3n käiguga. Ühe lindiga pole seda koopiat kuhugi panna ning edasi-tagasi liikumine on paratamatu.

$n = 5 : 21; n = 21 : \frac{22 \cdot 23}{2} = 253$

Allikad (3)

The single-tape quadratic lower bound for palindromes: F. C. Hennie, "One-tape, off-line Turing machine computations." Information and Control 8(6), 553–578, 1965.
Where multi-tape time complexity classes were set out: J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms." Transactions of the American Mathematical Society 117, 285–306, 1965.
The machine itself: A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42(1), 230–265, 1937.

42Mathi meeskond · Uuendatud 2026-06-19

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

Bitiümberpööramine - Bitipööramine: vaheta 0-d ja 1-d
Binaarne +1 - Binaarne inkrementeerimine: 1011→1100
1111 → 10000 - Inkrementimisele saab ette anda halvima võimaliku sisendi: iga bitt on 1, seega peab ülekanne need kõik ümber pöörama. Jälgige, kuidas masin liigub paremale kuni tühikuni. Seejärel astub ta vasakule tagasi ja muudab iga 1 hoopis 0-ks. Viimaks kirjutab ta uue juhtiva 1 lahtrisse, mis ei kuulunud algsesse sisendisse. Kokku üksteist konfiguratsiooni ning lint naaseb ühe lahtri võrra pikemana, kui see sisse läks.
Unaarne m+n - Unaarne liitmine: 3+2=5
1+1 = 2 - Lihtsaim võimalik unaarne summa, kuid ikkagi kulub selleks üheksa konfiguratsiooni. Masin ei oska liita. Ta kustutab vasakpoolsest rühmast ühe 1, käib läbi kogu lindi ja lisab paremale ühe 1. Kord iga ühiku kohta. Kulu kasvab arvude suuruse, mitte nende tähistuse pikkusega. Laadige pikem unaarne eelseadistus ja lugege vahe kokku.
Palindroom ✓ - Palindroomikontroll: 10101
1011 — tagasi lükatud - Välimine paar klapib. Sõne algab ja lõpeb 1-ga, mistõttu masin kustutab mõlemad ja naaseb sisemise kihi juurde. Alles seal leiab ta 1 vastas oleva 0, siirdub tagasilükkavasse olekusse ja näidik nimetab reegli, mis selle põhjustas. Ühelindiline palindroomikontroll ei saa varakult katkeda. Just seetõttu nõuab iga paar lindi täielikku läbimist.

YouTube

The Rest Is Science·Alan Turing's Final Theory Was About Leopards