Turingov stroj. Težave in rešitve
1. Opis Turingovega stroja. 3
1.1 Lastnosti Turingovega stroja kot algoritma. 5
2. Kompleksnost algoritmov. 7
2.1 Kompleksnost problemov... 9
3. Turingov stroj in algoritemsko nerešljivi problemi.. 12
Zaključek. 16
Reference.. 18
Uvod
Turingov stroj je zelo preprosta računalniška naprava. Sestavljen je iz traku neskončne dolžine, razdeljenega na celice, in glave, ki se premika po traku in je sposobna brati in pisati znake. Tudi Turingov stroj ima takšno značilnost, kot je stanje, ki ga je mogoče izraziti kot celo število od nič do neke največje vrednosti. Odvisno od stanja lahko Turingov stroj izvede eno od treh dejanj: zapiše simbol v celico, premakne eno celico v desno ali levo in nastavi notranje stanje.
Zasnova Turingovega stroja je izjemno preprosta, vendar lahko izvaja skoraj vsak program. Za izvajanje vseh teh dejanj je na voljo posebna tabela pravil, ki določa, kaj je treba narediti za različne kombinacije trenutnih stanj in simbolov, prebranih s traku.
Leta 1947 je Alan Turing razširil definicijo, da bi opisal "univerzalni Turingov stroj". Kasneje so za reševanje določenih razredov problemov uvedli njegovo različico, ki je omogočila izvajanje ne ene naloge, ampak več.
1. Opis Turingovega stroja
Ozadje nastanka tega dela je povezano s formulacijo nerešenih matematičnih problemov Davida Hilberta na mednarodnem matematičnem kongresu v Parizu leta 1900. Eden od njih je bil problem dokazovanja konsistentnosti sistema aksiomov običajne aritmetike, ki ga je Hilbert kasneje razjasnil kot "problem odločljivosti" - iskanje splošne metode za določitev izpolnitve dane izjave v jeziku formalne logike.
Turingov članek je natančno dal odgovor na to težavo – Hilbertov drugi problem se je izkazal za nerešljivega. Toda pomen Turingovega dokumenta je daleč presegel problem, za katerega je bil napisan.
Tukaj je opis tega dela, ki pripada Johnu Hopcroftu: »Pri delu na Hilbertovem problemu je moral Turing dati jasno definicijo samega koncepta metode, začenši z intuitivno idejo metode kot neke vrste algoritma. postopek, ki ga je mogoče izvajati mehansko, brez ustvarjalnega posega, je pokazal, kako je mogoče to idejo utelešiti v obliki dobljenega modela računanja, v katerem je bil vsak algoritem razčlenjen na zaporedje preprostih, osnovnih korakov, je bil logični konstrukt, kasneje imenovan Turingov stroj."
Turingov stroj je razširitev modela končnega stroja, razširitev, ki vključuje potencialno neskončen pomnilnik z možnostjo premikanja (premikanja) iz trenutno gledane celice v njeno levo ali desno sosedo.
Formalno lahko Turingov stroj opišemo na naslednji način. Naj bo podano naslednje:
končna množica stanj – Q, v katerih je lahko Turingov stroj;
končna množica tračnih simbolov – Г;
funkcija δ (prehodna funkcija ali program), ki je podana s preslikavo para iz kartezičnega produkta Q x Г (stroj je v stanju qi in gleda simbol gi) v trojko kartezičnega produkta Q x Г x (L ,R) (stroj gre v stanje qi, zamenja simbol gi s simbolom gj in se premakne levo ali desno za en simbol traku) – Q x Г-->Q x Г x (L,R)
en znak iz Г-->е (prazno);
podmnožica Σ є Г - -> je definirana kot podmnožica vhodnih simbolov traku in е є (Г - Σ);
eno od stanj - q0 є Q je začetno stanje stroja.
Problem, ki ga je treba rešiti, je določen s snemanjem končnega števila simbolov iz niza Σ є Г – Si є Σ na trak:
eS1S2S3S4... ... ...Sne
nato se stroj prestavi v začetno stanje in glava se namesti na skrajno levi neprazen simbol (q0,w) –, nato pa v skladu z določeno prehodno funkcijo (qi,Si) - ->(qj, Sk, L ali R), stroj začne zamenjati prikazane simbole, premakniti glavo v desno ali levo in preiti v druga stanja, ki jih predpisujejo prehodne funkcije.
Stroj se ustavi, če prehodna funkcija za par (qi,Si) ni definirana.
Alan Turing je predlagal, da je vsak algoritem v intuitivnem pomenu besede mogoče predstaviti z enakovrednim Turingovim strojem. Ta predpostavka je znana kot Church–Turingova teza. Vsak računalnik lahko simulira Turingov stroj (operacije prepisovanja celic, primerjave in premikanja v drugo sosednjo celico, ob upoštevanju sprememb v stanju stroja). Posledično lahko algoritme modelira v poljubnem formalizmu, iz te teze pa sledi, da so si vsi računalniki (ne glede na moč, arhitekturo itd.) enakovredni glede temeljne sposobnosti reševanja algoritemskih problemov.
1.1 Lastnosti Turingovega stroja kot algoritma
Na primeru Turingovega stroja lahko jasno vidimo lastnosti algoritmov. Študente prosite, naj pokažejo, da ima Turingov stroj vse lastnosti algoritma.
Diskretnost. Turingov stroj se lahko premakne na (k + 1)-ti korak šele po zaključku vsakega koraka, saj je vsak korak tisti, ki določa, kaj bo (k + 1)-ti korak.
Jasnost. Pri vsakem koraku se v celico zapiše simbol iz abecede, avtomat naredi en gib (L, P, N) in Turingov stroj preide v eno od opisanih stanj.
determinizem. Vsaka celica tabele Turingovega stroja vsebuje samo eno možnost za dejanje. Na vsakem koraku je rezultat enolično določen, torej je zaporedje korakov za rešitev problema enolično določeno, t.j. Če dobi Turingov stroj isto vhodno besedo, bo izhodna beseda vsakič enaka.
Produktivnost. Z vidika vsebine so rezultati vsakega koraka in celotnega zaporedja korakov enolično definirani; zato bo pravilno zapisan Turingov stroj prešel v stanje q0 v končnem številu korakov, tj. v končnem številu korakov bomo dobili odgovor na problemsko vprašanje.
Množični značaj. Vsak Turingov stroj je definiran nad vsemi dopustnimi besedami iz abecede, to je lastnost množičnega značaja. Vsak Turingov stroj je zasnovan za reševanje enega razreda problemov, tj. Za vsako težavo je napisan svoj (nov) Turingov stroj.
2. Kompleksnost algoritmov
Kompleksnost algoritma določa računalniška moč, potrebna za njegovo izvajanje. Računalniška kompleksnost algoritma se pogosto meri z dvema parametroma: T (časovna kompleksnost) in S (prostorska kompleksnost ali pomnilniške zahteve). Tako T kot S sta običajno predstavljena kot funkciji n, kjer je n velikost vhodnih podatkov. (Obstajajo tudi drugi načini za merjenje kompleksnosti: število naključnih bitov, širina komunikacijskega kanala, količina podatkov itd.)
Običajno je računska kompleksnost algoritma izražena z zapisom "Big O", kar pomeni, da je opisana z vrstnim redom velikosti računske kompleksnosti. To je preprosto člen v razširitvi kompleksne funkcije, ki raste najhitreje z večanjem n, vsi členi nižjega reda so prezrti. Na primer, če je časovna kompleksnost danega algoritma 4n2+7n+12, potem je računska kompleksnost reda n2, zapisano kot O(n2).
Tako izmerjena časovna kompleksnost je neodvisna od izvedbe. Ni vam treba poznati natančnih časov izvajanja različnih ukazov, niti števila bitov, ki se uporabljajo za predstavitev različnih spremenljivk, niti hitrosti procesorja. En računalnik je lahko 50 odstotkov hitrejši od drugega, tretji pa ima morda dvakrat širše podatkovno vodilo, vendar se kompleksnost algoritma, merjena z velikostnim redom, ne bo spremenila. Ne gre za goljufanje; pri delu s tako zapletenimi algoritmi, kot so opisani v tej knjigi, lahko zanemarimo vse ostalo (do konstantnega faktorja) v primerjavi z velikostjo kompleksnosti.
Ta zapis vam omogoča, da vidite, kako velikost vhodnih podatkov vpliva na zahteve po času in pomnilniku. Na primer, če je T = O(n), bo podvojitev vhodnih podatkov podvojila čas izvajanja algoritma. Če je T=O(2n), bo dodajanje enega bita vhodnim podatkom podvojilo čas izvajanja algoritma.
Običajno so algoritmi razvrščeni glede na njihovo časovno ali prostorsko kompleksnost. Algoritem se imenuje konstanten, če njegova kompleksnost ni odvisna od n: 0(1). Algoritem je linearen, če je njegova časovna kompleksnost O(n). Algoritmi so lahko kvadratni, kubični itd. Vsi ti algoritmi so polinomski, njihova kompleksnost je O(m), kjer je m konstanta. Algoritme s polinomsko časovno kompleksnostjo imenujemo polinomski časovni algoritmi
Algoritmi, katerih kompleksnost je enaka O(tf(n)), kjer je t konstanta večja od 1, f(n) pa neka polinomska funkcija od n, se imenujejo eksponentni. Podmnožica eksponentnih algoritmov, katerih kompleksnost je O(cf(n)), kjer je c konstanta in f(n) narašča hitreje kot konstanta, a počasneje kot linearna funkcija, se imenuje superpolinom.
Idealno bi bilo, če bi kriptograf želel trditi, da ima najboljši algoritem za razbijanje oblikovanega šifrirnega algoritma eksponentno časovno kompleksnost. V praksi so najmočnejše izjave, ki jih je mogoče podati glede na trenutno stanje teorije računalniške kompleksnosti, v obliki "vsi znani algoritmi napada za dani kriptosistem imajo superpolinomsko časovno kompleksnost." To pomeni, da imajo algoritmi napada, ki jih poznamo, superpolinomsko časovno kompleksnost, vendar še ni mogoče dokazati, da algoritma napada s polinomsko časovno kompleksnostjo ni mogoče odkriti. Razvoj teorije računalniške kompleksnosti bo morda nekega dne omogočil ustvarjanje algoritmov, pri katerih bo mogoče z matematično natančnostjo izključiti obstoj algoritmov s polinomskim odpiralnim časom.
Eno najpomembnejših vprašanj sodobnega računalništva je, ali obstaja formalni izvajalec, s katerim lahko posnemamo katerega koli 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 lahko posnemajo drug drugega, predvsem pa oponašajo delo katerega koli formalnega izvajalca.
Kaj je formalni izvršitelj? Kaj pomeni - en formalni izvajalec posnema delo drugega formalnega izvajalca? Če ste igrali računalniške igrice, predmeti na zaslonu nedvomno ubogajo igralčeve ukaze. Vsak objekt ima niz veljavnih ukazov. Hkrati je računalnik sam izvajalec, in ne virtualni, ampak resnični. Tako se izkaže, da en formalni izvajalec posnema delo drugega formalnega izvajalca.
Razmislite o delovanju Turingovega stroja.
Turingov stroj je neskončni trak, razdeljen na celice in voziček (bralna in tiskalna naprava), ki se premika po traku.
Tako je Turingov stroj formalno opisan z nizom dveh abeced:
A=(a1, a2, a3, …, an) - zunanja abeceda, ki se uporablja za zapis izvornih podatkov
Q=(q1, q2, q3,…, qm) - interna abeceda, opisuje nabor stanj bralno-tiskalne naprave.
Vsaka celica traku lahko vsebuje znak iz zunanje abecede A = (a0,a1,…,an) (v našem primeru A=(0, 1))
Dovoljena dejanja Turingovega stroja so:
1) v celico traku zapišite poljuben simbol zunanje abecede (simbol, ki je bil tam prej, je prepisan)
2) premaknite se v sosednjo celico
3) spremenite stanje v eno od tistih, ki jih označuje interni abecedni simbol Q
Turingov stroj je avtomat, ki ga krmili miza.
Vrstice v tabeli ustrezajo simbolom izbrane abecede A, stolpci pa stanjem stroja Q = (q0,q1,…,qm). Na začetku delovanja je Turingov stroj v stanju q1. Stanje q0 je končno stanje; ko je v njem, stroj konča svoje delovanje.
Vsaka celica tabele, ki ustreza nekemu simbolu ai in nekemu stanju qj, vsebuje ukaz, sestavljen iz treh delov
· znak iz abecede A
· smer gibanja: “>” (desno), “<» (влево) или «.» (на месте)
· novo stanje stroja
V zgornji tabeli je abeceda A =(0, 1, _) (vsebuje 3 znake) in notranja abeceda Q=(q1, q2, q3, q4, q0), q0 je stanje, ki povzroči, da nosilec stop.
Razmislimo o več rešitvah težav. Turingov stroj lahko prenesete na spletni strani v razdelku.
Problem 1. Naj bo A=(0, 1, _). Na traku celice vsebujejo znake iz abecede v naslednjem vrstnem redu 0011011. Nosilec se nahaja nad prvim znakom. Treba je napisati program, ki bo 0 zamenjal z 1, 1 z 0 in vrnil voziček v prvotni položaj.
Zdaj pa definirajmo stanja prevoza. Imenujem jih "kočija želi nekaj narediti."
q1) Voziček naj gre 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 _, gre za 1 celico nazaj "želi nekaj drugega", tj. gre v stanje q2. Svoje sklepanje zapišimo v izvajalčevo tabelo. Za sintakso glejte pomoč programa)
q2) Zdaj pa opišimo »željo po kočiji« q2. Vrniti se moramo v prvotni položaj. Za to: če vidimo 1, ga zapustimo in ostanemo v stanju q2 (z isto željo doseči konec niza simbolov); če vidimo 0, jo zapustimo in nadaljujemo s premikanjem levo v stanju q2; vidimo _ - premakne se v desno za 1 celico. Zdaj ste tam, kjer se zahteva v pogojih naloge. gremo v stanje q0.
Program v akciji si lahko ogledate na videu:
Problem 2. Dano: končno zaporedje 0 in 1 (001101011101). Izpisati jih je treba za tem zaporedjem skozi prazno celico in jih v tem zaporedju nadomestiti z 0. Na primer:
Iz 001101011101 dobimo 000000000000 1111111.
Kot lahko vidite, je bilo za tem zaporedjem napisanih sedem enic, na njihovih mestih pa so ničle.
Začnimo razpravo. Ugotovimo, katere države potrebuje kočija in koliko.
q1) žaga 1 - popravi na ničlo in pojdi v drugo stanje q2 (uvede se novo stanje, da voziček ne spremeni vseh enic v ničle v enem prehodu)
q2) ne spreminjajte ničesar, premaknite se na konec zaporedja
q3) takoj ko kočija zagleda prazno celico, naredi korak v desno in nariše 1, če zagleda 1, se pomakne naprej in podpiše simbol na koncu. Takoj, ko narišem enoto, preidemo na stanje q4
q4) gremo skozi zapisane enote, ne da bi karkoli spremenili. Takoj, ko dosežemo prazno celico, ki ločuje zaporedje od enic, preidemo v novo stanje q5
q5) v tem stanju gremo na začetek zaporedja, ne da bi karkoli spremenili. Pridemo do prazne celice, se obrnemo in preidemo v stanje q1
Voziček prevzame stanje q0 v primeru, ko preide v stanju q1 do konca tega zaporedja in naleti na prazno celico.
Dobimo naslednji program:
V spodnjem videu si lahko ogledate Turingov stroj v akciji.
Do sedaj nam je bilo priročno sklicevati se na programerske izkušnje, ko govorimo o algoritmih, programih, tolmačih, izvajanju po korakih itd. To nam je omogočilo, da smo prezrli podrobnosti konstrukcije določenih algoritmov pod pretvezo, da jih bo bralec zlahka obnovil (ali vsaj verjeli, da ni vsak bralec v svojem življenju napisal Pascalovega tolmača v Pascalu).
Toda v nekaterih primerih to ni dovolj. Recimo, da želimo na primer dokazati algoritemsko neodločljivost nekega problema, katerega definicija ne pove ničesar o programih (v tem razdelku bomo na primer dokazali neodločljivost problema enakosti besed v polskupinah, definiranih z generatorji in relacije). Običajno se naredi tako. Pokažemo, da se problem ustavljanja zmanjša na ta problem. Da bi to naredili, modeliramo delovanje poljubnega algoritma glede na obravnavani problem (kaj to pomeni, bo jasno iz spodnjega primera). Ob tem nam je pomembno, da je definicija algoritma čim bolj enostavna.
Naš načrt je torej takšen. Opisali bomo dokaj enostavno določljiv razred strojev (lahko ga izberemo na različne načine; uporabili bomo t. i. Turingove stroje), nato izjavili, da je vsako izračunljivo funkcijo mogoče izračunati na takem stroju, nato pa pokazali, da je vprašanje zaustavitev Turingovega stroja se lahko reducira na vprašanje enakosti besed v polskupini.
Drugi razlog, zakaj so preprosti računalniški modeli pomembni (obstaja veliko različnih vrst Turingovih strojev, naslovnih strojev itd.), je povezan s teorijo računalniške kompleksnosti, ko nas začne zanimati dobavni rok programi. Toda to vprašanje presega klasično teorijo algoritmov.
Turingovi stroji: definicija
Turingov stroj ima neskončnost v obe smeri trak, razdeljen na kvadratke ( celice). Vsaka celica lahko vsebuje nekaj simbolov iz fiksnega (za dani stroj) končnega niza, imenovanega abeceda tega stroja. Eden od znakov abecede je poudarjen in se imenuje "presledek"; predpostavlja se, da je na začetku celoten trak prazen, to je zapolnjen s presledki.
Turingov stroj lahko spreminja vsebino traku s pomočjo posebnega bralnika in zapisovalnika. glave, ki se premika po traku. V vsakem trenutku je glava v eni od celic. Turingov stroj prejme informacijo iz glave o tem, kateri simbol vidi, in se glede na to (in glede na svoje notranje stanje) odloči, kaj bo naredil, torej kateri simbol bo zapisal v trenutno celico in kam naj se po tem premakne (levo, desno ali ostanite na mestu). Ob tem se spremeni tudi notranje stanje stroja (predpostavimo, da ima stroj, če ne štejemo traku, končen pomnilnik, torej končno število notranjih stanj). Dogovoriti se moramo tudi, kje začnemo in kdaj končamo delo.
Če želite torej definirati Turingov stroj, morate podati naslednje objekte:
Prehodna tabela je urejena na naslednji način: za vsak par je navedena trojka. Tukaj je premik ena od številk -1 (na levo), 0 (na mestu) in 1 (na desno). Tako je prehodna tabela funkcija tipa S x A -> S x A x (-1,0,1), definirana na tistih parih, v katerih stanje ni končno.
Ostaja še opis obnašanja Turingovega stroja. V vsakem trenutku je nekaj konfiguracijo, sestavljen iz vsebine traku (formalno gledano je vsebina traku poljubna preslikava Z -> A), trenutnega položaja glave (neko celo število) in trenutnega stanja stroja (element S). Preoblikovanje konfiguracije v naslednjo poteka po naravnih pravilih: v tabeli pogledamo, kaj je treba storiti za dano stanje in za dani simbol, to pomeni, ugotovimo novo stanje stroja, spremenimo simbol na določeno in nato premaknite glavo v levo, desno ali jo pustite na mestu. Poleg tega, če je novo stanje eno od končnih, se delovanje stroja konča. Ostalo je še, da se dogovorimo, kako posredujemo informacije vhodu stroja in kaj se šteje za rezultat njegovega dela. Predpostavili bomo, da abeceda stroja poleg presledka vsebuje znaka 0 in 1 (in morda še kakšne znake). Vhod in izhod stroja bosta končna zaporedja ničel in enic (binarne besede). Vhodna beseda se zapiše na prazen trak, glava stroja se postavi v prvo celico, stroj se postavi v začetno stanje in zažene. Če se stroj ustavi, je rezultat dvojiška beseda, ki jo lahko berete tako, da začnete na položaju glave in se premikate v desno (dokler se ne pojavi znak, ki ni 0 in 1).
Tako vsak Turingov stroj definira neko delno funkcijo na binarnih besedah. Naravno je klicati vse take funkcije izračunljiv na Turingovih strojih.
Turingovi stroji: razprava
Seveda naša definicija vsebuje veliko specifičnih podrobnosti, ki bi jih lahko spremenili. Na primer, trak je lahko neskončen samo v eno smer. Avtomobilu lahko daš dva traka. Upoštevamo lahko, da lahko stroj zapiše nov znak ali se premakne, vendar ne obojega. Abecedo lahko omejite, če na primer upoštevate, da mora imeti točno 10 znakov. Zahtevate lahko, da na koncu na traku ni ničesar razen rezultata dela (preostale celice morajo biti prazne). Vse zgoraj omenjene in številne druge spremembe ne spremenijo razreda funkcij, ki jih je mogoče izračunati na Turingovih strojih. Seveda je tudi nekaj neškodljivih sprememb. Če na primer avtomobilu prepoveš premikanje v levo, se bo to bistveno spremenilo, trak bo postal neuporaben, saj se na stare posnetke ne bo več mogoče vrniti.
Kako veste, katere spremembe so neškodljive in katere ne? Očitno je tukaj potrebnih vsaj malo izkušenj s praktičnim programiranjem na Turingovih strojih. Po tem si lahko že predstavljate zmogljivosti stroja, ne da bi napisali celoten program, ampak vas vodi le približen opis. Kot primer bomo opisali stroj, ki podvoji vhodno besedo (proizvede besedo XX, če je bila vhodna beseda X).
Če naprava vidi presledek (vhodna beseda je prazna), preneha delovati. V nasprotnem primeru si zapomni trenutni znak in ga označi (v abecedi bosta poleg znakov 0 in 1 tudi njuni »označeni različici« in ). Nato se pomakne v desno do prazne celice, nato pa tja zapiše kopijo zapomnitvenega simbola. Nato se premika levo, dokler ni označena; Ko se zakoplje v oznako, se premakne nazaj in si zapomni naslednji znak in tako naprej, dokler ne prepiše celotne besede.
Če imate nekaj izkušenj, lahko za vsemi temi stavki vidite posebne dele programa za Turingov stroj. Na primer, besede "zapomni si simbol in se premakne v desno" pomenijo, da obstajata dve skupini stanj, ena za situacijo, ko se spomni ničla, druga, ko se spomni ena, znotraj vsake skupine pa je premik na desno je programirano na prvo prazno celico.
Z malo več izkušenj lahko razumete, da je v tem opisu napaka; ni mehanizma za zaustavitev, ko se kopira celotna beseda, saj se kopije znakov ne razlikujejo od znakov izvirne besede. Jasno je tudi, kako popraviti napako: vpisati morate posebne znake in kot kopije, na zadnji stopnji pa izbrisati vse oznake.
77 . Pokažite, da je funkcija obračanja, ki obrne besedo nazaj, izračunljiva s Turingovim strojem.
Še en primer neformalnega sklepanja: razložimo, zakaj ni mogoče uporabiti dodatnih znakov razen 0, 1 in praznega znaka. Naj obstaja stroj z veliko abecedo N znakov. Izdelajmo nov stroj, ki bo simuliral delovanje starega, vendar bo vsaka celica starega ustrezala bloku k celic novega. Velikost bloka (število k) bo fiksna, tako da bodo lahko znotraj bloka vsi znaki velike abecede kodirani z ničlami in enicami. Izvirni znaki 0, 1 in prazno bodo kodirani kot 0, ki mu sledi (k-1) praznih znakov, 1, ki mu sledi (k-1) praznih znakov, in skupina k praznih znakov. Najprej morate črke vhodne besede premakniti za razdaljo k, kar lahko storite brez dodatnih znakov (ko dosežete skrajno črko, jo premaknete stran, nato ko pridete do naslednje, jo premaknete in skrajno, in tako naprej); le razumeti morate, da lahko konec besede prepoznate kot položaj, ki mu sledi več kot k praznih znakov. Jasno je, da moramo v tem procesu shraniti neko končno količino informacij v pomnilnik, tako da je to mogoče. Po tem je že možno korak za korakom simulirati delovanje originalnega stroja, za to pa zadostuje tudi končen pomnilnik (e končno število stanj), saj je le majhna okolica glave simuliranega stroja pomembna za nas. Nazadnje moramo rezultat stisniti nazaj.
Za zaključek razprave predstavljamo zgoraj obljubljeni argument v prid dejstvu, da je vsaka izračunljiva funkcija izračunljiva na Turingovem stroju. Naj obstaja funkcija, ki jo lahko oseba izračuna. Ob tem mora seveda uporabljati svinčnik papir, saj količino informacij količina, ki jo lahko shrani »v svojih mislih«, je omejena. Predvidevamo, da piše na ločene liste papirja. Poleg tekočega lista sta na desni in na levi sveženj papirjev; Trenutni list lahko položite v katerega koli od njih, ko ste končali delo z njim, in vzamete naslednjega iz drugega kupa. Moški ima svinčnik in radirko. Ker zelo majhne črke niso vidne, je število jasno razločljivih stanj lista končno in lahko domnevamo, da je v vsakem trenutku na listu zapisana ena črka iz neke končne (čeprav zelo velike) abecede. Človek ima tudi končen spomin, zato je njegovo stanje element neke končne množice. V tem primeru lahko sestavite kakšno tabelo, v kateri je zapisano, kako se bo končalo njegovo delo na listu z dano vsebino, začeto v danem stanju (kaj bo na listu, v kakšnem stanju bo oseba). in iz katerega paketa bo vzet naslednji list). Zdaj je jasno, da človeška dejanja natančno ustrezajo delovanju Turingovega stroja z veliko (vendar končno) abecedo in velikim (vendar končnim) številom notranjih stanj.
Turingov stroj je zbirka naslednjih objektov
- 1) zunanja abeceda A=(a 0 , a 1 , …, a n );
- 2) notranja abeceda Q=(q 1, q 2,…, q m) - množica stanj;
- 3) niz kontrolnih znakov (P, L, S)
- 4) trak, neskončen v obe smeri, razdeljen na celice, v vsako od katerih je mogoče v katerem koli diskretnem trenutku zapisati samo en znak iz abecede A;
- 5) krmilna naprava, ki je sposobna biti v enem od mnogih stanj
Simbol prazne celice je črka zunanje abecede a 0 .
Med stanji sta začetno q 1, v katerem stroj začne delovati, in končno (ali zaustavitveno stanje) q 0, v katerem se stroj enkrat ustavi.
Krmilna naprava se lahko premika levo in desno po traku, bere in zapisuje črke A v celice traku. Krmilna naprava deluje po ukazih, ki imajo naslednjo obliko
q i a j > a p X q k
Snemanje pomeni naslednje: če je krmilna naprava v stanju q i in je v pregledovani celici zapisana črka a j, potem (1) je v celico namesto j zapisan p, (2) stroj nadaljuje s pregledom naslednjega desne celice 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 je delovanje stroja po dogovoru v celoti določeno z njegovim stanjem q v danem trenutku in vsebino a celice, ki je v tem trenutku opazovana, potem za vsako možno konfiguracijo q i a j obstaja točno eno pravilo. Ni pravil le za končno stanje, v katerem se avto ustavi. Zato program Turingovega stroja z zunanjo abecedo A=(a0, a1, …, an) in notranjo Q=(q1, q2,…, qm) ne vsebuje več kot m (n+ 1) ukazov.
Beseda v abecedi A ali v abecedi Q ali v abecedi A Q je poljubno zaporedje črk ustrezne abecede. S k-to konfiguracijo razumemo sliko strojnega traku z informacijami, zbranimi na njem na začetku k-tega koraka (ali besedo v abecedi A, napisano na traku na začetku k-tega koraka) , ki označuje, katera celica se pregleduje v tem koraku in v kakšnem stanju je avto. Smiselne so le končne konfiguracije, tj. tiste, pri katerih so vse celice traku, z morebitno izjemo končnega števila, prazne. Konfiguracija se imenuje končna, če je stanje, v katerem se nahaja stroj, končno.
Če za začetno izberemo neko nedokončno konfiguracijo Turingovega stroja, bo naloga stroja, da zaporedno (korak za korakom) transformira začetno konfiguracijo v skladu s programom stroja, dokler ne dosežemo končne konfiguracije. Po tem se šteje, da je delo Turingovega stroja končano, rezultat dela pa je končna dosežena konfiguracija.
Rekli bomo, da stroj zazna neprazno besedo b v abecedi A (a 0) = (a 1, ..., a n) v standardnem položaju, če je zapisana v zaporednih celicah traku, vseh druge celice so prazne in stroj od tistih, v katerih je zapisana beseda b, vidi skrajno levo ali skrajno desno celico. Standardni položaj se imenuje začetni (končni), če je stroj, ki zazna besedo v standardnem položaju, v začetnem stanju q 1 (oziroma v stanju zaustavitve q 0).
Če obdelava besede b pripelje Turingov stroj v končno stanje, se reče, da je uporabna za b, sicer ni uporabna za b (stroj deluje neomejeno)
Poglejmo primer:
Podan je Turingov stroj z zunanjo abecedo A = (0, 1) (tukaj je 0 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 С q 2 ;
q 2 0 > 0 П q 0 ;
q 2 1 > 1 С q 1 ;
Ta program lahko napišemo s tabelo
V prvem koraku se uporabi ukaz: q 1 0 > 1 Л q 2 (krmilna naprava je v stanju q1, v nadzorovani celici je zapisana črka 0, v celici je namesto 0 zapisana 1, glava premakne 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 П q 0 ustvari konfiguracija
Ta konfiguracija je dokončna, ker je stroj v zaustavljenem stanju q 0 .
Tako prvotno besedo 110 stroj obdela v besedo 101.
Nastalo zaporedje konfiguracij lahko zapišemo na krajši način (vsebina nadzorovane celice je zapisana desno od stanja, v katerem je stroj trenutno):
11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1
Turingov stroj ni nič drugega kot določeno pravilo (algoritem) za preoblikovanje besed abecede A Q, tj. konfiguracije. Če želite torej definirati Turingov stroj, morate določiti njegovo zunanjo in notranjo abecedo, program ter navesti, kateri simboli označujejo prazno celico in končno stanje.
Po dvajsetih letih 20. stoletja izraz Računski stroj se nanaša na vse stroje, ki so opravljali delo človek-računalnik, zlasti tiste, ki so bile razvite po učinkovitih metodah Church–Turingove teze. Ta teza je formulirana kot: »Vsak algoritem je mogoče podati v obliki ustreznega Turingovega stroja ali delno rekurzivne definicije, razred izračunljivih funkcij pa sovpada z razredom delno rekurzivnih funkcij in z razredom funkcij, izračunljivih na Turingovih strojih. .” Na drug način je Church-Turingova teza opredeljena kot hipoteza o naravi mehanskih računalniških naprav, kot so elektronski računalniki. Vse možne izračune lahko naredite na računalniku, če ima dovolj časa in prostora za shranjevanje.
Mehanizmi, ki delajo na izračunih z neskončnostmi, so postali znani kot analogni tip. Vrednosti v takih mehanizmih so bile predstavljene z zveznimi numeričnimi količinami, na primer kotom vrtenja gredi ali razliko v električnem potencialu.
Za razliko od analognih strojev so imeli digitalni stroji možnost predstaviti stanje numerične vrednosti in shraniti vsako števko posebej. Digitalni stroji so pred izumom pomnilnika z naključnim dostopom uporabljali različne procesorje ali releje.
Ime Računski stroj od štiridesetih let prejšnjega stoletja ga je začel nadomeščati koncept računalnik. Ti računalniki so lahko izvajali izračune, ki so jih prej izvajali uradniki. Ker vrednosti niso več odvisne od fizičnih lastnosti (kot pri analognih strojih), je logični računalnik, ki temelji na digitalni strojni opremi, zmogel vse, kar je mogoče opisati čisto mehanski sistem .
Turingovi stroji so bili zasnovani tako, da formalno matematično definirajo, kaj je mogoče izračunati, ob upoštevanju omejitev računske moči. Če lahko Turingov stroj dokonča nalogo, se naloga šteje za Turingovo izračunljivo. Turing se je osredotočil predvsem na oblikovanje stroja, ki bi lahko določil, kaj je mogoče izračunati. Turing je zaključil, da dokler obstaja Turingov stroj, ki lahko izračuna približek števila, je ta vrednost števna. Poleg tega lahko Turingov stroj interpretira logične operatorje, kot so AND, OR, XOR, NOT in If-Then-Else, da ugotovi, ali
