Izraz po 1920-ih Računski stroj se nanaša na kateri koli stroj, ki je opravil delo človeški računalnik, zlasti tistim, ki so bili razviti v skladu z učinkovite metode Cerkev - Turingova teza. Ta teza je oblikovana tako: "Vsak algoritem je mogoče podati v obliki ustreznega Turingovega stroja ali delno rekurzivne definicije, razred izračunanih funkcij pa sovpada s razredom delno rekurzivnih funkcij in z razredom funkcij, ki jih je mogoče izračunati na Turingovih strojih . " Z drugimi besedami, Church-Turingova teza je opredeljena kot hipoteza o naravi mehanskih računalniških naprav, kot so elektronski računalniki. Vsak možen izračun je mogoče izvesti v računalniku, če je na voljo dovolj časa in prostora za shranjevanje.

Mehanizmi, ki delujejo na računalništvu z neskončnostmi, so postali znani kot analogni tip. Vrednosti v takšnih mehanizmih so bile predstavljene z neprekinjenimi numeričnimi vrednostmi, na primer kotom vrtenja gredi ali razliko v električnem potencialu.

Za razliko od analognih strojev so imeli digitalni stroji možnost prikazati stanje numerične vrednosti in shraniti vsako številko posebej. Digitalni stroji so pred izumom RAM -a uporabljali različne procesorje ali releje.

Ime Računski stroj od štiridesetih let prejšnjega stoletja ga je koncept začel izpodrivati Računalnik... Ti računalniki so lahko naredili izračune, ki so jih delali uradniki. Ker trenutne vrednosti niso bile več odvisne od fizičnih lastnosti (tako kot pri analognih strojih), je logični računalnik, ki temelji na digitalni strojni opremi, zmogel narediti vse, kar je bilo mogoče opisati. čisto mehanski sistem .

Turingovi stroji so bili oblikovani tako, da formalno matematično opredelijo, kaj je mogoče izračunati glede na omejitve računalniške moči. Če lahko Turingov stroj opravi nalogo, potem se ta naloga šteje za Turingovo izračunano. Turing se je osredotočal predvsem na oblikovanje stroja, ki bi lahko določil, kaj bi lahko izračunali. Turing je zaključil, da dokler obstaja Turingov stroj, ki lahko izračuna približek števila, je ta vrednost šteta. Poleg tega lahko Turingov stroj interpretira logične operaterje, kot so AND, OR, XOR, NOT in If-Then-Else, da ugotovi, ali

Pogosto rešujemo probleme različne kompleksnosti: vsakodnevne, matematične itd. Nekatere je enostavno rešiti, nekatere moramo veliko razmišljati, za nekatere nikoli ne najdemo rešitve.

V splošnem lahko način reševanja problema (če obstaja) opišemo s končnim številom osnovnih dejanj.

Na primer reševanje kvadratne enačbe:

Enačbo pripeljimo v kanonično obliko \ (a x ^ 2 + b x + c = 0 \)
Če \ (a = 0 \), potem to linearna enačba z rešitvijo \ (x = \ frac (-c) (b) \). Problem je rešen. V nasprotnem primeru pojdite na korak 3.
Izračunajte diskriminatorno \ (D = b ^ 2-4 a c \)
Izračunajte rešitve enačbe \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... Problem je rešen.

Lahko predstavite naslednji intuitivni koncept algoritma:

Algoritem je niz navodil, ki opisujejo vrstni red dejanj izvajalca za dosego rezultata reševanja problema v končnem številu dejanj za kateri koli niz začetnih podatkov.

To seveda ni stroga opredelitev, opisuje pa bistvo koncepta algoritma.

Algoritmi so sestavljeni na podlagi določenega izvajalec in ga je zato treba pripraviti v jeziku, ki ga izvajalec razume.

Izvajalec algoritma je lahko oseba ali pa računalnik ali kakšen drug stroj, na primer statve.

Poudarjene so naslednje lastnosti algoritmov:

Diskretnost algoritma mora biti določeno zaporedje ločenih, jasno opredeljenih korakov (dejanj). Vsako od teh dejanj mora biti časovno omejeno. Odločnost na vsakem koraku algoritma, naslednji korak je enolično določen s trenutnim stanjem sistema. Posledično na istih začetnih podatkih algoritem vsakič vrne enake rezultate, ne glede na to, kolikokrat se izvede. Razumljivost Algoritem mora biti oblikovan v jeziku, razumljivem izvajalcu. Če prihaja v računalniku mora algoritem uporabljati le tiste ukaze, ki so računalniku znani in katerih rezultat je strogo določen. Končnost algoritma mora dokončati v končnem številu korakov. Masovnost algoritma bi morala veljati za različne nabore vhodnih podatkov. Z drugimi besedami, algoritem mora biti primeren za reševanje razred naloge. Če se vrnem na kvadratni primer, je algoritem primeren za reševanje od vseh kvadratne enačbe, ne samo enega ali več. Učinkovitost algoritma se mora končati z določenim rezultatom. Recimo tako, da rešite težavo ali ugotovite, da rešitev ni. Če algoritem ne vodi do rezultata, ni jasno, zakaj je sploh potreben.

Algoritem ni vsak način za rešitev problema. Recimo, da algoritem ne pomeni izbire. Večina receptov na primer ni algoritem, ker uporabljajo stavke, kot je »sol po okusu«. Posledično je kršena zahteva po determinizmu.

Ne za vsak problem, za katerega obstaja rešitev, obstaja tudi algoritem za rešitev. Na primer, problem prepoznavanja slik je še vedno v veliki meri nerešen in zagotovo ne uporablja strogega algoritma. Vendar pa uporaba nevronskih omrežij daje precej dobre rezultate.

Običajno obstajajo algoritmi dovoljeno vnos podatkov. Čudno bi bilo poskusiti uporabiti algoritem za reševanje enačb za pripravo večerje ali obratno.

Poleg tega je nabor možnih dejanj izvajalca tudi omejen, saj če bi bila katera koli dejanja dovoljena, bi morala biti med njimi tudi "nesprejemljiva".

Opredelitev strogega algoritma

Opredelitev zgornjega algoritma ni stroga. To ustvarja nekatere težave. Zlasti s takšno definicijo ni mogoče strogo dokazati, ali je dani razred težav rešljiv z algoritmom.

Izkazalo se je, da obstaja razred algoritmično nerešljive težave- težave, za katere ni mogoče sestaviti algoritma rešitev. Toda, če želite strogo dokazati algoritmično nerazrešljivost, morate najprej natančno opredeliti algoritem.

V 20-30-ih letih 20. stoletja so se razni matematiki ukvarjali s problemom stroge opredelitve algoritma, zlasti Alan Turing, Emil Leon Post, Andrej Andreevič Markov, Andrej Nikolajevič Kolmogorov, Alonzo Church in drugi. Njihovo delo je sčasoma pripeljalo do nastanka in razvoja teorije algoritmov, teorije računa in različnih pristopov k izračunu ter, mimogrede, programiranja na splošno. Eden od rezultatov njihovega dela je bil pojav več strogih definicij algoritma, uvedenih na različne načine, vendar enakovrednih med seboj.

Podrobno se bomo osredotočili na Turingovo definicijo in površno analizirali enakovredne definicije Post, Church in Markov.

Turingov stroj

Za uvedbo formalne definicije algoritma je Turing prišel in opisal abstraktni računalniški stroj, imenovan Turingov računalniški stroj ali preprosto Turingov stroj.

Alan Turing (1912-1954)

Angleški matematik, logik, kriptograf, morda prvi "heker" na svetu, je bil pri izvoru računalništva in teorije umetne inteligence. Pomembno je prispeval k zmagi zavezniških sil v drugi svetovni vojni.

Vhodni podatki za Turingov stroj so besede sestavljeno s pomočjo določenega abeceda, torej komplet znakov.

Rezultat dela Turingovega stroja so tudi besede.

Beseda, za katero se uporablja algoritem, se imenuje vnos... Beseda, ki prihaja iz dela vikend.

Niz besed, za katere se uporablja algoritem, se imenuje obseg algoritma.

Strogo gledano, nemogoče je dokazati, da je kateri koli predmet lahko predstavljen v obliki besed, sestavljenih v neki abecedi - za to bi potrebovali strogo opredelitev predmeta. Lahko pa preverite, ali je mogoče kateri koli naključni algoritem, ki deluje na objektih, spremeniti tako, da deluje na besedah, ne da bi spremenil bistvo algoritma.

Opis Turingovega stroja

Turingov stroj vključuje neomejen trak v obeh smereh, razdeljen na celice, in krmilno napravo (imenovano tudi glava za branje in pisanje ali preprosto stroj), ki je lahko v eni od mnogih držav. Število možnih stanj krmilne naprave je omejeno in natančno določeno.

Krmilna naprava se lahko premika levo in desno po traku, bere in zapisuje znake neke končne abecede v celice. Dodeljen je poseben prazen znak, označen z \ (a_0 \) ali \ (\ Lambda \), ki zapolni vse celice traku, razen tistih (omejeno število), na katere so zapisani vhodni podatki.

Krmilnik deluje v skladu s prehodnimi pravili, ki predstavljajo algoritem, ki ga izvaja določen Turingov stroj. Vsako pravilo prehoda naloži stroju, odvisno od trenutnega stanja in simbola, opaženega v trenutni celici, da v to celico vpiše nov simbol, preklopi v novo stanje in premakne eno celico v levo ali desno. Nekatera stanja Turingovega stroja lahko označimo kot terminalna in prehod na katero koli od njih pomeni konec dela, ustavitev algoritma.

Čeprav je Turingov stroj abstrakten koncept, je dovolj, da si tak stroj (čeprav s končnim trakom) preprosto predstavljamo, obstajajo pa celo takšni demo stroji:

Algoritem za Turingov stroj je priročno predstaviti v obliki tabele: stolpci tabele ustrezajo trenutnemu (opazovanemu) simbolu na traku, vrstice ustrezajo trenutnemu stanju stroja, celice pa vsebujejo ukaz, ki ga mora stroj izvesti.

Ukaz ima lahko naslednjo strukturo:

\ [a_k \ left \ lbrace \ begin (matrika) L \\ N \\ R \ end (matrica) \ right \ rbrace q_m \]

Najprej sledi simbol abecede, ki mora biti zapisan v trenutni celici \ (a_k \), nato premik stroja v levo (L), v desno (P) ali nikamor (ostanite na mestu, H) . Na koncu je označeno novo stanje, v katerega mora iti avtomat \ (q_m \).

Celica tabele je jasno opredeljena s trenutnim simbolom \ (a_i \) in trenutnim stanjem stroja \ (q_j \).

Strinjamo se, da je na začetku dela Turingov stroj začetno stanje, označeno z \ (q_1 \), in ob prehodu na stanje ustavitve\ (q_0 \) je algoritem dokončan in stroj se ustavi.

Primer

Sestavimo algoritem za Turingov stroj, ki vnosni besedi doda 1, kar je decimalno število.

Nato lahko opisno algoritem formuliramo na naslednji način:

Če se pomaknete v desno, poiščite začetek vnosne besede
Če se premaknete v desno, poiščite konec vnosne besede
Dodajte eno trenutnemu bitu vhodne besede. Če je število od 0 do 8, zapustite. V nasprotnem primeru napišite 0, se pomaknite levo in se vrnite na 3. korak.

Zapišite ta algoritem v obliki tabele. Abeceda je sestavljena iz številk od 0 do 9 in praznega znaka \ (\ Lambda \). Potrebujemo tudi 4 stanja avtomata, ki štejejo stop stanje, ki ustrezajo korakom v opisu algoritma.

Strinjamo se, da je začetno stanje \ (1 \) iskanje začetka vhodne besede, \ (2 \) iskanje konca vhodne besede, \ (3 \) je dodatek 1.

\ (_ (q_j) \ poševnica ^ (a_i) \)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛП1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	ΛЛ3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Sledimo delovanju tega algoritma na primeru. Prva vrstica ustreza traku, druga označuje položaj stroja in njegovo trenutno stanje.

	1	9	9
1

V stanju 1 je avtomat nad prazno celico. Ustrezni ukaz iz tabele "ΛП1", torej pustite celico prazno, se pomaknite v desno in ostanite v stanju 1:

	1	9	9
	1

Zdaj avtomat spremlja vrednost "1". Ustrezni ukaz "1H2", torej pustite "1" v celici, se ne premaknite in pojdite v stanje "2":

	1	9	9
	2

V stanju "2" stroj upošteva vrednost "1". Ustrezni ukaz "1P2", torej pustite "1", se pomaknite v desno in ostanite v stanju "2":

Situacija se ponavlja:

Zdaj v stanju 3 in ob upoštevanju simbola "9" stroj izvede ukaz "0L3":

	1	9	0
		3

Situacija se ponavlja:

Stanje "0" - stanje ustavitve. Algoritem je dokončan.

Uradni opis

Matematično lahko Turingov stroj opišemo na naslednji način:

Turingov stroj (MT)

to je sistem oblike \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), kje

\ (A \) - končni niz simbolov abecede MT
\ (a_0 \ in A \) - prazen abecedni znak
\ (Q \) je končni niz stanj MT
\ (q_1 \ in Q \) - začetno stanje MT
\ (q_0 \ in Q \) - končno stanje MT (stanje ustavitve)
\ (T = \ (A, P, H \) \) je niz premikov MT
\ (\ tau \) - program MT, to je funkcija, ki določa preslikavo \ (\ tau: A \ krat Q \ poševnica \ (q_0 \) \ desna strelica A \ krat T \ krat Q \)

Ključ v teoriji algoritmov je Turingova teza.

Ohlapno oblikovana Turingova teza je oblikovana na naslednji način:

Turingova teza za vsak algoritemsko rešljiv problem obstaja Turingov stroj, ki ta problem rešuje. sicer za vsak algoritem obstaja enakovreden Turingov stroj.

Turingova teza nam omogoča, da govorimo o algoritmih s pomočjo dokaj preprostega matematičnega aparata. Poleg tega je sam Turingov stroj univerzalni pogon, in že sama možnost ustvarjanja tako namišljenega stroja je postala razlog za govor o ustvarjanju univerzalne računalniške tehnologije.

Opredelitve alternativnih algoritmov

Poleg Turingovega stroja obstaja več neodvisnih opredelitev, ki so enakovredne Turingovi definiciji.

Zlasti opredelitev s pomočjo Poštnega stroja, preko cerkvenega lambda računa, običajnega Markovljevega algoritma.

Razmislimo o teh metodah.

Poštni stroj

Leto po Turingu je ameriški matematik Emile Leon Post neodvisno predlagal še en abstraktni univerzalni računalniški stroj, ki je nekoliko poenostavljen v primerjavi s Turingovim strojem.

Post-ov stroj deluje z dvomestno abecedo, notranje stanje stroja pa se nadomesti z programska vrstica.

Sicer je Poštni stroj podoben Turingovemu: obstaja avtomat in obstaja neskončen trak s celicami.

Poštni stroj lahko izvede naslednje ukaze:

Napišite 1, pojdite na i-to vrstico programa
Napišite 0, pojdite na i-to vrstico programa
Premaknite se v levo, pojdite na i-to vrstico programa
Premaknite se v desno, pojdite na i-to vrstico programa
Pogojni skok: če je v opazovani celici 0, pojdite v i-to vrstico programa, sicer pa v j -to vrstico programa.
Stop.

Poštni stroj ima tudi več prepovedanih ukazov:

Pisanje v celico 1, ko je že 1.
Pisanje v celico 0, ko je že 0.

Takšni dogodki vodijo v propad.

Za pisanje programov za poštni stroj lahko uporabite naslednji zapis:

∨ i - napišite 1, pojdite na i -to vrstico programa
× i - napišite 0, pojdite na i -to vrstico programa
← i - izvedite levi premik, pojdite na i -to vrstico programa
→ i - izvedite premik v desno, pojdite na i -to vrstico programa
? jaz; j-pogojni skok: če je v opazovani celici 0, pojdite v i-to vrstico programa, sicer pa v j -to vrstico programa.
! - nehaj.

Vzorec programa:

1. → 2 2.? 1; 3 3. × 4 4. ← 5 5.!

Ta program bo izbrisal prvo oznako (1), ki se nahaja desno od začetnega položaja stroja, in ustavil stroj v celici levo od njega.

Na splošno je Postov avtomobil predhodnik imperativ programskih jezikov, na primer C, Fortran itd.

Poštni stroj je enakovreden Turingovemu. Z drugimi besedami, za kateri koli program za Turingov stroj lahko napišete enakovreden program za stroj Post in obratno.

Ena od pomembnih posledic te enakovrednosti je ta katero koli abecedo lahko reduciramo v binarno kodo.

Podobno kot Turingova teza obstaja tudi Postova teza.

Post -ova teza je lahko kateri koli algoritem predstavljen v obliki Poštnega stroja.

Običajni Markov algoritem

Običajni Markovljevi algoritmi so zasnovani tako, da se uporabljajo za besede v različnih abecedah.

Opredelitev katerega koli običajnega algoritma je sestavljena iz dveh delov:

Abeceda algoritem
Sheme algoritem

Za sam algoritem velja besede, to je zaporedja znakov abeceda.

Shema normalnega algoritma se imenuje končno urejen niz tako imenovanih nadomestne formule, od katerih je lahko vsaka preprosto ali konec... Izrazi oblike \ (L \ do D \) se imenujejo preproste nadomestne formule, kjer sta \ (L \) in \ (D \) dve poljubni besedi, sestavljeni iz abecede algoritma (imenovani levo in desno strani formule zamenjave). Podobno so formule za končno zamenjavo izrazi oblike \ (L \ to \ cdot D \), kjer sta \ (L \) in \ (D \) dve poljubni besedi, sestavljeni iz abecede algoritma.

Predvideva se, da pomožni znaki \ (\ to \) in \ (\ to \ cdot \) ne pripadajo abecedi algoritma.

Postopek uporabe običajnega algoritma za poljubno besedo \ (V \) je naslednje zaporedje dejanj:

Naj bo \ (V "\) beseda, pridobljena v prejšnjem koraku algoritma (ali izvirna beseda, če je trenutni korak prvi).
Če med substitucijskimi formulami ni zamenjave, katere leva stran bi bila vključena v \ (V "\), se delo algoritma šteje za dokončano, rezultat tega dela pa je beseda \ (V" \ ).
V nasprotnem primeru je med formulami zamenjave, katerih leva stran je vključena v \ (V "\), izbrana prva.
Od vseh možnih predstavitev besede \ (V "\) v obliki \ (RLS \) (kjer je \ (R \) predpona, \ (L \) pa pripona) je ena izbrana tako, da \ R \) je najkrajši, sledi zamenjava \ (V "= RDS \).
Če je nadomestna formula končna, se algoritem zaključi z rezultatom \ (V "\). V nasprotnem primeru pojdite na 1. korak (naslednji korak).

Vsak normalen algoritem je enakovreden nekemu Turingovemu stroju in obratno - vsak Turingov stroj je enakovreden nekemu normalnemu algoritmu.

Običajno se imenuje analog Turingove teze za normalne algoritme načelo normalizacije.

Primer

Ta algoritem pretvori binarna števila v "enote" (pri katerih je zapis negativnega celega števila N niz N palic). Na primer, binarno število 101 se pretvori v 5 palic: |||||.

Abeceda: (0, 1, |) Pravila:

1 → 0|
|0 → 0||
0 -> (prazen niz)

Originalna linija: 101 Izvedba:

0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

Rekurzivne funkcije

Sistem, enakovreden Turingovemu stroju, je mogoče zgraditi na podlagi matematičnih funkcij. Za to moramo uvesti naslednje razrede funkcij:

primitivne rekurzivne funkcije
splošne rekurzivne funkcije
delno rekurzivne funkcije

Slednji razred bo sovpadal s razredom Turingovih izračunanih funkcij (to je funkcij, za izračun katerih je mogoče sestaviti algoritem za Turingov stroj).

Opredelitev algoritma z rekurzivnimi funkcijami je v bistvu v središču lambda računa in pristop temelji na njegovi podlagi funkcionalno programiranje.

Primitivne rekurzivne funkcije

Razred primitivnih rekurzivnih funkcij vsebuje osnovne funkcije in vse funkcije, ki izhajajo iz osnovnih s pomočjo operatorjev zamenjave in primitivna rekurzija.

Osnovne funkcije vključujejo:

Ničelna funkcija \ (O () = 0 \) je funkcija brez argumentov, ki vedno vrne \ (0 \).
Zaporedna funkcija \ (S (x) = x + 1 \) je funkcija katere koli naravno število\ (x \) se ujema z naslednjo številko \ (x + 1 \)
Funkcije \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), kjer \ (0

Za izdelavo preostalih funkcij razreda se uporabljajo operatorji:

Zamenjave. Za funkcijo \ (f \) iz \ (m \) spremenljivk in \ (m \) funkcije \ (g_1, \ ldots, g_m \) iz \ (n \) spremenljivk, rezultat zamenjave \ (g_k \) in \ (f \) je funkcija \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \) iz \ (n \) spremenljivk.
Primitivna rekurzija. Naj bo \ (f (x_1, \ ldots, x_n) \) funkcija \ (n \) spremenljivk in \ (g (x_1, \ ldots, x_ (n + 2)) \) funkcija \ (n + 2 \) spremenljivke. Potem je rezultat uporabe primitivnega rekurzijskega operaterja za funkcije \ (f \) in \ (g \) funkcija \ (h \) spremenljivke \ (n + 1 \) oblike: \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Delno rekurzivne funkcije

Razred delno rekurzivnih funkcij vključuje primitivne rekurzivne funkcije in poleg tega vse funkcije, ki so pridobljene iz primitivnih rekurzivnih funkcij z uporabo operatorja minimiziranja argumentov:

Operator za minimiziranje argumentov

Naj bo \ (f \) funkcija \ (n \) spremenljivk \ (x_i \ v \ mathbb (N) \). Potem je rezultat uporabe operatorja minimiziranja argumentov za funkcijo \ (f \) funkcija \ (h \) argumenta \ (n-1 \), opredeljena kot:

\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \] kje \ To pomeni, da \ (h \) vrne minimalno vrednost zadnjega argumenta funkciji \ (f \), pri kateri je \ (f \) nič.

Medtem ko so primitivne rekurzivne funkcije vedno izračunane, delno rekurzivne funkcije morda niso določene za nekatere vrednosti argumentov.

Natančneje, delno rekurzivne funkcije bi morali imenovati "delno definirane rekurzivne funkcije", saj so opredeljene le na del možnih vrednosti argumentov.

Splošne rekurzivne funkcije

Splošne rekurzivne funkcije so podrazred vseh delno rekurzivnih funkcij, ki so definirane za katero koli vrednost argumenta. Problem ugotavljanja, ali je neka delno rekurzivna funkcija splošno rekurzivna, je algoritemsko nejasno... To nas pripelje do teme teorije izračunanosti in problema zaustavitve.

Teorija izračunanosti in problem zaustavitve

Naša domišljija na splošno dopušča obstoj nerešljivih problemov, torej problemov, za katere je nemogoče sestaviti algoritem.

Teorija računanja obravnava takšne težave.

Primeri algoritmično nerešljivih problemov so problem ustaviti in problem prepoznavanja valilnosti... Poglejmo jih podrobneje.

Problem ustavitve Na podlagi opisa algoritma A in vhodnih podatkov \ (x \) je treba ugotoviti, ali se algoritem \ (A \) ustavi na vhodnih podatkih \ (x \).

Problem ustavitve je algoritemsko nerešljiv. Dokažimo.

\ (\ Delta \)

Naj obstaja univerzalni algoritem, ki reši problem ustavitve. Nato razmislite o razredu algoritmov, ki obdeluje besedila, ki opisujejo algoritme.

Zaradi obstoja univerzalnega algoritma za reševanje problema ustavitve obstaja algoritem, ki določa, ali se bo algoritem iz omenjenega razreda ustavil pri svojem besedilu ali ne. Ta algoritem označimo z \ (B \).

Zgradimo algoritem \ (C \), katerega vhodni podatek je besedilo algoritma \ (A \), ki obdeluje svoje besedilo:

Izvedite algoritem \ (B \) nad \ (A \).
Če algoritem \ (B \) ugotovi, da se bo \ (A \) ustavil pri svojem besedilu, pojdite na korak 1. V nasprotnem primeru pojdite na korak 3.
Konec algoritma \ (C \).

Ko smo poskusili uporabiti algoritem \ (C \) za algoritem \ (C \), pridemo do očitnega protislovja: če se \ (C \) ustavi pri svojem besedilu, se ne more ustaviti in obratno. Zato ni algoritma \ (B \). \ (\ ne \ Delta \)

Splošnejša formulacija problema zaustavitve je problem opredelitve valilnosti.

Težava s prepoznavanjem valilnosti

Naj se določi določena abeceda, besede (formule) te abecede in sistem formalnih transformacij nad besedami te abecede (tj. Zgrajen je logični račun)

Ali obstajata v okviru tega logičnega računa za kateri koli dve besedi \ (R \) in \ (S \) deduktivna veriga, ki vodi od \ (R \) do \ (S \)?

Leta 1936 je Alonzo Church dokazal Cerkveni izrek.

Cerkveni izrek Problem priznavanja odbitnosti je algoritemsko nerešljiv.

Cerkev je za dokaz uporabila formalizem lambda računa. Leta 1937 je Turing neodvisno od njega z uporabo formalizma Turingovega stroja dokazal isti izrek.

Ker so vse definicije algoritmov enakovredne, obstaja sistem konceptov, ki ni povezan z določeno definicijo algoritma in deluje s konceptom izračunana funkcija.

Izračunljiva funkcija Funkcija, ki jo je mogoče izračunati z algoritmom.

Obstajajo težave, pri katerih razmerja med vhodnimi in izhodnimi podatki ni mogoče opisati z uporabo algoritma. Takšne funkcije so neračunano.

Primer neračunane funkcije

Vzemite funkcijo \ (h (n) \), opredeljeno za \ (\ forall n \ in \ mathbb (N) \), kot sledi:

\ [h (n) = \ start (primeri) 1, & \ besedilo (če je v) \ pi \ besedilo (obstaja natančno zaporedje) n \ besedilo (9-k) \\ 0, & \ besedilo (drugače ) \ end (primeri) \]

Za to funkcijo lahko dobimo vrednost \ (1 \), vendar, da dobimo vrednost \ (0 \), moramo preveriti neskončno decimalno razširitev \ (\ pi \), kar je v končnem času očitno nemogoče . Te funkcije torej ni mogoče izračunati.

Eno najpomembnejših vprašanj sodobne računalništva je, ali obstaja formalni izvajalec, s pomočjo katerega je mogoče posnemati vsakega formalnega izvajalca. odgovor na to vprašanje sta skoraj istočasno dobila dva izjemna znanstvenika - A. Turing in E. Post. Izvajalci, ki so jih predlagali, so se med seboj razlikovali, vendar se je izkazalo, da se lahko posnemajo drug drugega, in kar je najpomembneje, posnemajo delo katerega koli formalnega izvajalca.

Kaj je uradni izvajalec? Kaj pomeni - en formalni izvajalec posnema delo drugega formalnega izvajalca? Če ste igrali računalniške igre, predmeti na zaslonu brez vprašanj ubogajo ukaze predvajalnika. Vsak predmet ima niz veljavnih ukazov. Hkrati je računalnik sam izvršitelj in ne virtualni, ampak resničen. Tako se izkaže, da en formalni izvajalec posnema delo drugega formalnega izvajalca.

Razmislite, kako deluje Turingov stroj.

Turingov stroj je neskončen trak, razdeljen na celice, in nosilec (bralnik in tiskalnik), ki se premika vzdolž traku.

Tako je Turingov stroj uradno opisan z nizom dveh abeced:

A = (a1, a2, a3, ..., an) - zunanja abeceda, ki se uporablja za beleženje začetnih podatkov

Q = (q1, q2, q3,…, qm) - notranja abeceda, opisuje niz stanj bralnika in tiskalne naprave.

Vsaka celica traku lahko vsebuje simbol iz zunanje abecede A = (a0, a1, ..., an) (V našem primeru je A = (0, 1))

Veljavna dejanja Turingovega stroja so naslednja:

1) v celico traku vnesite kateri koli znak zunanje abecede (znak, ki je bil tam prej, se prepiše)

