| În starea | Citește | Scrie | Mișcare | Starea următoare |
|---|
Simulator de mașină Turing
O mașină Turing este cel mai simplu computer posibil: un cap care citește un simbol de pe o bandă nesfârșită, scrie un simbol, se mută cu o celulă la stânga sau la dreapta și își schimbă starea, după un tabel scurt de reguli. Alan Turing a inventat-o în 1936 și tot ce face computerul dumneavoastră poate fi făcut, în principiu, în acest fel. Scrieți propriile reguli sau încărcați un exemplu, apăsați Rulează și urmăriți cum se schimbă banda pas cu pas, cu o diagramă a întregii ei istorii dedesubt. Alege un program sau scrie-l pe al tău, introdu intrarea și apasă Rulează, sau Pas pentru a urmări câte o regulă pe rând; Înapoi anulează un pas. Fiecare linie a programului este o regulă: starea, simbolul citit, simbolul de scris, mișcarea (L, R sau N pentru nicio mișcare) și starea următoare, de exemplu A 0 -> 1 R B. Folosește _ pentru o celulă goală. Mașina pornește în starea primei reguli, pe primul simbol al intrării, și se oprește în H, accept sau reject ori atunci când nicio regulă nu se potrivește. Diagrama arată banda după fiecare pas, de sus în jos.
Cum funcționează
- Alegeți un program exemplu sau scrieți reguli ca A 0 -> 1 R B, câte una pe linie, și introduceți intrarea.
- Apăsați Rulează pentru a vedea capul mișcându-se sau Pas pentru a urmări câte o regulă pe rând; Înapoi anulează un pas.
- Citiți starea, pașii și simbolurile de pe bandă în casete, iar istoria benzii în diagramă.
Cum funcționează mașina
În fiecare moment, mașina se află într-una dintre câteva stări, iar capul ei stă pe o celulă a benzii. Regula pentru acea stare și pentru simbolul de sub cap spune trei lucruri: ce simbol să scrie în celulă, dacă să se mute la stânga, la dreapta sau deloc și în ce stare să treacă apoi. Aceasta este toată mașina. Se oprește când ajunge într-o stare de oprire, precum H, accept sau reject, sau când nicio regulă nu se potrivește. Un program care adună 1 la un număr binar are nevoie de doar nouă astfel de reguli.
Castori harnici
Care mașină cu n stări, pornită pe o bandă goală, scrie cele mai multe cifre de 1 înainte de a se opri? Tibor Radó a pus această întrebare în 1962. Campionii se numesc castori harnici (busy beavers) și cresc mai repede decât orice funcție pe care o poate calcula un computer. Două stări dau 4 cifre de 1 în 6 pași, trei stări 6 cifre de 1, patru stări 13 cifre de 1 în 107 pași. Campionul cu cinci stări, găsit în 1989, scrie 4.098 de cifre de 1 în 47.176.870 de pași, iar în 2024 o colaborare online a demonstrat, cu matematică verificată de computer, că nicio altă mașină cu cinci stări care se oprește nu rulează mai mult.
Întrebări frecvente
Cum scriu o regulă?
O regulă pe linie: starea curentă, simbolul citit, simbolul de scris, mișcarea (L, R sau N) și starea următoare, de exemplu A 0 -> 1 R B. Săgeata și virgulele sunt opționale. Folosiți _ pentru o celulă goală și # pentru un comentariu. Mașina pornește în starea primei reguli; o stare următoare numită H sau halt o oprește, iar accept și reject o opresc cu un verdict.
Poate o mașină Turing să calculeze chiar orice?
Tot ce poate calcula orice computer, dacă are suficientă bandă și timp: aceasta este teza Church–Turing. O mașină Turing nu are limită de memorie, așa că, în acest sens, este mai puternică decât orice computer real, deși mult mai lentă. Ce nu poate face este să răspundă la orice întrebare: Turing a demonstrat că nicio mașină nu poate decide, pentru orice program și orice intrare, dacă programul se va opri.
De ce nu se oprește niciodată contorul?
Regulile lui nu duc niciodată la o stare de oprire. Adună mereu 1 la un număr binar de la capătul din dreapta al benzii și se întoarce, așa că numărul crește la nesfârșit. Problema opririi a lui Turing spune că nicio metodă generală nu poate stabili, pentru orice mașină, dacă se va opri; la acest contor simplu se vede, dar pentru unele mașini cu doar șase stări nimeni nu știe încă.
Cum poate castorul harnic cu cinci stări să ruleze aici 47 de milioane de pași?
Banda este stocată ca un tablou compact care crește în ambele direcții, iar la setarea cea mai rapidă aplicația rulează sute de mii de pași între două actualizări ale ecranului, așa că întreaga rulare durează câteva secunde într-un browser modern. Diagrama înregistrează doar primii 400 de pași, deoarece o imagine cu 47 de milioane de rânduri nu ar încăpea pe niciun ecran.
Se trimite ceva la un server?
Nu. Programul rulează în browserul dumneavoastră, iar programul și intrarea dumneavoastră rămân în spațiul de stocare local al acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor