Recimo, davno... Ali u stvari, prije stvaranja Turingove mašine, stvorene su mašine za obavljanje raznih radnji. Na primjer, trebate uzeti logaritam, pa, hajde da zakijemo mašinu koja će očitati broj i uzeti logaritam. Ili, recimo, treba da saberete dva broja - ovde imate mašinu za sabiranje dva broja. Da, i sada postoje takve mašine, na primjer, kalkulatori. Šta oni mogu da urade? Sabirajte, oduzimajte, množite i projektirajte - čak i uzmite kosinus ili sinus. Ispostavilo se da ove glupe mašine, osim radnji koje su u njima snimljene, nisu mogle i ne mogu ništa izvršiti.

Tako da bi bilo vrlo interesantno napraviti mašinu koja bi čitala ne brojeve ili simbole, već algoritam, i koja bi ga izvršavala, odnosno kreirala programabilnu mašinu. To je ono što je Turing uradio (reći ću da postoji mnogo takvih apstrakcija osim Turingove). I smislio je model takve mašine. Ispostavilo se da za izvršavanje složenih algoritama sve što vam je potrebno je karet, beskonačna traka i mogućnost mijenjanja vrijednosti ​​​napisanih na traci i kretanja po njoj. Ispostavilo se da se ova apstrakcija zapravo može pretvoriti u pravu mašinu, jedino sa ograničenjem da mašini ne možemo da obezbedimo beskrajnu traku, ali možemo napraviti veoma dugačku traku;)

Povlačenje. Zapravo, nema potrebe pričati kako radi Tjuringova mašina, kao što sam rekao, može se vrlo lako pronaći. Stoga ćemo pretpostaviti da već znate kako to funkcionira.

Pa, Turingova mašina izvodi neke jednostavne algoritme, to je neosporno. Ali šta je sa složenim? I, na primjer, kako organizirati ciklus koristeći MT? Ili kako shvatiti grananje? Ispostavilo se da postoje teoreme koje dokazuju da MT može izvoditi petlje i grane, što nam govori da sa vrlo jednostavnim mehanizmom možete sastaviti programe od jednostavnih blokova kao što su grane i petlje, što znači da možete programirati sve što se može programirano. I tu bi, u teoriji, trebalo da postoji objašnjenje da postoje i neizračunljive funkcije, pa samim tim i nerešivi problemi, a ti problemi se ne mogu rešiti uz pomoć MT. Evo kako.

Ali niko nije smislio ništa bolje od Turingove mašine, tako da svi programski jezici koje sada koristimo ne mogu programirati više od Turingove mašine. Odatle dolazi koncept Turingove potpunosti, što znači da je jezik (ili nešto drugo) Turing kompletan ako može napisati sve algoritme koji se pokreću na Turing mašini. I možete dokazati da je jezik Turing potpun tako što ćete napisati emulator Turingove mašine na njemu. Ovo su pite.

Sa tačke gledišta matematike, post je sranje, ali jasno je zašto nam je trebala Turingova mašina. Pa, zapravo pisanje algoritama za ovu mašinu je zanimljiva zagonetka. Vjerujem onima koji kažu da je nakon programiranja exp(x) na Turing mašini zaista shvatio šta je algoritam. Još nisam probao, ali je zanimljiv izazov.

Turingova mašina je kolekcija sljedećih objekata

• 1) eksterno pismo A=(a 0 , a 1 , …, a n );
• 2) interna abeceda Q=(q 1 , q 2 ,…, q m ) - skup stanja;
• 3) skup kontrolnih znakova (P, L, S)
• 4) beskonačna traka u oba smera, podeljena na ćelije, u svakoj od kojih se u bilo kom diskretnom trenutku može upisati samo jedan znak iz abecede A;
• 5) upravljački uređaj koji može biti u jednom od brojnih stanja

Simbol prazne ćelije je slovo spoljašnjeg alfabeta, a 0.

Među stanjima se razlikuje početno q 1, u kojem mašina počinje da radi, i konačno (ili stanje zaustavljanja) q 0, kada se mašina zaustavi.

Upravljački uređaj se može kretati lijevo i desno po traci, čitati i pisati znakove abecede A u ćelije trake. Upravljački uređaj radi prema naredbama koje imaju sljedeći oblik

q i a j > a p X q k

Snimanje znači sljedeće: ako je upravljački uređaj u stanju q i , a slovo a j je napisano u ćeliji koja se gleda, tada (1) u ćeliju se upisuje p umjesto a j , (2) mašina nastavlja sa pregledom sljedeću desnu ćeliju od one koja je upravo pregledana, ako je X=P, ili da pogledate sljedeću lijevu ćeliju, ako je X=L, ili nastavite sa pregledom iste ćelije trake, ako je X=C, (3) kontrolni uređaj ulazi stanje q k.

Pošto je rad mašine, po uslovu, potpuno određen njenim stanjem q, u datom trenutku, i sadržajem a ćelije koja se u tom trenutku posmatra, postoji tačno jedno pravilo za svaku moguću konfiguraciju q i a j. Ne postoje pravila samo za konačno stanje u kojem se mašina zaustavlja. Prema tome, program Turingove mašine sa spoljašnjim alfabetom A=(a0, a1, …, an) i unutrašnjim Q=(q1, q2,…, qm) ne sadrži više od m (n+ 1) instrukcija.

Riječ u abecedi A ili u abecedi Q ili u abecedi A Q je bilo koji niz slova odgovarajuće abecede. Pod k-tom konfiguracijom podrazumijevamo sliku trake mašine sa informacijama koje su se na njoj razvile do početka k-tog koraka (ili riječ u abecedi A napisanu na traci do početka k-ti korak), koji pokazuje koja se ćelija gleda u ovom koraku I u kakvom je stanju automobil? Samo konačne konfiguracije imaju smisla, tj. one u kojima su sve ćelije trake, sa mogućim izuzetkom konačnog broja, prazne. Za konfiguraciju se kaže da je konačna ako je stanje u kojem se mašina nalazi konačno.

Ako neko odabere bilo koju ne-konačnu konfiguraciju Turingove mašine kao početnu, onda je posao mašine da sekvencijalno (korak po korak) transformiše početnu konfiguraciju prema mašinskom programu sve dok se ne postigne konačna konfiguracija. Nakon toga smatra se da je rad Turingove mašine završen, a rezultat rada je postignuta konačna konfiguracija.

Reći ćemo da mašina percipira nepraznu riječ b u abecedi A (a 0 ) = (a 1 , ..., a n ) u standardnoj poziciji ako je napisana u uzastopnim ćelijama trake, sve ostale ćelije su prazne, a mašina gleda najlijevu ili krajnju desnu ćeliju od onih u kojima je napisana riječ b. Standardna pozicija se naziva početna (konačna) ako je mašina koja percipira riječ u standardnoj poziciji u početnom stanju q 1 (odnosno u stop stanju q 0).

Ako obrada riječi b dovede Turingovu mašinu do konačnog stanja, onda se kaže da se primjenjuje na b, inače se ne primjenjuje na b (mašina radi neograničeno)

Razmotrimo primjer:

S obzirom na Turingovu mašinu s vanjskim alfabetom A = (0, 1) (ovdje je 0 simbol prazne ćelije), abecedom unutrašnjih stanja Q = (q 0, q 1, q 2 ) i sa sljedećim funkcionalni dijagram (program):

q 1 0 > 1 L q 2 ;

q 1 1 > 0 S q 2 ;

q 2 0 > 0 P q 0 ;

q 2 1 > 1 C q 1;

Ovaj program se može napisati pomoću tabele

U prvom koraku radi naredba: q 1 0 > 1 L q 2 (upravljački uređaj je u stanju q1, a u ćeliji koja se prati piše slovo 0, u ćeliju se upisuje 1 umjesto 0, glava je pomaknut ulijevo, upravljački uređaj prelazi u stanje q2), u Kao rezultat, na stroju se kreira sljedeća konfiguracija:

Konačno, nakon izvršenja naredbe q 2 0 > 0 P q 0, kreira se konfiguracija

Ova konfiguracija je konačna jer je mašina u zaustavljenom stanju q 0 .

Dakle, originalnu riječ 110 mašina obrađuje u riječ 101.

Rezultirajući niz konfiguracija može se napisati na kraći način (sadržaj nadzirane ćelije upisuje se desno od stanja u kojem se mašina trenutno nalazi):

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

Tjuringova mašina nije ništa drugo do neko pravilo (algoritam) za pretvaranje reči abecede A Q, tj. konfiguracije. Dakle, da biste definisali Turingovu mašinu, potrebno je da navedete njenu spoljašnju i unutrašnju abecedu, program i naznačite koji od simbola označavaju praznu ćeliju i konačno stanje.

Tjuringova mašina jedno je od najintrigantnijih i najuzbudljivijih intelektualnih otkrića 20. veka. To je jednostavan i koristan apstraktni model računarstva (kompjuterskog i digitalnog) koji je dovoljno općenit da implementira bilo koji računalni zadatak. Zahvaljujući jednostavnom opisu i matematičkoj analizi, čini temelj teorijske računarske nauke. Ovo istraživanje je dovelo do dubljeg razumijevanja digitalnih računara i računanja, uključujući i spoznaju da postoje neki računski problemi koji se ne mogu riješiti na općim korisničkim računarima.

Alan Turing je nastojao da opiše najprimitivniji model mehaničkog uređaja koji bi imao iste osnovne mogućnosti kao kompjuter. Turing je prvi opisao mašinu 1936. godine u "O izračunljivim brojevima sa primenom na problem odlučivosti", koji se pojavio u Proceedings of the London Mathematical Society.

Turingova mašina je računarski uređaj koji se sastoji od glave za čitanje/pisanje (ili "skenera") kroz koju prolazi papirna traka. Traka je podijeljena na kvadrate, od kojih svaki nosi jedan simbol - "0" ili "1". Svrha mehanizma je da djeluje i kao sredstvo za ulazak i izlaz, i kao radna memorija za pohranjivanje rezultata međufaza proračuna. Od čega se sastoji uređaj Svaka takva mašina se sastoji od dvije komponente: Neograničena traka. Beskonačan je u oba smjera i podijeljen je na ćelije. Mašina je kontrolisani program, glava skenera za čitanje i upisivanje podataka. U svakom trenutku može biti u jednom od mnogih stanja.

Svaka mašina povezuje dva konačna niza podataka: abecedu ulaznih simbola A = (a0, a1, ..., am) i abecedu stanja Q = (q0, q1, ..., qp). Stanje q0 naziva se pasivno. Vjeruje se da uređaj završava svoj rad kada ga udari. Stanje q1 naziva se početno stanje - mašina počinje svoje proračune, nalazeći se na početku u njemu. Ulazna riječ se stavlja na traku po jedno slovo u redu na svakoj poziciji. Sa obe strane su samo prazne ćelije.

Kako mehanizam radi

Turingova mašina ima suštinsku razliku od računarskih uređaja - njen uređaj za skladištenje ima beskonačnu traku, dok za digitalne uređaje takav uređaj ima traku određene dužine. Svaku klasu zadataka rješava samo jedna konstruirana Turingova mašina. Zadaci drugačijeg tipa uključuju pisanje novog algoritma. Kontrolni uređaj, koji je u jednom stanju, može se kretati u bilo kojem smjeru duž trake. Zapisuje u ćelije i iz njih čita znakove konačnog alfabeta. Prilikom selidbe dodjeljuje se prazan element koji popunjava pozicije koje ne sadrže ulazne podatke. Algoritam za Turingovu mašinu definira pravila prijelaza za kontrolni uređaj. Postavljaju sljedeće parametre glavi pisanja-čitanja: pisanje novog karaktera u ćeliju, prijelaz u novo stanje, pomicanje lijevo ili desno duž trake.

Svojstva kretanja

Turingova mašina, kao i drugi računarski sistemi, ima svoje inherentne karakteristike, a one su slične svojstvima algoritama: Diskretnost. Digitalna mašina prelazi na sljedeći korak n+1 tek nakon što je prethodni završen. Svaki završeni korak označava šta će biti n+1. Jasnoća. Uređaj obavlja samo jednu radnju za istu ćeliju. Unosi znak iz abecede i čini jedan pokret: lijevo ili desno. Odlučnost. Svaka pozicija u mehanizmu odgovara jedinoj varijanti date šeme, a u svakoj fazi radnje i redoslijed njihovog izvršenja su nedvosmisleni. Efikasnost. Tačan rezultat za svaki korak određuje Turingova mašina. Program izvršava algoritam i u konačnom broju koraka prelazi u stanje q0. Masovni karakter. Svaki uređaj je definiran preko dozvoljenih riječi uključenih u abecedu. Funkcije Turingove mašine U rješavanju algoritama često je potrebno implementirati funkciju. U zavisnosti od mogućnosti pisanja lanca za proračun, funkcija se naziva algoritamski odlučiva ili neodlučiva. Kao skup prirodnih ili racionalnih brojeva, riječi u konačnoj abecedi N za mašinu, razmatra se niz skupa B - riječi u okviru abecede binarnog koda B=(0.1). Takođe, rezultat proračuna uzima u obzir „nedefinisanu“ vrednost koja se javlja kada se algoritam „zamrzne“. Za implementaciju funkcije važno je da postoji formalni jezik u konačnom alfabetu i da je problem prepoznavanja ispravnih opisa rješiv.

Softver uređaja

Programi za Tjuringov mehanizam raspoređeni su u tabele, u kojima prvi red i kolona sadrže simbole eksterne abecede i vrednosti mogućih unutrašnjih stanja automata - internog alfabeta. Tabelarni podaci su komande koje Turingova mašina prihvata. Zadaci se rješavaju na ovaj način: pismo koje čita glava u ćeliji nad kojom se trenutno nalazi i unutrašnje stanje glave automata određuju koja od naredbi mora biti izvršena. Konkretno, takva komanda se nalazi na preseku simbola eksterne abecede i unutrašnjeg alfabeta, koji se nalazi u tabeli.

Komponente za proračune

Da bi se izgradila Turingova mašina za rešavanje jednog specifičnog problema, potrebno je za nju definisati sledeće parametre. eksterno pismo. Ovo je neki konačni skup simbola, označen znakom A, čiji se sastavni elementi nazivaju slovima. Jedan od njih - a0 - mora biti prazan. Na primjer, abeceda Turingovog uređaja koji radi s binarnim brojevima izgleda ovako: A = (0, 1, a0). Neprekidni lanac slova-simbola snimljenih na traci naziva se riječ. Automat je uređaj koji radi bez ljudske intervencije. U Turing mašini ima nekoliko različitih stanja za rešavanje problema i, pod određenim uslovima, prelazi iz jedne pozicije u drugu. Skup takvih stanja je interna abeceda. On ima slovna oznaka oblika Q=(q1, q2...). Jedna od ovih pozicija - q1 - mora biti početna, odnosno ona koja pokreće program. Drugi neophodan element je stanje q0, koje je konačno stanje, odnosno ono koje prekida program i pomiče uređaj u zaustavljenu poziciju.

Skoči sto.

Ova komponenta je algoritam za ponašanje nosača uređaja, u zavisnosti od trenutnog stanja mašine i vrednosti karaktera koji se čita.-

Algoritam za automat

Nosač Turing uređaja tokom rada kontrolira program koji tokom svakog koraka izvodi sljedeći niz radnji: Upisivanje vanjskog znaka abecede na poziciju, uključujući i praznu, zamjenu elementa koji se nalazi u njemu, uključujući i prazan. Pomjerite jednu ćeliju koraka lijevo ili desno. Promijenite svoje unutrašnje stanje. Dakle, prilikom pisanja programa za svaki par znakova ili pozicija, potrebno je precizno opisati tri parametra: ai - element iz odabrane abecede A, smjer pomicanja nosača ("←" ulijevo, "→" u desno, "tačka" - nema pomeranja) i qk - novo stanje uređaja Na primer, komanda 1 "←" q2 ima vrednost "zameni karakter sa 1, pomeri glavu nosača ulevo za jednu ćeliju koraka i skoči na stanje q2".

Često rješavamo probleme različite složenosti: svakodnevne, matematičke itd. Neke je lako riješiti, neke zahtijevaju puno razmišljanja, a za neke nikada ne nađemo rješenje.

U opštem slučaju, metoda rješavanja problema (ako postoji) može se opisati korištenjem konačnog broja elementarnih akcija.

Na primjer, rješavanje kvadratne jednadžbe:

1. Pretvorite jednadžbu u kanonski oblik \(a x^2 + b x + c = 0\)
2. Ako je \(a=0\) , onda ovo linearna jednačina sa rješenjem \(x=\frac(-c)(b)\) . Problem riješen. U suprotnom, idite na korak 3.
3. Izračunajte diskriminanta \(D=b^2-4 a c\)
4. Izračunajte rješenja jednadžbi \(x_(1,2) = \frac(-b\pm\sqrt(D))(2 a)\). Problem riješen.

Možemo uvesti sljedeći intuitivni pojam algoritma:

Algoritam je skup instrukcija koje opisuju proceduru da izvođač postigne rezultat rješavanja problema u konačnom broju akcija, za bilo koji skup početnih podataka.

Ovo, naravno, nije stroga definicija, ali opisuje suštinu koncepta algoritma.

Algoritmi se kompajliraju na osnovu određenog izvođač, te stoga mora biti na jeziku koji izvođač može razumjeti.

Izvršilac algoritma može biti osoba, ili može biti kompjuter, ili neki drugi automat, na primjer, razboj.

Razlikuju se sljedeća svojstva algoritama:

Diskretnost algoritma treba da bude određeni niz odvojenih, dobro definisanih koraka (akcija). Svaka od ovih radnji mora biti konačna u vremenu. Odlučnost u svakom koraku algoritma, sljedeći korak je jedinstveno određen trenutnim stanjem sistema. Kao posljedica toga, na istim početnim podacima, algoritam uvijek vraća iste rezultate, bez obzira koliko puta se izvršava. Razumljivost Algoritam treba da bude formulisan na jeziku razumljivom izvođaču. Ako a mi pričamo o računaru, algoritam treba da koristi samo one naredbe koje su računaru poznate i čiji je rezultat radnji striktno definisan. Konačnost Algoritam se mora završiti u konačnom broju koraka. Masovni karakter algoritma mora biti primjenjiv na različite skupove ulaznih podataka. Drugim riječima, algoritam mora biti prikladan za rješavanje klasa zadataka. Vraćajući se na primjer kvadratne jednadžbe, algoritam je pogodan za rješavanje sve kvadratne jednačine, a ne samo jednu ili više. Algoritam mora završiti sa određenim rezultatom. Recimo, rješavanjem problema ili otkrivanjem odsustva rješenja. Ako algoritam ne dovede do rezultata, nije jasno zašto je uopće potreban.

Nije svaki način rješavanja problema algoritam. Recimo da algoritam ne podrazumijeva izbor. Na primjer, većina recepti oni nisu algoritmi, jer koriste fraze kao što su „posoliti po ukusu“. Kao posljedica toga, krše se zahtjev determinizma.

Ne postoji za svaki problem za koji postoji rješenje, postoji i algoritam rješenja. Na primjer, problem prepoznavanja slike još uvijek je u velikoj mjeri neriješen, a svakako ne uz pomoć rigoroznog algoritma. Međutim, korištenje neuronskih mreža daje prilično dobre rezultate.

Obično za algoritam postoje skupovi prihvatljivo ulazni podaci. Bilo bi čudno pokušati primijeniti algoritam za rješavanje jednačina na kuhanje večere, ili obrnuto.

Osim toga, ograničen je i skup mogućih radnji izvršitelja, jer da su neke radnje dozvoljene, onda bi među njima morale biti i „nedopustive“.

Stroga definicija algoritma

Gore navedena definicija algoritma nije stroga. To stvara određene poteškoće. Konkretno, sa takvom definicijom nemoguće je rigorozno dokazati da li je data klasa problema rješiva ​​algoritmom.

Ispostavilo se da postoji klasa algoritamski nerješivi problemi- problemi za koje je nemoguće kreirati algoritam za rješavanje. Ali da bi se rigorozno dokazala algoritamska neodlučivost, prvo se mora imati rigorozna definicija algoritma.

U 20-30-im godinama XX veka, različiti matematičari su radili na problemu rigorozne definicije algoritma, posebno Alan Turing, Emil Leon Post, Andrej Andrejevič Markov, Andrej Nikolajevič Kolmogorov, Alonzo Čerč i drugi. Njihov rad je na kraju doveo do nastanka i razvoja teorije algoritama, teorije izračunljivosti i raznih pristupa računanju, a usput i programiranju uopšte. Jedan od rezultata njihovog rada bila je pojava nekoliko striktnih definicija algoritma, uvedenih na različite načine, ali međusobno ekvivalentnih.

Detaljno ćemo se zadržati na Turingovoj definiciji i preletjeti na ekvivalentne definicije Posta, Churcha i Markova.

Turingova mašina

Da bi uveo formalnu definiciju algoritma, Turing je izumeo i opisao apstraktni računar nazvan Tjuringov računar ili jednostavno Turingova mašina.

Alan Turing (1912-1954)

Engleski matematičar, logičar, kriptograf, možda prvi "haker" na svijetu, stajao je na početku kompjuterske nauke i teorije vještačke inteligencije. Dao je značajan doprinos pobjedi savezničkih snaga u Drugom svjetskom ratu.

Kao ulaz u Turingovu mašinu se koriste riječi, sastavljen sa nekima abeceda, odnosno skup karaktera.

Izlaz Tjuringove mašine su takođe reči.

Poziva se riječ na koju se algoritam primjenjuje unos. Riječ koja proizlazi iz djela vikend.

Poziva se skup riječi na koji se algoritam primjenjuje opseg algoritma.

Strogo govoreći, nemoguće je dokazati da se bilo koji predmet može predstaviti u obliku riječi sastavljenih u nekom alfabetu - za to bi nam bila potrebna stroga definicija objekta. Međutim, može se provjeriti da se svaki nasumično odabran algoritam koji radi na objektima može transformirati tako da radi na riječima bez promjene suštine algoritma.

Opis Turingove mašine

Sastav Turingove mašine uključuje traku neograničenu u oba smjera, podijeljenu na ćelije, i kontrolni uređaj (također tzv. glava za čitanje/pisanje, ili jednostavno mašina) koji može biti u jednom od brojnih stanja. Broj mogućih stanja upravljačkog uređaja je konačan i tačno zadan.

Kontrolni uređaj se može kretati lijevo i desno duž trake, čitati i pisati znakove neke konačne abecede u ćelije. Dodjeljuje se poseban prazan znak, označen sa \(a_0\) ili \(\Lambda\) , koji ispunjava sve ćelije trake, osim onih od njih (konačan broj) na kojima su upisani ulazni podaci.

Upravljački uređaj radi prema prijelaznim pravilima, koja predstavljaju algoritam koji implementira ova Turingova mašina. Svako pravilo prijelaza nalaže mašini, ovisno o trenutnom stanju i simbolu uočenom u trenutnoj ćeliji, da upiše novi simbol u ovu ćeliju, pređe u novo stanje i pomjeri jednu ćeliju ulijevo ili udesno. Neka stanja Turingove mašine mogu se označiti kao terminalna, a prelazak u bilo koje od njih znači kraj rada, zaustavljanje algoritma.

Dok je Turingova mašina apstraktan koncept, dovoljno je lako zamisliti takvu mašinu (iako sa konačnom trakom), a postoje čak i demonstracione mašine poput ove:

Pogodno je predstaviti algoritam za Turingovu mašinu u obliku tabele: kolone tabele odgovaraju trenutnom (uočenom) karakteru na traci, redovi odgovaraju trenutnom stanju automata, a ćelije beleže naredbu koju automat mora izvršiti.

Komanda, zauzvrat, može imati sljedeću strukturu:

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

Prvo dolazi znak abecede, koji treba upisati u tekuću ćeliju \(a_k\), zatim je kretanje automata lijevo (L), desno (R) ili nigdje (ostani na mjestu, N) naznačeno. Na kraju je naznačeno novo stanje u koje bi automat \(q_m\) trebao ići.

Ćelija tabele je jasno određena trenutnim karakterom \(a_i\) i trenutnim stanjem automata \(q_j\) .

Složimo se da je na početku rada Turingova mašina unutra početno stanje, označen sa \(q_1\) , i kada se prelazi na stop stanje\(q_0\) algoritam je završen i mašina se zaustavlja.

Primjer

Napisaćemo algoritam za Turingovu mašinu koji će dodati ulaznoj reči, što je decimalni broj, 1.

Zatim, deskriptivno, algoritam se može formulirati na sljedeći način:

1. Krećući se udesno, pronađite početak riječi za unos
2. Krećući se udesno, pronađite kraj unesene riječi
3. Dodajte jedan trenutnom bitu ulazne riječi. Ako postoji broj od 0 do 8, izađite. U suprotnom, upišite 0, pomaknite se ulijevo i vratite se na korak 3.

Ovaj algoritam zapisujemo u obliku tabele. Abeceda se sastoji od brojeva od 0 do 9 i "praznog znaka" \(\Lambda\) . Također su nam potrebna 4 stanja automata, računajući stanje zaustavljanja, koje odgovaraju koracima opisa algoritma.

Slažemo se da je početno stanje \(1\) traženje početka ulazne riječi, \(2\) je traženje kraja ulazne riječi, \(3\) je dodavanje 1.

\(_(q_j)\backslash^(a_i)\)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛP1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	ΛL3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Pogledajmo kako ovaj algoritam radi na primjeru. Prvi red odgovara traci, drugi označava poziciju mašine i njeno trenutno stanje.

	1	9	9
1

U stanju 1, automat je iznad prazne ćelije. Odgovarajuća komanda iz tabele “ΛP1”, odnosno ostavite ćeliju praznu, pomerite se udesno i ostanite u stanju 1:

	1	9	9
	1

Sada automat posmatra vrijednost "1". Odgovarajuća komanda je "1H2", odnosno ostavite "1" u ćeliji, ne pomerajte se i pređite u stanje "2":

	1	9	9
	2

U stanju „2“, mašina primećuje vrednost „1“. Odgovarajuća komanda je „1P2“, odnosno ostavite „1“, pomerite se udesno i ostanite u stanju „2“:

Situacija se ponavlja:

Sada, u stanju 3 i posmatrajući simbol "9", automat izvršava naredbu "0L3":

	1	9	0
		3

Situacija se ponavlja:

Stanje “0” – stanje zaustavljanja. Algoritam je završen.

Formalni opis

Matematički, Turingova mašina se može opisati na sledeći način:

Turingova mašina (MT)

to je sistem forme \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), gdje

• \(A\) je konačan skup simbola MT alfabeta
• \(a_0 \u A\) – prazan znak abecede
• \(Q\) – konačan skup MT stanja
• \(q_1 \u Q\) – početno stanje MT
• \(q_0 \in Q\) – MT konačno stanje (stanje zaustavljanja)
• \(T = \(L, P, H\)\) je skup pomaka MT
• \(\tau\) – MT program, odnosno funkcija koja definira mapiranje \(\tau: A\puta Q\backslash \(q_0\) \strelica desno A\puta T \puta Q\)

Ključ u teoriji algoritama je Turingova teza.

Slobodno rečeno, Turingova teza je navedena na sljedeći način:

Turingova teza Za svaki algoritamski rješiv problem postoji Turingova mašina koja rješava ovaj problem. inače, za bilo koji algoritam postoji ekvivalentna Turingova mašina.

Turingova teza nam omogućava da govorimo o algoritmima koristeći prilično jednostavan matematički aparat. Štaviše, i sama Turingova mašina jeste univerzalni uređaj za aktiviranje, a sama mogućnost stvaranja ovakve zamišljene mašine postala je povod za razgovor o stvaranju univerzalne računarske tehnologije.

Definicije alternativnih algoritama

Osim Turingove mašine, postoji nekoliko nezavisnih definicija koje su ekvivalentne Turingovoj definiciji.

Konkretno, definicija putem Post mašine, kroz Churchov lambda račun, normalni Markovljev algoritam.

Hajde da razmotrimo ove metode.

Post Machine

Godinu dana nakon Turinga, američki matematičar Emil Leon Post nezavisno je predložio još jedan apstraktni univerzalni računar koji je donekle pojednostavljen Turingovom.

Pošta mašina radi sa dvocifrenim alfabetom, a unutrašnje stanje automata je zamenjeno sa programska linija.

Inače, Post mašina je slična Turing mašini: postoji automat, a postoji beskonačna traka sa ćelijama.

Post mašina može izvršiti sljedeće naredbe:

1. Napišite 1, idite na i-ti red programa
2. Upišite 0, idite na i-ti red programa
3. Pomaknite lijevo, idite na i-ti red programa
4. Pomaknite desno, idite na i-ti red programa
5. Uslovna grana: ako je posmatrana ćelija 0, idite na i-ti red programa, u suprotnom idite na j-ti red programa.
6. Stani.

Post mašina takođe ima nekoliko zabranjenih komandi:

1. Pišite u ćeliju 1 kada već postoji 1.
2. Pisanje u ćeliju 0 kada već postoji 0.

Takvi događaji dovode do kraha.

Sljedeća notacija se može koristiti za pisanje programa za poštansku mašinu:

1. ∨ i - upišite 1, idite na i-ti red programa
2. × i – upišite 0, idite na i-ti red programa
3. ← i - pomak lijevo, idite na i-ti red programa
4. → i - pomak udesno, idite na i-ti red programa
5. ? i; j- uslovna grana: ako u posmatranoj ćeliji postoji 0, idite na i-ti red programa, u suprotnom idite na j-ti red programa.
6. ! – stani.

Primjer programa:

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

Ovaj program će izbrisati prvu oznaku (1) desno od početne pozicije automata i zaustaviti automat u ćeliji s njegove lijeve strane.

Uglavnom, pošta je preteča imperativ programski jezici kao što su C, Fortran itd.

Post mašina je ekvivalentna Turing mašini. Drugim riječima, za bilo koji program Turingove mašine možete napisati ekvivalentni Post mašinski program i obrnuto.

Jedna važna posljedica ove ekvivalencije je da bilo koja abeceda se može svesti na binarni kod.

Slično Turingovoj tezi, postoji i Postova teza.

Postova teza Svaki algoritam se može predstaviti kao Post mašina.

Normalni Markovljev algoritam

Normalni Markovljevi algoritmi su dizajnirani da se primjenjuju na riječi u različitim alfabetima.

Definicija bilo kojeg normalnog algoritma sastoji se od dva dijela:

1. abeceda algoritam
2. Šema algoritam

Sam algoritam se primjenjuje na riječi, odnosno nizovi znakova abeceda.

Šema normalnog algoritma je konačno uređeni skup tzv zamjenske formule, od kojih svaki može biti jednostavno ili final. Jednostavne formule zamjene su izrazi oblika \(L\to D\) , gdje su \(L\) i \(D\) dvije proizvoljne riječi sastavljene od alfabeta algoritma (nazivaju se, redom, lijevi i desni dio formule supstitucije). Slično, konačne formule zamjene su izrazi oblika \(L\to\cdot D\) , gdje su \(L\) i \(D\) dvije proizvoljne riječi sastavljene od alfabeta algoritma.

Pretpostavlja se da pomoćni znakovi \(\to\) i \(\to\cdot\) ne pripadaju abecedi algoritma.

Proces primjene normalnog algoritma na proizvoljnu riječ \(V\) je sljedeći niz akcija:

1. Neka je \(V"\) riječ dobijena u prethodnom koraku algoritma (ili originalna riječ ako je trenutni korak prvi).
2. Ako među formulama zamjene nema nijedne, čiji bi lijevi dio bio uključen u \(V"\) , tada se operacija algoritma smatra završenom, a riječ \(V"\) smatra se rezultatom ovo djelo.
3. Inače, među formulama zamjene, čiji je lijevi dio uključen u \(V"\) , bira se prva.
4. Od svih mogućih reprezentacija riječi \(V"\) u obliku \(RLS\) (gdje je \(R\) prefiks, a \(L\) sufiks), jedan je odabran tako da \(R\ \) je najkraći , nakon čega se vrši zamjena \(V"=RDS\).
5. Ako je formula zamjene bila konačna, tada je algoritam završio rezultatom \(V"\) . U suprotnom idite na korak 1 (sljedeći korak).

Svaki normalni algoritam je ekvivalentan nekoj Turing mašini, i obrnuto, bilo koja Turing mašina je ekvivalentna nekom normalnom algoritmu.

Obično se naziva analogom Turingove teze za normalne algoritme princip normalizacije.

Primjer

Ovaj algoritam pretvara binarne brojeve u „jedne“ (u kojima je zapis nenegativnog cijelog broja N niz od N štapića). Na primjer, binarni broj 101 se pretvara u 5 štapića: |||||.

Abeceda: ( 0, 1, | ) Pravila:

1. 1 → 0|
2. |0 → 0||
3. 0 → (prazan niz)

Izvorna linija: 101 Izvršenje:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

Rekurzivne funkcije

Sistem ekvivalentan Turing mašini može se izgraditi na osnovu matematičkih funkcija. Da bismo to učinili, moramo uvesti sljedeće klase funkcija:

• primitivne rekurzivne funkcije
• opšte rekurzivne funkcije
• djelomično rekurzivne funkcije

Posljednja klasa će biti ista kao klasa Tjuringovih izračunljivih funkcija (tj. funkcije koje se mogu procijeniti algoritmom za Turingovu mašinu).

Definicija algoritma u terminima rekurzivnih funkcija u suštini leži u osnovi lambda računa, a pristup se zasniva na njemu. funkcionalno programiranje.

Primitivne rekurzivne funkcije

Klasa primitivnih rekurzivnih funkcija sadrži osnovne funkcije i sve funkcije dobijene od osnovnih pomoću operatora zamjene i primitivna rekurzija.

Osnovne karakteristike uključuju:

• Null funkcija \(O()=0\) je funkcija bez argumenata koja uvijek vraća \(0\) .
• Funkcija sukcesije \(S(x)=x+1\) je funkcija koja pripisuje bilo kojem prirodnom broju \(x\) sljedeći broj\(x+1\)
• Funkcije \(I_n^m(x_1,\ldots,x_n) = x_m\), gdje je \(0

Za konstruiranje ostalih funkcija klase koriste se sljedeći operatori:

• Zamjene. Za funkciju \(f\) od \(m\) varijabli i \(m\) funkcije \(g_1,\ldots,g_m\) od \(n\) varijabli svaka, rezultat zamjene \(g_k\) u \( 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\) varijabli.
• primitivna rekurzija. Neka je \(f(x_1,\ldots,x_n)\) funkcija \(n\) varijabli, a \(g(x_1,\ldots,x_(n+2))\) funkcija \( n+ 2\) varijable. Tada je rezultat primjene primitivnog rekurzivnog operatora na funkcije \(f\) i \(g\) funkcija \(h\) varijable \(n+1\) u obliku: \[ 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)) \]

Djelomično rekurzivne funkcije

Klasa djelomično rekurzivnih funkcija uključuje primitivne rekurzivne funkcije i, osim toga, sve funkcije koje su dobivene iz primitivnih rekurzivnih pomoću operatora minimizacije argumenata:

Operator minimizacije argumenta

Neka je \(f\) funkcija \(n\) varijabli \(x_i \in \mathbb(N)\) . Tada je rezultat primjene operatora minimizacije argumenata na funkciju \(f\) funkcija \(h\) argumenta \(n-1\), definirana kao:

\[ h(x_1,\ldots,x_(n-1)) = \min y, \] gdje \ To jest, \(h\) vraća minimalnu vrijednost posljednjeg argumenta funkcije \(f\) za koju je vrijednost \(f\) nula.

Dok su primitivne rekurzivne funkcije uvijek izračunljive, djelomično rekurzivne funkcije mogu biti nedefinirane za neke vrijednosti argumenata.

Strože, djelomično rekurzivne funkcije treba zvati "djelomično definirane rekurzivne funkcije", budući da su definirane samo na dijelu mogućih vrijednosti argumenata.

Opće rekurzivne funkcije

Opće rekurzivne funkcije su podklase svih djelomično rekurzivnih funkcija koje su definirane za bilo koje vrijednosti argumenata. Problem određivanja je li data djelomično rekurzivna funkcija općenito rekurzivna algoritamski neodlučivo. Ovo nas dovodi do teme teorije izračunljivosti i problema zaustavljanja.

Teorija izračunljivosti i problem zaustavljanja

Naša mašta u cjelini priznaje postojanje nerješivih problema, odnosno problema za koje je nemoguće sastaviti algoritam.

Teorija izračunljivosti bavi se proučavanjem takvih problema.

Primjeri algoritamski nerješivih problema su zaustavi problem i problem prepoznavanja izvodljivosti. Razmotrimo ih detaljnije.

Problem zaustavljanja S obzirom na opis algoritma A i ulaza \(x\) , potrebno je saznati da li se algoritam \(A\) zaustavlja na ulazu \(x\) .

Problem zaustavljanja je algoritamski neodlučiv. Dokažimo to.

\(\Delta\)

Neka postoji univerzalni algoritam koji rješava problem zaustavljanja. Razmotrimo onda klasu algoritama koja obrađuje tekstove koji opisuju algoritme.

Zbog postojanja univerzalnog algoritma za rješavanje problema zaustavljanja, postoji algoritam koji određuje da li će se algoritam iz navedene klase zaustaviti na svom tekstu ili ne. Označite takav algoritam \(B\) .

Napravimo algoritam \(C\) za koji je ulaz tekst algoritma \(A\) koji obrađuje vlastiti tekst:

1. Pokrenite algoritam \(B\) na \(A\) .
2. Ako algoritam \(B\) utvrdi da će se \(A\) zaustaviti na svom tekstu, idite na korak 1. U suprotnom idite na korak 3.
3. Kraj \(C\) algoritma.

Pokušavajući primijeniti algoritam \(C\) na algoritam \(C\), dolazimo do očigledne kontradikcije: ako se \(C\) zaustavi na svom tekstu, onda se ne može zaustaviti, i obrnuto. Dakle, ne postoji \(B\) algoritam. \(\ne \Delta\)

Općenitija formulacija problema zaustavljanja je problem određivanja izvodljivosti.

Problem prepoznavanja izvodljivosti

Neka se definiše određena abeceda, riječi (formule) ove abecede i sistem formalnih transformacija nad riječima ove abecede (tj. izgradi se logički račun)

Postoji li za bilo koje dvije riječi \(R\) i \(S\) deduktivni lanac koji vodi od \(R\) do \(S\) unutar datog logičkog računa?

Godine 1936. Alonzo Church je dokazao Churchovu teoremu.

Churchov teorem Problem prepoznavanja deducibilnosti je algoritamski neodlučiv.

Church je koristio formalizam lambda računa da to dokaže. Godine 1937, nezavisno od njega, Turing je dokazao istu teoremu koristeći formalizam Turingove mašine.

Pošto su sve definicije algoritama ekvivalentne jedna drugoj, postoji sistem pojmova koji nije vezan za konkretnu definiciju algoritma i radi sa konceptom izračunljiva funkcija.

Izračunava funkcija je funkcija koja se može procijeniti algoritmom.

Postoje problemi u kojima se odnos između ulaznih i izlaznih podataka ne može opisati algoritmom. Takve karakteristike su neizračunljiv.

Primjer neizračunljive funkcije

Uzmite funkciju \(h(n)\) definiranu za \(\forall n \in \mathbb(N)\) kako slijedi:

\[ h(n) = \begin(slučajevi) 1, & \text(ako )\pi\text( sadrži sekvencu tačno )n\text(9.) \\ 0, & \text(u suprotnom) \end( slučajevi) \]

Možemo dobiti vrijednost \(1\) za ovu funkciju, međutim, da bismo dobili vrijednost \(0\) , moramo provjeriti beskonačno decimalno proširenje broja \(\pi\) , što je očigledno nemoguće u konačnom vrijeme. Ova funkcija stoga nije izračunljiva.

Izraz nakon 1920-ih Računska mašina odnosi se na sve mašine koje su radile ljudski kompjuter, posebno one koje su razvijene prema efikasnim metodama Church-Turingove teze. Ova teza je formulisana kao: „Svaki algoritam se može dati u obliku odgovarajuće Turingove mašine ili delimično rekurzivne definicije, a klasa izračunljivih funkcija se poklapa sa klasom delimično rekurzivnih funkcija i sa klasom funkcija izračunavih na Turingovim mašinama. " . Na drugi način, Church-Turingova teza je definirana kao hipoteza o prirodi mehaničkih računarskih uređaja, kao što su elektronički računari. Bilo koji mogući proračun može se obaviti na računaru, pod uslovom da ima dovoljno vremena i prostora za skladištenje.

Mehanizmi koji rade na proračunima beskonačnosti postali su poznati kao analogni tip. Vrijednosti u takvim mehanizmima bile su predstavljene kontinuiranim numeričkim vrijednostima, na primjer, kutom rotacije osovine ili razlikom električnog potencijala.

Za razliku od analognih mašina, digitalne mašine su imale mogućnost da predstave stanje numeričke vrednosti i pohranjuju svaku cifru zasebno. Digitalne mašine su koristile različite procesore ili releje pre pronalaska memorijskog uređaja sa slučajnim pristupom.

Ime Računska mašina od 1940-ih je koncept počeo da se zamenjuje kompjuter. Ti kompjuteri su mogli da izvrše proračune koje su radili službenici. Pošto vrijednosti više nisu ovisile o fizičkim karakteristikama (kao u analognim mašinama), logički kompjuter baziran na digitalnom hardveru mogao je učiniti sve što se može opisati. čisto mehanički sistem .

Turingove mašine su dizajnirane da formalno definišu matematički šta se može izračunati s obzirom na ograničenja računske sposobnosti. Ako Turingova mašina može izvršiti zadatak, onda se za zadatak kaže da je Turing izračunljiv. Turing se uglavnom fokusirao na dizajniranje mašine koja bi mogla odrediti šta se može izračunati. Turing je zaključio da sve dok postoji Turingova mašina koja može izračunati aproksimaciju broja, ta vrijednost je prebrojiva. Osim toga, Turingova mašina može interpretirati logičke operatore kao što su AND, OR, XOR, NOT i "If-Onda-Else" kako bi utvrdila da li