2) premaknite se v sosednjo celico

3) spremenite stanje v eno od tistih, ki jih označuje simbol notranje abecede Q

Turingov stroj je namizni stroj.

Vrstice v tabeli ustrezajo simbolom izbrane abecede A, stolpci pa stanjem avtomata Q = (q0, q1,…, qm). Na začetku delovanja je Turingov stroj v stanju q1. Stanje q0 je končno stanje; ko avtomat vstopi vanj, avtomat konča svoje delo.

Vsaka celica tabele, ki ustreza nekemu simbolu ai in nekemu stanju qj, vsebuje ukaz, sestavljen iz treh delov
Znak iz abecede A
· Smer gibanja: ">" (na desni), "<» (влево) или «.» (на месте)
Novo stanje stroja

V zgornji tabeli sta abeceda A = (0, 1, _) (vsebuje 3 znake) in notranja abeceda Q = (q1, q2, q3, q4, q0), q0 je stanje, zaradi katerega se nosilec ustavi.

Z reševanjem razmislimo o več nalogah. Na spletnem mestu v razdelku lahko prenesete Turingov stroj.

Naloga 1. Naj bo A = (0, 1, _). Celice na traku vsebujejo znake iz abecede v naslednjem vrstnem redu 0011011. Kareta je nad prvim znakom. Napisati je treba program, ki bo 0 zamenjal z 1, 1 z 0 in nosilec vrnil v prvotni položaj.

Zdaj pa opredelimo stanja kočije. Imenujem jih "želje po vozičku, da naredijo nekaj".

q1) Nosilec mora iti v desno: če vidi 0, ga spremeni v 1 in ostane v stanju q1, če vidi 1, ga spremeni v 0 in ostane v stanju q1, če vidi _, to vrne 1 celico "želi nekaj drugega", to pomeni, da preide v stanje q2. Zapišimo svoje razmišljanje v tabelo izvajalca. Za sintakso si oglejte pomoč programa)

q2) Zdaj opišemo "željo po vozičku" q2. Moramo se vrniti v prvotni položaj. Če želite to narediti: pustite 1 in ga pustite v stanju q2 (z enako željo, da pridete do konca vrstice simbolov); če vidimo 0, ga pustimo in se še naprej premikamo levo v stanju q2; vidimo _ - je premaknjeno v desno za 1 celico. Tu ste tam, kjer to zahteva izjava o težavi. preidemo v stanje q0.

Delo programa si lahko ogledate v videu:

