Do sada nam je bilo zgodno da se pozivamo na iskustvo programera kada govorimo o algoritmima, programima, interpretatorima, izvršavanju korak po korak, itd. To nam je omogućilo da zanemarimo detalje konstrukcije određenih algoritama pod izgovorom da će ih čitalac lako vratiti (ili barem vjerovati da nije svaki čitatelj u svom životu napisao Pascal interpreter na Pascalu).

Ali u nekim slučajevima to nije dovoljno. Neka, na primjer, želimo dokazati algoritamsku neodlučivost nekog problema čija definicija ne govori ništa o programima (u ovom dijelu ćemo, na primjer, dokazati neodlučivost problema jednakosti riječi u polugrupama definisanim sa generatori i odnosi). Obično se radi ovako. Pokazujemo da se problem zaustavljanja svodi na ovaj problem. Da bismo to učinili, modeliramo rad proizvoljnog algoritma u smislu problema koji se razmatra (šta to znači bit će jasno iz primjera u nastavku). Istovremeno, važno nam je da definicija algoritma bude što jednostavnija.

Naš plan je ovo. Opisat ćemo prilično jednostavno definiranu klasu strojeva (može se birati na različite načine; koristit ćemo takozvane Turingove mašine), zatim proglasiti da se svaka izračunljiva funkcija može izračunati na takvoj mašini, a zatim pokazati da je pitanje zaustavljanje Turingove mašine može se svesti na pitanje jednakosti riječi u polugrupi.

Drugi razlog zašto su jednostavni računski modeli važni (postoji mnogo različitih tipova Turingovih mašina, adresarskih mašina, itd.) vezan je za teoriju računske složenosti, kada počinjemo da nas zanima vodeće vrijeme programe. Ali ovo pitanje ide dalje od klasične teorije algoritama.

Turing mašine: definicija

Turingova mašina ima beskonačnost u oba smjera traka, podijeljen na kvadrate ( ćelije). Svaka ćelija može sadržavati neki simbol iz fiksnog (za datu mašinu) konačnog skupa tzv abeceda ove mašine. Jedan od znakova abecede je istaknut i naziva se "razmak"; pretpostavlja se da je u početku cijela traka prazna, odnosno ispunjena razmacima.

Turingova mašina može promijeniti sadržaj trake koristeći poseban čitač i pisač. glave, koji se kreće duž trake. U svakom trenutku glava se nalazi u jednoj od ćelija. Turingova mašina prima informaciju od glave o tome koji simbol vidi i u zavisnosti od toga (i od svog unutrašnjeg stanja) odlučuje šta da radi, odnosno koji simbol da upiše u tekuću ćeliju i kuda da se pomeri nakon toga (levo, desno ili ostanite na lokaciji). Istovremeno se menja i unutrašnje stanje mašine (pretpostavljamo da mašina, ne računajući traku, ima konačnu memoriju, odnosno konačan broj unutrašnjih stanja). Takođe moramo da se dogovorimo gde počinjemo i kada završavamo posao.

Dakle, da biste definirali Turingovu mašinu, morate navesti sljedeće objekte:

Tablica prijelaza je uređena na sljedeći način: za svaki par je naznačena trojka. Ovdje je pomak jedan od brojeva -1 (lijevo), 0 (na mjestu) i 1 (desno). Dakle, prijelazna tablica je funkcija tipa S x A -> S x A x (-1,0,1) definirana na onim parovima u kojima stanje nije konačno.

Ostaje da opišemo ponašanje Turingove mašine. U svakom trenutku ih ima konfiguraciju, koji se sastoji od sadržaja trake (formalno gledano, sadržaj trake je proizvoljno preslikavanje Z -> A), trenutne pozicije glave (neki cijeli broj) i trenutnog stanja mašine (element S). Transformacija konfiguracije u sljedeću odvija se prema prirodnim pravilima: gledamo u tablicu šta treba učiniti za dato stanje i za dati simbol, odnosno saznajemo novo stanje mašine, mijenjamo simbol na navedeni, a zatim pomaknite glavu lijevo, desno ili je ostavite na mjestu. Štaviše, ako je novo stanje jedno od konačnih, rad mašine se završava. Ostaje da se dogovorimo kako dajemo informacije na ulaz mašine i šta se smatra rezultatom njenog rada. Pretpostavićemo da abeceda mašine, pored razmaka, sadrži znakove 0 i 1 (i eventualno neke druge znakove). Ulaz i izlaz mašine će biti konačni nizovi nula i jedinica (binarne reči). Ulazna riječ se upisuje na praznu traku, glava mašine se postavlja u prvu ćeliju, mašina se dovodi u početno stanje i pokreće. Ako se mašina zaustavi, rezultat je binarna riječ, koja se može čitati počevši od položaja glave i pomjerajući se udesno (sve dok se ne pojavi znak koji nije 0 i 1).

Dakle, bilo koja Turingova mašina definira neku parcijalnu funkciju na binarnim riječima. Prirodno je pozvati sve takve funkcije izračunljiv na Turingovim mašinama.

Turingove mašine: diskusija