Problem 2. Podano: končno zaporedje 0 in 1 (001101011101). Po tem zaporedju jih morate zapisati skozi prazno celico in jih v tem zaporedju zamenjati z 0. Na primer:

Od 001101011101 dobimo 000000000000 1111111.

Kot lahko vidite, je po tem zaporedju napisanih sedem ena, na njihovih mestih pa ničle.

Pojdimo na sklepanje. Ugotovite, katera stanja so potrebna za prevoz in koliko.

q1) žaga 1 - popravite jo na nič in pojdite v drugo stanje q2 (uvede se novo stanje, tako da nosilec v enem prehodu ne spremeni vseh enot v ničle)

q2) ne spreminjajte ničesar, premaknite se na konec zaporedja

q3) takoj, ko kareta zagleda prazno celico, naredi korak v desno in jo nariše, če jo vidi, se premakne naprej in podpiše znak na koncu. Takoj, ko narišemo enoto, gremo v stanje q4

q4) gremo skozi zapisane enote, ne da bi kaj spremenili. Takoj, ko pridemo do prazne celice, ki loči zaporedje od enot, preidemo iz novega stanja q5

q5) v tem stanju gremo na začetek zaporedja, ne da bi kaj spremenili. Pridemo do prazne celice, se obrnemo in gremo v stanje q1

Nosilec prevzame stanje q0, ko preide v stanju q1 na konec tega zaporedja in naleti na prazno celico.

Dobimo naslednji program:

Delo Turingovega stroja si lahko ogledate v spodnjem videu.

Turingov stroj je zbirka naslednjih predmetov

1) zunanja abeceda A = (a 0, a 1,…, a n);
2) notranja abeceda Q = (q 1, q 2,…, q m) je niz stanj;
3) niz kontrolnih znakov (P, L, S)
4) neskončen trak v obeh smereh, razdeljen na celice, v vsako lahko v vsakem diskretnem trenutku vpišemo samo en znak iz abecede A;
5) krmilna naprava, ki je lahko v enem od mnogih stanj

Simbol za prazno celico je zunanja črka a 0.

Med stanjem se razlikujeta začetno q 1, v katerem stroj začne delovati, in končno (ali stanje ustavitve) q 0, v katerem se stroj ustavi.

Krmilna naprava se lahko premika levo in desno vzdolž traku, bere in zapisuje črke abecede A. V celice traku krmilna naprava deluje v skladu z naslednjimi ukazi.

q i a j> a p X q k

Vnos pomeni naslednje: če je krmilna naprava v stanju qi in je v opazovani celici zapisana črka aj, se namesto aj v celico zapiše (1) ap, (2) naprava preide na naslednjo desno celico od tiste, ki je bila pravkar ogledana, če je X = P, ali za ogled naslednje leve celice, če je X = L, ali nadaljuje z ogledom iste celice traku, če je X = C, (3) krmilna naprava preide v stanje q k.

Ker delovanje stroja po pogojih v celoti določa njegovo stanje q, v ta trenutek in vsebino celice, ki si jo trenutno ogledate, potem za vsako možno konfiguracijo q i a j obstaja točno eno pravilo. Ne obstajajo pravila samo za končno stanje, v katerem se avto ustavi. Zato program Turingovega stroja z zunanjo abecedo A = (a0, a1,…, an) in notranjim Q = (q1, q2,…, qm) vsebuje največ m (n + 1) navodil.

Beseda v abecedi A ali v abecedi Q ali v abecedi A Q je katero koli zaporedje črk ustrezne abecede. S k-to konfiguracijo mislimo na podobo traku stroja z informacijami, ki so na njem nastale na začetku k-tega koraka (ali besedo v abecedi A, zapisano na traku na začetku k- th korak), ki označuje, katero celico si ogledujete na tem koraku in v kakšnem stanju je avto. Smiselne so le končne konfiguracije, tj. tiste, v katerih so vse celice traku, z izjemo možnega končnega števila, prazne. Konfiguracija se imenuje končna, če je stanje, v katerem je stroj, dokončno.

Če za začetno izberemo katero koli nekončno konfiguracijo Turingovega stroja, bo delo stroja sestavljeno iz zaporednega (korak za korakom) spreminjanja začetne konfiguracije v skladu s programom stroja, dokler ni dosežena končna konfiguracija. Po tem se šteje, da je delo Turingovega stroja končano, rezultat dela pa je dosežena končna konfiguracija.

Rekli bomo, da stroj, ki je prazen v abecedi A (a 0) = (a 1, ..., an), zazna stroj v standardnem položaju, če je zapisan v zaporednih celicah traku, vse druge celice so prazne, stroj pa gleda v levo ali skrajno desno celico od tistih, v katerih je zapisana beseda b. Standardni položaj se imenuje začetni (končni) položaj, če je stroj, ki zazna besedo v standardnem položaju, v začetnem stanju q 1 (oziroma v stanju ustavitve q 0).

Če obdelava besede b prenese Turingov stroj v končno stanje, potem velja, da velja za b, sicer pa ne velja za b (stroj deluje v nedogled)

Poglejmo primer:

Glede na Turingov stroj z zunanjo abecedo A = (0, 1) (tukaj 0 je simbol prazne celice), abecedo notranjih stanj Q = (q 0, q 1, q 2) in z naslednjim funkcionalnim diagramom (program):

q 1 0> 1 L q 2;

q 1 1> 0 C q 2;

q 2 0> 0 P q 0;

q 2 1> 1 C q 1;

Ta program je mogoče napisati s pomočjo tabele

Na prvem koraku deluje naslednji ukaz: q 1 0> 1 Л q 2 (krmilna naprava je v stanju q1, črka 0 je zapisana v opazovani celici, 1 je v celico namesto 0, glava se pomakne v levo, krmilna naprava preide v stanje q2), v Posledično se na stroju ustvari naslednja konfiguracija:

Končno se po izvedbi ukaza q 2 0> 0 P q 0 ustvari konfiguracija

Ta konfiguracija je dokončna, ker je bil stroj v stanju ustavitve q 0.

Tako stroj prvotno besedo 110 obdela v besedo 101.

Nastalo zaporedje konfiguracij je mogoče zapisati na krajši način (vsebina opazovane celice je zapisana desno od stanja, v katerem se stroj trenutno nahaja):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Turingov stroj ni nič drugega kot pravilo (algoritem) za preoblikovanje besed abecede A Q, tj. konfiguracije. Tako morate za določitev Turingovega stroja določiti njegovo zunanjo in notranjo abecedo, program in navesti, kateri od simbolov označujeta prazno celico in končno stanje.

Turingov stroj (MT)- abstraktni izvajalec (abstraktni računalniški stroj). Alan Turing je leta 1936 predlagal formalizacijo koncepta algoritma.

Turingov stroj je podaljšek stroja končnega stanja in po Cerkvi - Turingova teza, sposoben posnemati vse izvajalce(z določitvijo prehodnih pravil), ki nekako izvajajo postopek postopnega izračunavanja, pri katerem je vsak korak izračuna precej elementaren.

To pomeni, da se lahko kateri koli intuitivni algoritem izvede z uporabo nekega Turingovega stroja.

Kolegij YouTube

1 / 5

✪ 09 - Uvod v algoritme. Turingov stroj

✪ Turingov stroj - Alexander Shen

✪ Predavanje 20: Turingov stroj

✪ Turingov stroj. Primer dela

✪ 16 - Računanje. Turingovi stroji. Motivacija in primeri

Podnapisi

Struktura Turingovega stroja

Turingov stroj vključuje neomejeno število v obe smeri trak(Možni so Turingovi stroji, ki imajo več neskončnih trakov), razdeljeni na celice in krmilna naprava(imenovano tudi glava za branje in pisanje (GZCH)), sposoben biti v enem od niz držav... Število možnih stanj krmilne naprave je omejeno in natančno določeno.

Krmilna naprava se lahko premika levo in desno po traku, bere in zapisuje znake neke končne abecede v celice. Izstopa posebno prazno znak, ki zapolni vse celice traku, razen tistih izmed njih (končno število), na katere so zapisani vhodni podatki.

Krmilna naprava deluje v skladu z prehodna pravila ki predstavljajo algoritem, izvedljivo ta Turingov stroj. Vsako pravilo prehoda naloži stroju, odvisno od trenutnega stanja in simbola, opaženega v trenutni celici, da v to celico vpiše nov simbol, preklopi v novo stanje in premakne eno celico v levo ali desno. Nekatera stanja Turingovega stroja lahko označimo kot terminal in prehod na katero koli od njih pomeni konec dela, ustavitev algoritma.

Turingov stroj se imenuje determinističnoče se največ eno pravilo ujema z vsako kombinacijo stanja in simbola traku v tabeli. Če obstaja par "črtast simbol - stanje", za katerega obstajata 2 ali več navodil, se tak Turingov stroj imenuje nedeterministična.

Opis Turingovega stroja

Določen Turingov stroj je določen z naštevanjem elementov niza črk abecede A, niza stanj Q in niza pravil, po katerih stroj deluje. Imajo obliko: qiaj → q i1 a j1 dk (če je glava v stanju qi in je črka aj zapisana v opazovani celici, potem glava preide v stanje q i1, v celico je zapisano a j1 namesto aj glava naredi gib dk, ki ima tri možnosti: ena celica levo (L), ena celica desno (R), ostane na mestu (N)). Za vsako možno konfiguracijo obstaja točno eno pravilo (za nedeterministični Turingov stroj lahko obstaja velika količina pravila). Ne obstajajo pravila samo za končno stanje, v katerem se avto ustavi. Poleg tega morate določiti končno in zagonsko stanje, začetno konfiguracijo na pasu in lokacijo glave stroja.

Primer Turingovega stroja

Navedimo primer MT za množenje števil v unarnem številčnem sistemu. Zapis pravila "qiaj → q i1 a j1 R / L / N" je treba razumeti tako: qi je stanje, v katerem se to pravilo izvaja, aj so podatki v celici, v kateri se nahaja glava, q i1 je stanje, v katerega je treba iti, a j1 - kar je treba zapisati v celico, R / L / N - ukaz premik.

Stroj deluje v skladu z naslednjimi pravili:

	q 0	q 1	q 2	q 3	q 4	q 5	q 6	q 7	q 8
1	q 0 1 → q 0 1R	q 1 1 → q 2 aR	q 2 1 → q 2 1L	q 3 1 → q 4 aR	q 4 1 → q 4 1R			q 7 1 → q 2 aR
×	q 0 × → q 1 × R		q 2 × → q 3 × L		q 4 × → q 4 × R		q 6 × → q 7 × R		q 8 × → q 9 × N
=			q 2 = → q 2 = L		q 4 = → q 4 = R			q 7 = → q 8 = L
a			q 2 a → q 2 aL	q 3 a → q 3 aL	q 4 a → q 4 aR		q 6 a → q 6 1R	q 7 a → q 7 aR	q 8 a → q 8 1L
*	q 0 * → q 0 * R			q 3 * → q 6 * R	q 4 * → q 5 1R
						q 5 → q 2 * L

Opis držav:

Začni
q 0	začetno stanje. Iščemo "x" na desni. Ko najdemo, gremo v stanje q1
q 1	zamenjajte "1" z "a" in pojdite v stanje q2
Prenesite vse "1" od prve številke do rezultata
q 2	išče "x" na levi. Ko najdemo, gremo v stanje q3
q 3	na levi poiščite "1", ga zamenjajte z "a" in pojdite v stanje q4. Če je "1" končano, poiščemo "*" in gremo v stanje q6
q 4	pojdite do konca (iščete »« na desni), zamenjajte »« z »1« in pojdite v stanje q5
q 5	dodajte "*" na konec in pojdite v stanje q2
Obdelujemo vsako številko druge številke
q 6	poiščite "x" na desni in pojdite v stanje q7. Medtem ko iščemo, "a" zamenjamo z "1"
q 7	iščete "1" ali "=" na desni ko najdemo "1", ga zamenjamo z "a" in preidemo v stanje q2 ko je "=", gremo v stanje q8
Konec
q 8	išče "x" na levi. Ko najdemo, preidemo v stanje q9. Medtem ko iščemo, "a" zamenjamo z "1"
q 9	stanje terminala (algoritem zaustavitve)

Pomnožite 3 s 2 s pomočjo MT v sistemu enot. Protokol označuje začetno in končno stanje MT, začetno konfiguracijo na pasu in lokacijo glave stroja (podčrtani simbol).

Začni. Smo v stanju q 0, v stroj smo vnesli podatke: *111x11 = *, glava stroja se nahaja na prvem znaku *.