Naravno, naša definicija sadrži mnogo specifičnih detalja koji se mogu promijeniti. Na primjer, traka može biti beskonačna samo u jednom smjeru. Možete dati automobilu dvije trake. Možemo smatrati da mašina može ili napisati novi karakter ili se pomeriti, ali ne oboje. Možete ograničiti abecedu s obzirom, recimo, da mora imati tačno 10 znakova. Možete zahtijevati da na kraju na traci nema ništa osim rezultata rada (preostale ćelije moraju biti prazne). Sve gore navedene i mnoge druge promjene ne mijenjaju klasu funkcija izračunljivih na Turingovim mašinama. Naravno, postoje i neke bezazlene promjene. Na primjer, ako zabranite automobilu da se kreće lijevo, to će radikalno promijeniti stvari; u suštini, traka će postati beskorisna, jer više neće biti moguće vratiti se na stare snimke.

Kako znate koje su promjene bezopasne, a koje nisu? Očigledno je ovdje potrebno određeno iskustvo u praktičnom programiranju na Turingovim mašinama, barem malo. Nakon toga, već možete zamisliti mogućnosti mašine bez pisanja cijelog programa, već vodeći se samo približnim opisom. Kao primjer, opisat ćemo mašinu koja udvostručuje ulaznu riječ (proizvodi riječ XX ako je ulaz riječ X).

Ako mašina vidi razmak (ulazna riječ je prazna), prestaje raditi. Ako ne, pamti trenutni znak i stavlja oznaku (u abecedi će pored znakova 0 i 1 biti i njihove „označene varijante“ i ). Zatim se pomiče udesno do prazne ćelije, nakon čega upisuje kopiju memorisanog simbola. Zatim se pomiče lijevo dok se ne označi; Zakopavši se u znak, vraća se nazad i pamti sledeći lik, i tako redom, sve dok ne kopira celu reč.

Imajući određeno iskustvo, možete vidjeti iza svih ovih fraza specifične dijelove programa za Turingovu mašinu. Na primjer, riječi “pamti simbol i pomiče se udesno” znače da postoje dvije grupe stanja, jedno za situaciju kada se pamti nula, drugo kada se pamti jedinica, a unutar svake grupe kretanje prema desno je programirano na prvu praznu ćeliju.

Uz malo više iskustva, možete shvatiti da postoji greška u ovom opisu; ne postoji mehanizam za zaustavljanje kada se cijela riječ kopira, budući da se kopije znakova ne razlikuju od znakova originalne riječi. Također je jasno kako ispraviti grešku: potrebno je napisati posebne znakove i kao kopije, a u posljednjoj fazi izbrisati sve oznake.

77 . Pokažite da je funkcija preokreta, koja okreće riječ unatrag, Turingova mašina izračunljiva.

Još jedan primjer neformalnog razmišljanja: objasnimo zašto je moguće ne koristiti dodatne znakove osim 0, 1 i praznog znaka. Neka postoji mašina sa velikom abecedom od N znakova. Napravimo novu mašinu koja će simulirati rad stare, ali će svaka ćelija stare odgovarati bloku od k ćelija nove. Veličina bloka (broj k) bit će fiksirana tako da unutar bloka svi znakovi velike abecede mogu biti kodirani nulama i jedinicama. Originalni znakovi 0 , 1 i prazno će biti kodirani kao 0 praćeni (k-1) praznim znakovima, 1 praćenim (k-1) praznim znakovima i grupom od k praznih znakova. Prvo treba da razmaknete slova ulazne riječi za razmak k, što se može učiniti bez dodatnih simbola (kada dođete do vanjskog slova, odmaknite ga, zatim kada dođete do sljedećeg, pomaknite ga i krajnje slovo jedan, i tako dalje); samo trebate razumjeti da možete identificirati kraj riječi kao poziciju iza koje slijedi više od k praznih znakova. Jasno je da u ovom procesu moramo pohraniti neku konačnu količinu informacija u memoriju, tako da je to moguće. Nakon toga, već je moguće simulirati rad originalne mašine korak po korak, a za to je dovoljna i konačna memorija (e. konačan broj stanja), jer je samo malo susjedstvo glave simulirane mašine važno za nas. Konačno, rezultat je potrebno ponovo komprimirati.

Da zaključimo raspravu, predstavljamo argument koji je gore obećan u prilog činjenici da je bilo koja izračunljiva funkcija izračunljiva na Turingovom stroju. Neka postoji funkcija koju osoba može izračunati. U isto vrijeme, prirodno mora koristiti olovku i papir, jer količina informacija količina koju može pohraniti "u svom umu" je ograničena. Pretpostavićemo da piše na odvojenim listovima papira. Pored tekućeg lista, desna je hrpa papira, a lijevo hrpa; Možete staviti trenutni list u bilo koji od njih, nakon što ste završili rad s njim, i uzeti sljedeći iz druge hrpe. Čovjek ima olovku i gumicu. Budući da se vrlo mala slova ne vide, broj jasno razlučivih stanja lista je konačan, te možemo pretpostaviti da je u svakom trenutku jedno slovo iz neke konačne (iako vrlo velike) abecede napisano na listu. Osoba ima i konačno pamćenje, pa je njegovo stanje element nekog konačnog skupa. U tom slučaju možete napraviti neku tabelu u kojoj je zapisano kako će se završiti njegov rad na listu sa datim sadržajem, započet u datom stanju (šta će biti na listu, u kakvom će se stanju osoba nalaziti i iz kojeg pakovanja će se uzeti sljedeći list). Sada je jasno da ljudske akcije tačno odgovaraju radu Turingove mašine sa velikim (ali konačnim) alfabetom i velikim (ali konačnim) brojem unutrašnjih stanja.