1. korak. Poglejmo tabelo pravil, kaj bo stroj naredil, ko je v stanju q 0 in nad simbolom "*". To je pravilo iz prvega stolpca 5. vrstice - q 0 * → q 0 * R. To pomeni, da gremo v stanje q 0 (torej ga ne spreminjamo), simbol postane "*" (to pomeni, da se ne spremeni) in se premikamo po vnesenem besedilu "*111x11 =*" desno na eno mesto (R), nato je na prvem znaku 1. Stanje q 0 1 (1. stolpec 1. vrstica) se obdela po pravilu q 0 1 → q 0 1R. Se pravi, spet je preprosto prehod v desno za 1 položaj. To se zgodi, dokler ne stojimo pri simbolu "x". In tako naprej: vzamemo stanje (indeks pri q), vzamemo simbol, na katerem stojimo (podčrtani simbol), jih povežemo in opazujemo obdelavo nastale kombinacije v skladu s tabelo pravil.

Z enostavnimi besedami je algoritem množenja naslednji: označimo 1. enoto 2. faktorja, ga nadomestimo s črko "a" in prenesemo celoten 1. faktor za znak enakosti. Prenos se izvede tako, da enote prvega faktorja izmenično zamenjate z "a" in na koncu vrstice (levo od skrajnega desnega "*") dodate enako število enot. Nato vse "a" spremenimo v znak množenja "x" nazaj v enote. In cikel se ponavlja. Konec koncev je A, pomnoženo z B, mogoče predstaviti kot A + A + A B krat. Zdaj označimo 2. enoto 2. faktorja s črko "a" in znova prenesemo enote. Če pred znakom "=" ni enot, je množenje končano.

Turingova popolnost

Lahko rečemo, da je Turingov stroj najpreprostejši računalniški stroj z linearnim pomnilnikom, ki po formalnih pravilih spreminja vhodne podatke z uporabo zaporedja elementarna dejanja.

Osnovna narava dejanj je v tem, da dejanje spremeni le majhen del podatkov v pomnilniku (v primeru Turingovega stroja samo eno celico), število možnih dejanj pa je končno. Kljub preprostosti Turingovega stroja se lahko z njim izračuna vse, kar je mogoče izračunati na katerem koli drugem stroju, ki izvaja izračune z zaporedjem osnovnih dejanj. Ta lastnost se imenuje popolnost.

Eden od naravnih načinov dokazovanja, da se lahko računski algoritmi, ki jih je mogoče izvesti na enem stroju, lahko izvede na drugem, je posnemati prvi stroj na drugem.

Imitacija je naslednja. Ob vhodu v drugi stroj je podan opis programa (pravila delovanja) prvega stroja D (\ displaystyle D) in vnos podatkov X (\ displaystyle X), ki naj bi prišli do vhoda prvega avtomobila. Ta program je treba opisati (pravila delovanja drugega stroja), tako da se zaradi izračunov izkaže, da je izhod enak, kot bi se prvi stroj vrnil, če bi prejel podatke kot vhodne X (\ displaystyle X).

Kot je bilo rečeno, je na Turingovem stroju mogoče (z nastavitvijo prehodnih pravil) simulirati vse druge izvajalce, ki nekako izvajajo postopek postopnega izračunavanja, pri katerem je vsak korak izračunavanja precej elementaren.

Na Turingovem stroju lahko posnemate Post stroj, običajne Markovljeve algoritme in kateri koli program za navadne računalnike, ki pretvori vhodne podatke v izhode z uporabo nekega algoritma. Turingov stroj pa lahko posnemamo pri različnih abstraktnih izvajalcih. Imenujejo se izvajalci, za katere je to mogoče Turing je končan(Turingov zaključek).

Obstajajo programi za navadne računalnike, ki simulirajo delovanje Turingovega stroja. Vendar je treba opozoriti, da je to posnemanje nepopolno, saj je v Turingovem stroju abstraktni neskončni trak. Neskončnega traku s podatki ni mogoče v celoti simulirati v računalniku s omejenim pomnilnikom (skupni pomnilnik računalnika je Oven, trdi diski, različni zunanji pomnilniški mediji, registri in predpomnilnik procesorja itd. - so lahko zelo veliki, vendar kljub temu vedno omejeni).

Različice Turingovih strojev

Model Turingovega stroja je razširljiv. Lahko upoštevamo Turingove stroje s poljubnim številom trakov in večdimenzionalne trakove z različnimi omejitvami. Vendar so vsi ti stroji Turingovi popolni in jih modelira običajni Turingov stroj.

Turingov stroj, ki deluje na pol neskončnem pasu

Kot primer takega zmanjšanja upoštevajte naslednji izrek: Za vsak Turingov stroj obstaja enakovreden Turingov stroj, ki deluje na pol neskončnem traku (torej na traku, ki je neskončen v eno smer).

Upoštevajte dokaz, ki ga je podal Yu. G. Karpov v knjigi Teorija avtomatov. Dokaz tega izreka je konstruktiven, torej podali bomo algoritem, s katerim lahko za kateri koli Turingov stroj sestavimo enakovreden Turingov stroj z deklarirano lastnostjo. Najprej poljubno oštevilčimo celice delovnega traku MT, torej določimo novo lokacijo informacij na traku:

Nato bomo celice preštevilčili in domnevali bomo, da simbol "*" ni v slovarju MT:

Končno spremenimo Turingov stroj tako, da podvojimo število njegovih stanj in spremenimo premik glave za branje in pisanje, tako da bi bilo v eni skupini stanj delovanje stroja enako delovanju v zasenčenem območju, v drugi skupini stanj stroj bi deloval tako kot prvotni stroj na nezasenčenem območju. Če med delovanjem MT naletite na simbol '*', je glava za branje in pisanje dosegla mejo območja:

Začetno stanje novega Turingovega stroja je nastavljeno v eni ali drugi coni, odvisno od tega, kateri del prvotnega traku je bil glava za branje in pisanje v prvotni konfiguraciji. Očitno se levo od omejevalnih oznak "*" trak ne uporablja v enakovrednem Turingovem stroju.

Dvodimenzionalni Turingovi stroji

Langtonova mravlja

Poglej tudi

JFLAP program za več platformah simulator avtomatov, Turingovi stroji, slovnice, nariše avtomatski graf