Uvod

Godine 1936. Alan Turing je predložio apstraktni univerzalni izvršilac da razjasni koncept algoritma. Njegova apstraktnost leži u činjenici da predstavlja logičku računsku konstrukciju, a ne pravu računarsku mašinu. Termin "univerzalni izvođač" znači da određeni izvođač može imitirati bilo kojeg drugog izvođača. Na primjer, operacije koje izvode stvarni računari mogu se simulirati na univerzalnom izvršiocu. Nakon toga, računski dizajn koji je izmislio Turing nazvan je Turingova mašina.

Svrha ovog kursa je kreiranje programa koji implementira Turingovu mašinu u funkcionalnom programskom jeziku Haskell. Kao primjer, implementiraćemo Turingovu mašinu dizajniranu da pomnoži decimalni broj sa 2.

Da bi se postigao ovaj cilj, potrebno je riješiti sljedeće zadatke: proučiti principe rada Turingove mašine, njenu strukturu, razmotriti algoritamski nerješive probleme, odabrati strukturu podataka, opisati funkcije koje se implementiraju, a također dati primjere programa .

Osnovne odredbe Turingove mašine

Tjuringova mašina je dobila ime po engleskom matematičaru Alanu Tjuringu, koji je 1937. godine predložio metod za formalno specificiranje algoritama pomoću neke apstraktne mašine. Suština rada se svodi na sljedeće. Postoji potencijalno beskonačna traka, podijeljena na ćelije, od kojih svaka može sadržavati jedan znak iz neke konačne abecede. Turingova mašina ima glavu za čitanje/pisanje koja vam omogućava da pročitate znak u trenutnoj ćeliji, upišete znak u ćeliju i pomerite glavu levo ili desno u susednu ćeliju. Mašina radi diskretno, u ciklusima, i u svakom ciklusu se nalazi u jednom od mogućih stanja kojih ima konačan broj. Za svaki par (stanje, simbol koji se posmatra) definiše se trojka (znak koji se upisuje, pokret glave, novo stanje). Prije početka rada, Turingova mašina je u početnom stanju, a glava za čitanje i upisivanje skenira najlijevu nepraznu ćeliju na traci. Tako, dok pregledava sljedeći simbol, mašina upisuje novi simbol (možda isti), pomiče glavu lijevo, desno ili ostaje na mjestu i prelazi u novo stanje ili ostaje u istom stanju.

Tjuringova mašina se sastoji od tri dela: trake, glave za čitanje (upisivanje) i logičkog uređaja, kao što je jasno prikazano na slici 1.

Traka se ponaša kao vanjska memorija. Smatra se neograničenim (beskonačnim). Samo ovo ukazuje da je Turingova mašina model uređaja, jer nijedan pravi uređaj ne može imati beskonačnu memoriju.

Slika 1 - Krug Turingove mašine

Turingova mašina radi u nekoj proizvoljnoj konačnoj abecedi A = (_, a1…an) - ova abeceda se naziva eksterna. Sadrži poseban znak - _, koji se zove prazan znak - slanjem u bilo koju ćeliju briše se znak koji je prethodno bio tamo i ostavlja ćeliju praznom. U svaku ćeliju trake može se upisati samo jedan znak. Informacija pohranjena na traci predstavljena je konačnim nizom vanjskih znakova abecede osim praznog znaka.

Glava se uvijek nalazi iznad jedne od ćelija trake. Rad se odvija u ciklusima (koracima). Sistem komandi koje izvršava glava je krajnje jednostavan: u svakom taktu zamenjuje znak u posmatranoj ćeliji ai znakom aj. U ovom slučaju moguće su kombinacije:

1) aj = ai - znači da se predznak u posmatranoj ćeliji nije promenio;

2) ai ? _, aj = _ - znak pohranjen u ćeliji se zamjenjuje praznim, tj. izbrisani;

3) ai = _, aj ? _ - prazan znak se zamjenjuje nepraznim (sa brojem j u abecedi), tj. umetnut je znak;

4) ai ? aj ? _ - odgovara zamjeni jednog znaka drugim.

Dakle, Turingova mašina implementira sistem izuzetno jednostavnih naredbi za obradu informacija. Ovaj sistem obrade komandi upotpunjen je i izuzetno jednostavnim sistemom komandi za pomeranje trake: jedna ćelija ulevo, jedna ćelija udesno i ostati na mestu, tj. Kao rezultat izvršenja naredbe, adresa ćelije koja se nadgleda može se promijeniti u 1 ili ostati nepromijenjena.

Međutim, iako dolazi do stvarnog pomeranja trake, obično se uzima u obzir pomeranje glave u odnosu na deo koji se posmatra. Iz tog razloga, komanda za pomicanje trake ulijevo je označena R (desno), pomicanje udesno je L (lijevo), a nijedan pomak nije označen kao S (Stop). Posebno ćemo govoriti o pomicanju glave i smatrati R, L i S komandama za njeno kretanje.

Elementarna priroda ovih naredbi znači da ako je potrebno pristupiti sadržaju određene ćelije, on se nalazi samo kroz lanac pojedinačnih pomaka jedne ćelije. Naravno, ovo značajno produžava proces obrade, ali vam omogućava da bez numerisanja ćelija i korišćenja komandi idete na adresu, tj. smanjuje broj zaista elementarnih koraka, što je važno sa teorijske tačke gledišta.

Obrada informacija i izdavanje komandi za pisanje znaka, kao i pomeranje trake u Turing mašini, obavlja se pomoću logičkog uređaja (LU). LU može biti u jednom od stanja koje formira konačan skup i označava se sa Q =(q1...qm, q0), a stanje q0 odgovara završetku rada, a q1 je početno (početno) stanje . Q zajedno sa znakovima R, L, S čine internu abecedu mašine. LU ima dva ulazna kanala (ai, qi) i tri izlazna kanala (ai+1, qi+1, Di+1). LU dijagram Turingove mašine je prikazan na slici 2.

Slika 2 - LU dijagram Turingove mašine

Neophodno je razumjeti sklop na sljedeći način: u ciklusu i, na jedan ulaz LU se dovodi znak iz trenutno gledane ćelije (ai), a napaja se znak koji pokazuje stanje LU u trenutku (qi). na drugi ulaz. U zavisnosti od primljene kombinacije znakova (ai, qi) i postojećih pravila obrade, LU generiše i šalje novi znak (ai+1) u posmatranu ćeliju preko prvog izlaznog kanala, izdaje komandu za pomeranje glave (Di +1 iz R, L i S), a također daje komandu za prelazak u sljedeće stanje (qi+1). Dakle, elementarni korak (ciklus) rada Turingove mašine je sledeći: glava čita simbol iz ćelije koja se prati i, u zavisnosti od njenog stanja i simbola za čitanje, izvršava naredbu koja određuje koji simbol treba napisati ( ili obrisati) i koji pokret napraviti . Istovremeno, glava prelazi u novo stanje. Dijagram rada takve mašine prikazan je na slici 3.

Slika 3 - Dijagram rada Turingove mašine

Ovaj dijagram odražava podjelu memorije na eksternu i internu. Vanjski je predstavljen, kao što je naznačeno, u obliku beskrajne trake - dizajniran je za pohranjivanje informacija kodiranih u simbolima vanjske abecede. Interna memorija je predstavljena sa dvije ćelije za pohranjivanje sljedeće komande tokom trenutnog ciklusa takta: sljedeće stanje (qi+1) se prenosi na Q iz LU i pohranjuje, a komanda pomaka (Di+1) je pohranjena u D . Iz Q preko povratne linije qi+1 ulazi u LU, a iz D se naredba šalje aktuatoru koji po potrebi pomiče traku za jednu poziciju udesno ili ulijevo.

Opšte pravilo po kojem radi Turingova mašina može se predstaviti sljedećom notacijom: qi aj > qi" aj" Dk, tj. nakon gledanja simbola aj od strane glave u stanju qi, simbol aj se upisuje u ćeliju, glava prelazi u stanje qi, a traka pravi pokret Dk. Za svaku kombinaciju qi aj postoji tačno jedno pravilo transformacije (nema pravila samo za q0, pošto se mašina zaustavlja kada dođe u ovo stanje). To znači da logički blok implementira funkciju koja povezuje svaki par ulaznih signala qi aj sa jednom i samo jednom trostrukom izlaznih signala qi "aj" Dk - naziva se logičkom funkcijom mašine i obično se predstavlja u obliku tabela (funkcionalni dijagram mašine), čiji su stupci označeni simbolima stanja, a linije su znakovi eksternog alfabeta. Ako postoji n znakova eksternog alfabeta, a broj LU stanja je m, tada će, očigledno, ukupan broj pravila transformacije biti n×m.

Specifična Turing mašina se specificira nabrajanjem elemenata skupova A i Q, kao i logičke funkcije koju LU implementira, tj. skup pravila transformacije. Jasno je da može postojati beskonačno mnogo različitih skupova A, Q i logičkih funkcija, tj. a postoji i beskonačno mnogo Turingovih mašina.

Takođe je potrebno uvesti pojam konfiguracije mašine, tj. skupovi stanja svih ćelija trake, LU stanja i položaja glave. Jasno je da konfiguracija mašine može sadržavati bilo koji broj znakova iz eksterne abecede i samo jedan znak iz interne.

Prije početka rada, početna riječ a konačne dužine u abecedi A upisuje se na praznu traku; glava se instalira iznad prvog znaka riječi a, LU se prenosi u stanje q1 (tj. početna konfiguracija izgleda kao q1a). Pošto je u svakoj konfiguraciji implementirano samo jedno pravilo transformacije, početna konfiguracija jedinstveno određuje sve naredne operacije mašine, tj. cijeli niz konfiguracija do prestanka rada.

Ovisno o početnoj konfiguraciji, moguća su dva scenarija:

1) nakon konačnog broja ciklusa, mašina se zaustavlja na komandi za zaustavljanje; u ovom slučaju, konačna konfiguracija koja odgovara izlaznim informacijama pojavljuje se na traci;

2) nema zaustavljanja.

U prvom slučaju kažu da je ova mašina primjenjiva na početne informacije, u drugom - ne. Čitav skup ulaznih konfiguracija pod kojima mašina daje rezultat formira klasu problema koje treba riješiti. Očigledno, nema smisla koristiti Turingovu mašinu za problem koji nije uključen u klasu rješivih.

Postoji Tjuringova hipoteza: ako je postupak dobro definisan i mehaničke prirode, onda se može razumno pretpostaviti da će postojati Turingova mašina sposobna da je izvede. Ne može se dokazati jer povezuje labavu definiciju koncepta algoritma sa strogom definicijom Turingove mašine. Ova pretpostavka se može opovrgnuti ako se može dati primjer algoritma koji se ne može implementirati korištenjem kruga Turingove funkcije. Međutim, svi do sada poznati algoritmi mogu se specificirati korištenjem Turingovih funkcionalnih kola.

simulator za učenje univerzalnog izvođača

Šta je to?

Simulator Turingove mašine je model obuke univerzalnog izvršioca (apstraktne računarske mašine), koji je 1936. predložio A. Turing da bi razjasnio koncept algoritma. Prema Turingovoj tezi, svaki algoritam se može napisati kao program za Turingovu mašinu. Dokazano je da je Tjuringova mašina po svojim mogućnostima ekvivalentna Post mašini i normalnim Markovljevim algoritmima.

Turingova mašina se sastoji od nosača (glava za čitanje i pisanje) i beskrajne trake podijeljene na ćelije. Svaka ćelija trake može sadržavati znak iz neke abecede A=(a 0 ,a 1 ,…,a N ) . Bilo koja abeceda sadrži razmak, koji je označen kao 0 ili Λ. Prilikom unosa naredbi, razmak se zamjenjuje donjom crtom "_".

Turingova mašina je automat kojim se upravlja pomoću stola. Redovi u tabeli odgovaraju znakovima odabranog alfabeta A, a stupci stanjima mašine Q=(q 0 ,q 1 ,…,q M ) . Na početku svog rada, Turingova mašina je u stanju q 1 . Stanje q 0 je konačno stanje: jednom u njemu, mašina završava svoj rad.

U svakoj ćeliji tabele, koja odgovara nekom simbolu a i i nekom stanju q j, nalazi se naredba koja se sastoji od tri dela:

1. znak iz abecede A;
2. smjer kretanja: > (desno),
3. novo stanje mašine

Vijesti

1. Falina I.N. Tema „Tjuringova mašina“ u školskom kursu informatike (inf.1september.ru).
2. Mayer R.V. Post i Turing mašine (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Turingova mašina i Markovljevi algoritmi. Rješavanje problema, M.: MSU, 2006.
4. Bekman I.N. Računarska nauka. Predavanje 7. Algoritmi (profbeckman.narod.ru)
5. Solovjev A. Diskretna matematika bez formula (lib.rus.ec)
6. Ershov S.S. Elementi teorije algoritama, Čeljabinsk, Izdavački centar SUSU, 2009.
7. Varpakhovsky F.L. Elementi teorije algoritama, M: Prosveshchenie, 1970.
8. Vereshchagin N.K., Shen A. Izračunljive funkcije, M: MTsNMO, 1999.

Šta učiniti povodom toga?

Na vrhu programa nalazi se polje za uređivanje u koje možete unijeti stanje problema u slobodnom obliku.

Traka se pomiče lijevo i desno pomoću dugmadi smještenih lijevo i desno od nje. Dvoklikom na ćeliju trake (ili desnim klikom) možete promijeniti njen sadržaj.

Korišćenje menija Ribbon možete pohraniti stanje trake u interni međuspremnik i vratiti traku iz međuspremnika.

U polju Abeceda Navedeni su znakovi odabrane abecede. Unesenim znakovima se automatski dodaje razmak.

Program se upisuje u tabelu na dnu prozora. Prva kolona sadrži abecedne znakove i popunjava se automatski. Prvi red navodi sva moguća stanja. Možete dodavati i uklanjati kolone tabele (stanja) pomoću dugmadi koja se nalaze iznad tabele.

Kada unosite naredbu u ćeliju tabele, prvo morate unijeti novi znak, zatim smjer prijelaza i broj stanja. Ako je znak izostavljen, on se po defaultu ostavlja nepromijenjen. Ako je broj stanja izostavljen, po defaultu se stanje stroja ne mijenja.

Pravo u polju Komentar Možete unijeti komentare slobodnog oblika na rješenje. Najčešće objašnjava šta svako stanje Turingove mašine znači.

Program se može izvršavati kontinuirano (F9) ili u koracima (F8). Naredba koja će se sada izvršiti je označena zelenom pozadinom. Brzina izvršenja je podesiva pomoću menija Brzina.

Problemi s Turingovom mašinom mogu se sačuvati u fajlovima. Stanje zadatka, abeceda, program, komentari i početno stanje trake se čuvaju. Kada se zadatak učita iz datoteke i spremi u datoteku, stanje trake se automatski čuva u međuspremniku.

Ako primijetite grešku ili imate prijedloge, komentare, pritužbe, zahtjeve ili izjave, pišite.

Tehnički uslovi

Program radi pod operativnim sistemima linije Windows na bilo kom modernom računaru.

Licenca

Program je besplatan za nekomercijalnu upotrebu. Izvorni kod programa nije distribuiran.

Program dolazi" kao što je“, odnosno autor ne snosi nikakvu odgovornost za sve moguće posljedice njegovog korištenja, uključujući moralne i materijalne gubitke, kvar opreme, fizičke i psihičke ozljede.

Prilikom postavljanja programa na druge web stranice potrebna je veza do originalnog izvora.

1. 1) objavljivanje materijala u bilo kom obliku, uključujući postavljanje materijala na druge veb stranice;
2. 2) distribucija nekompletnih ili izmenjenih materijala;
3. 3) uključivanje materijala u zbirke na bilo kom mediju;
4. 4) sticanje komercijalne koristi od prodaje ili drugog korišćenja materijala.

Preuzimanje materijala znači da prihvatate uslove ovog ugovora o licenci.

Skinuti

Nakon raspakivanja arhive, program je u radnom stanju i ne zahtijeva dodatne instalacije.

1. Opis Turingove mašine. 3

1.1 Svojstva Tjuringove mašine kao algoritma. 5

2. Složenost algoritama. 7

2.1 Složenost problema... 9

3. Turingova mašina i algoritamski nerješivi problemi.. 12

Zaključak. 16

Reference.. 18

Uvod

Turingova mašina je vrlo jednostavan računarski uređaj. Sastoji se od trake beskonačne dužine, podijeljene na ćelije, i glave koja se kreće duž trake i koja je sposobna čitati i pisati znakove. Također, Turingova mašina ima takvu karakteristiku kao što je stanje, koje se može izraziti kao cijeli broj od nule do neke maksimalne vrijednosti. Ovisno o stanju, Turingova mašina može izvršiti jednu od tri radnje: upisati simbol u ćeliju, pomjeriti jednu ćeliju udesno ili ulijevo i postaviti unutrašnje stanje.

Dizajn Turingove mašine je izuzetno jednostavan, ali može pokrenuti gotovo svaki program. Da biste izvršili sve ove radnje, obezbeđena je posebna tabela pravila koja specificira šta treba učiniti za različite kombinacije trenutnih stanja i simbola pročitanih sa trake.

Godine 1947. Alan Turing je proširio definiciju kako bi opisao "univerzalnu Turingovu mašinu". Kasnije, za rješavanje određenih klasa problema, uvedena je njegova varijacija, koja je omogućila izvođenje ne jednog zadatka, već nekoliko.

1. Opis Turingove mašine

Pozadina nastanka ovog rada povezana je sa formulisanjem nerešenih matematičkih problema od strane Davida Hilberta na Međunarodnom matematičkom kongresu u Parizu 1900. godine. Jedan od njih bio je zadatak da se dokaže konzistentnost aksiomskog sistema obične aritmetike, što je Hilbert kasnije razjasnio kao „problem odlučivosti” – pronalaženje opšte metode za određivanje zadovoljivosti datog iskaza u jeziku formalne logike.

Turingov rad je precizno dao odgovor na ovaj problem - drugi Hilbertov problem se pokazao nerješivim. Ali značaj Tjuringovog rada je prevazišao problem zbog kojeg je napisan.

Evo opisa ovog rada, koji pripada Johnu Hopcroftu: "Radeći na Hilbertovom problemu, Turing je morao dati jasnu definiciju samog koncepta metode. Polazeći od intuitivne ideje metode kao vrste algoritma, tj. postupak koji se može izvesti mehanički, bez kreativne intervencije", pokazao je kako se ova ideja može utjeloviti u obliku detaljnog modela računskog procesa. Rezultirajući model proračuna, u kojem je svaki algoritam razbijen u niz jednostavnih, elementarnih koraka, bila je logička konstrukcija koja je kasnije nazvana Turingova mašina."

Turingova mašina je ekstenzija modela konačnog stroja, ekstenzija koja uključuje potencijalno beskonačnu memoriju sa mogućnošću pomicanja (pomjeranja) od trenutno gledane ćelije do njenog lijevog ili desnog susjeda.

Formalno, Turingova mašina se može opisati na sledeći način. Neka se da sljedeće:

konačan skup stanja – Q, u kojem može biti Tjuringova mašina;

konačan skup simbola trake – G;

funkcija δ (prijelazna funkcija ili program), koja je specificirana preslikavanjem para iz kartezijanskog proizvoda Q x G (mašina je u stanju qi i gleda simbol gi) u trojku kartezijanskog proizvoda Q x G x (L ,R) (mašina prelazi u stanje qi, zamjenjuje gi simbol simbolom gj i pomiče lijevo ili desno za jedan simbol trake) – Q x G-->Q x G x (L,R)

jedan znak iz G-->e (prazno);

podskup Σ ê G - -> je definisan kao podskup ulaznih simbola trake, a e ê (G - Σ);

jedno od stanja – q0 ê Q je početno stanje mašine.

Problem koji treba riješiti je specificiran snimanjem konačnog broja simbola iz skupa Σ ê G – Si ê Σ na traku:

eS1S2S3S4... ... ...Sne

nakon čega se mašina prebacuje u početno stanje i glava se ugrađuje na krajnje lijevo neprazan simbol (q0,w) –, nakon čega, u skladu sa navedenom funkcijom prijelaza (qi,Si) - ->(qj, Sk, L ili R), mašina počinje da zamenjuje prikazane simbole, pomera glavu udesno ili ulevo i prelazi u druga stanja propisana prelaznim funkcijama.

Stroj se zaustavlja ako funkcija prijelaza za par (qi,Si) nije definirana.

Alan Turing je predložio da bilo koji algoritam u intuitivnom smislu riječi može biti predstavljen ekvivalentnom Turingovom mašinom. Ova pretpostavka je poznata kao Church-Turingova teza. Svaki računar može simulirati Turingovu mašinu (operacije ponovnog pisanja ćelija, upoređivanje i premještanje u drugu susjednu ćeliju, uzimajući u obzir promjene u stanju mašine). Shodno tome, on može modelirati algoritme u bilo kojem formalizmu, a iz ove teze proizilazi da su svi računari (bez obzira na snagu, arhitekturu itd.) ekvivalentni u smislu fundamentalne sposobnosti rješavanja algoritamskih problema.

1.1 Svojstva Tjuringove mašine kao algoritma

Koristeći Turingovu mašinu kao primjer, mogu se jasno vidjeti svojstva algoritama. Zamolite učenike da pokažu da Tjuringova mašina ima sva svojstva algoritma.

Diskretnost. Tjuringova mašina može da pređe na (k + 1)-ti korak tek nakon što završi svaki korak, jer svaki korak određuje šta će biti (k + 1)-ti korak.

Jasnoća. Na svakom koraku u ćeliju se upisuje simbol iz abecede, automat čini jedan pokret (L, P, N), a Turingova mašina prelazi u jedno od opisanih stanja.

Determinizam. Svaka ćelija tabele Turingove mašine sadrži samo jednu opciju za akciju. U svakom koraku rezultat je jednoznačno određen, dakle, jednoznačno je određen slijed koraka za rješavanje problema, tj. Ako je Turing mašini data ista ulazna reč, onda će izlazna reč biti ista svaki put.

Produktivnost. Sadržajno, rezultati svakog koraka i čitav niz koraka su jednoznačno određeni, stoga će ispravno napisana Turingova mašina preći u stanje q0 u konačnom broju koraka, tj. u konačnom broju koraka će se dobiti odgovor na problem.

Masovni karakter. Svaka Turing mašina je definisana nad svim dozvoljenim rečima iz abecede, to je svojstvo masovnog karaktera. Svaka Turingova mašina je dizajnirana da reši jednu klasu problema, tj. Za svaki problem je napisana sopstvena (nova) Turing mašina.

2. Složenost algoritama

Složenost algoritma određena je računskom snagom koja je potrebna za njegovo izvršavanje. Računska složenost algoritma se često mjeri pomoću dva parametra: T (vremenska složenost) i S (složenost prostora, ili memorijski zahtjevi). I T i S se obično predstavljaju kao funkcije od n, gdje je n veličina ulaznih podataka. (Postoje i drugi načini mjerenja složenosti: broj nasumičnih bitova, širina komunikacijskog kanala, količina podataka, itd.)

Obično se računska složenost algoritma izražava korištenjem “Big O” notacije, odnosno opisuje se redoslijedom veličine računske složenosti. Ovo je jednostavno izraz u proširenju funkcije složenosti koji najbrže raste kako n raste, svi članovi nižeg reda se zanemaruju. Na primjer, ako je vremenska složenost datog algoritma 4n2+7n+12, tada je složenost računanja reda n2, zapisana kao O(n2).

Vremenska složenost mjerena na ovaj način je nezavisna od implementacije. Ne morate znati tačna vremena izvršavanja raznih instrukcija, niti broj bitova koji se koriste za predstavljanje različitih varijabli, pa čak ni brzinu procesora. Jedan računar može biti 50 posto brži od drugog, a treći može imati duplo širu magistralu podataka, ali složenost algoritma, mjerena redom veličine, neće se promijeniti. To nije varanje; kada se radi sa složenim algoritmima kao što su oni opisani u ovoj knjizi, sve ostalo se može zanemariti (do konstantnog faktora) u poređenju sa složenošću reda veličine.

Ova notacija vam omogućava da vidite kako veličina ulaznih podataka utječe na zahtjeve vremena i memorije. Na primjer, ako je T = O(n), tada će udvostručenje ulaznih podataka udvostručiti vrijeme izvršenja algoritma. Ako je T=O(2n), tada će dodavanje jednog bita ulaznim podacima udvostručiti vrijeme izvršenja algoritma.

Obično se algoritmi klasifikuju prema njihovoj vremenskoj ili prostornoj složenosti. Algoritam se naziva konstantnim ako njegova složenost ne zavisi od n: 0(1). Algoritam je linearan ako je njegova vremenska složenost O(n). Algoritmi mogu biti kvadratni, kubni, itd. Svi ovi algoritmi su polinomni, njihova složenost je O(m), gdje je m konstanta. Algoritmi sa polinomskom vremenskom složenošću nazivaju se polinomijski vremenski algoritmi

Algoritmi čija je složenost jednaka O(tf(n)), gdje je t konstanta veća od 1, a f(n) neka polinomna funkcija od n, nazivaju se eksponencijalni. Podskup eksponencijalnih algoritama čija je složenost O(cf(n)), gdje je c konstanta, a f(n) raste brže od konstante, ali sporije od linearne funkcije, naziva se superpolinom.

U idealnom slučaju, kriptograf bi želio da tvrdi da najbolji algoritam za razbijanje dizajniranog algoritma šifriranja ima eksponencijalnu vremensku složenost. U praksi, najjače tvrdnje koje se mogu dati s obzirom na trenutno stanje teorije složenosti računara su u obliku „svi poznati algoritmi napada za dati kriptosistem imaju superpolinomsku vremensku složenost“. Odnosno, nama poznati algoritmi napada imaju superpolinomsku vremensku složenost, ali još nije moguće dokazati da se algoritam napada sa polinomskom vremenskom složenošću ne može otkriti. Razvoj teorije računske složenosti može jednog dana omogućiti stvaranje algoritama za koje se postojanje algoritama sa polinomskim vremenom otvaranja može isključiti s matematičkom tačnošću.

Turingova mašina jedno je od najintrigantnijih i najuzbudljivijih intelektualnih otkrića 20. stoljeća. To je jednostavan i koristan apstraktni model računarstva (kompjuterski i digitalni) koji je dovoljno općenit da implementira bilo koji računski zadatak. Zahvaljujući jednostavnom opisu i matematičkoj analizi, čini temelj teorijske informatike. Ovo istraživanje dovelo je do boljeg razumijevanja digitalnog računarstva i računanja, uključujući razumijevanje da postoje neki računarski problemi koji se ne mogu riješiti na mainframe 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 put opisao mašinu 1936. godine u radu "O izračunljivim brojevima sa primenom na problem reš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 unos 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. Automatski - kontrolirani 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 se naziva pasivno. Vjeruje se da uređaj završava svoj rad kada ga udari. Stanje q1 naziva se početno - mašina počinje svoje proračune dok je u njemu na početku. Ulazna riječ se nalazi na traci, po jedno slovo u redu na svakoj poziciji. Sa obe strane ima 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 beskrajnu traku, dok kod digitalnih uređaja takav uređaj ima traku određene dužine. Svaku klasu zadataka rješava samo jedna izgrađena Turingova mašina. Problemi drugačijeg tipa zahtijevaju pisanje novog algoritma. Upravljački uređaj, u jednom stanju, može se kretati u bilo kojem smjeru duž pojasa. Upisuje i čita iz ćelija znakove konačne abecede. Tokom selidbe, prazan element se dodeljuje i popunjava pozicije koje ne sadrže ulazne podatke. Algoritam Turingove mašine određuje pravila prijelaza za kontrolni uređaj. Oni postavljaju sljedeće parametre glavi za čitanje i upisivanje: pisanje novog karaktera u ćeliju, prelazak u novo stanje, pomicanje lijevo ili desno duž trake.

Osobine mehanizma

Tjuringova mašina, kao i drugi računarski sistemi, ima inherentne karakteristike, i 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 izvršeni korak dodjeljuje ono što će biti n+1. Jasnoća. Uređaj obavlja samo jednu radnju za jednu ćeliju. Unosi znak iz abecede i čini jedan pokret: lijevo ili desno. Determinizam. Svaka pozicija u mehanizmu odgovara jednoj opciji za izvršavanje date šeme, a u svakoj fazi radnje i redoslijed njihovog izvršenja su nedvosmisleni. Produktivnost. Tačan rezultat za svaku fazu 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 važećih riječi uključenih u abecedu. Funkcije Turingove mašine Rešavanje algoritama često zahteva implementaciju funkcije. U zavisnosti od mogućnosti pisanja lanca za proračun, funkcija se naziva algoritamski rješ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 unutar binarnog kodnog alfabeta 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 imati formalni jezik u završnoj abecedi i riješiti problem prepoznavanja ispravnih opisa.-

Program uređaja

Programi za Tjuringov mehanizam su formatirani u tabele u kojima prvi red i kolona sadrže simbole eksterne abecede i vrednosti mogućih unutrašnjih stanja automata - interne abecede. Tabelarni podaci su komande koje Turingova mašina prihvata. Rješavanje problema se odvija na ovaj način: slovo koje čita glava u ćeliji nad kojom se trenutno nalazi, i unutrašnje stanje glave mašine određuju koju naredbu treba izvršiti. Ova konkretna komanda se nalazi na preseku spoljašnjih i unutrašnjih simbola abecede koji se nalaze u tabeli.

Komponente za proračune

Da biste napravili Turingovu mašinu za rješavanje jednog specifičnog problema, trebate definirati sljedeće parametre za nju. Eksterna abeceda. Ovo je određeni 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 i simbola snimljenih na traci naziva se riječ. Automatski uređaj 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 koji nastaju, prelazi iz jedne pozicije u drugu. Skup takvih stanja je interna abeceda. Ima slovnu oznaku 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 završava program i dovodi uređaj u zaustavljenu poziciju.

Prijelazni stol.

Ova komponenta je algoritam za ponašanje nosača uređaja u zavisnosti od trenutnog stanja mašine i vrednosti pročitanog simbola.-

Algoritam za mašinu

Tokom rada, nošenje Turing uređaja kontroliše program koji, tokom svakog koraka, izvodi niz sljedećih radnji: Upisivanje simbola eksterne abecede na poziciju, uključujući i praznu, zamjenu elementa koji je bio u uključujući i prazan. Pomjerite za jedan korak ulijevo ili udesno. Promjena vašeg unutrašnjeg stanja. 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, "→" do desno, "tačka" - nema kretanja) i qk - novo stanje uređaja. Na primjer, komanda 1 “←” q2 ima značenje “zamijenite znak sa 1, pomaknite glavu nosača ulijevo za jednu stepenicu i napraviti prijelaz u stanje q2”.