Tiuringo mašina yra šių objektų rinkinys

• 1) išorinė abėcėlė A=(a 0 , a 1 , …, a n );
• 2) vidinė abėcėlė Q=(q 1 , q 2 ,…, q m ) - būsenų rinkinys;
• 3) valdymo simbolių rinkinys (P, L, S)
• 4) begalinė juosta abiem kryptimis, suskirstyta į langelius, kurių kiekvienoje gali būti tik vienas simbolis iš abėcėlės A bet kuriuo atskiru laiku;
• 5) valdymo įtaisas, galintis būti vienoje iš daugelio būsenų

Tuščio langelio simbolis yra išorinės abėcėlės raidė 0 .

Tarp būsenų išskiriama pradinė q 1, kurioje mašina pradeda veikti, ir galutinė (arba sustojimo būsena) q 0, kai mašina sustoja.

Valdymo įtaisas juostoje gali judėti kairėn ir dešinėn, skaityti ir įrašyti į juostos langelius A abėcėlės simbolius. Valdymo įrenginys veikia pagal komandas, kurios turi tokią formą

q i a j > a p X q k

Įrašymas reiškia: jei valdymo įtaisas yra q i būsenoje, o žiūrimame langelyje parašyta raidė a j, tada (1) langelyje vietoj j įrašoma p, (2) aparatas pradeda peržiūrėti kitas dešinysis langelis nuo ką tik peržiūrėto, jei X = P, arba peržiūrėti kitą kairįjį langelį, jei X = L, arba toliau žiūrėti tą patį juostos langelį, jei X = C, (3) įeina valdymo įtaisas valstybė q k.

Kadangi mašinos veikimas pagal sąlygas yra visiškai nulemtas jos būsenos q tam tikru momentu ir tuo momentu žiūrimo langelio turinio a, tai kiekvienai galimai konfigūracijai q i a j galioja tiksliai viena taisyklė. Nėra taisyklių tik galutinei būsenai, kai mašina sustoja. Todėl Tiuringo mašinos programoje su išorine abėcėle A=(a0, a1, …, an) ir vidine abėcėle Q=(q1, q2,…, qm) yra ne daugiau kaip m (n+ 1) instrukcijų.

Žodis abėcėlės A arba abėcėlės Q arba abėcėlės A Q yra bet kokia atitinkamos abėcėlės raidžių seka. Pagal k-ąją konfigūraciją turime omenyje mašinos juostos vaizdą su informacija, kuri joje susiformavo iki k-ojo žingsnio pradžios (arba žodį abėcėlėje A, įrašytą juostoje iki k pradžios -tas žingsnis), nurodant, kuri kamera šiuo žingsniu žiūrima Ir kokios būklės automobilis? Prasmingos tik baigtinės konfigūracijos, t.y. tie, kuriuose visi juostos langeliai, išskyrus galinį skaičių, yra tušti. Konfigūracija laikoma galutine, jei mašinos būsena yra galutinė.

Jei pasirenkama bet kokia ne galutinė Tiuringo mašinos konfigūracija kaip pradinė, tada mašinos užduotis yra nuosekliai (žingsnis po žingsnio) transformuoti pradinę konfigūraciją pagal mašinos programą, kol bus pasiekta galutinė konfigūracija. Po to Tiuringo mašinos darbas laikomas baigtu, o darbo rezultatas – pasiekta galutinė konfigūracija.

Sakysime, kad netuščią žodį b abėcėlėje A (а 0 ) = (a 1 , ..., a n ) aparatas suvokia standartinėje padėtyje, jei jis parašytas nuosekliuose juostos langeliuose, visi kiti langeliai yra tušti, o mašina peržiūri kairėje arba dešinėje pusėje esantį langelį iš tų, kuriuose įrašytas žodis b. Standartinė padėtis vadinama pradine (galutine), jei mašina, suvokianti žodį standartinėje padėtyje, yra pradinėje būsenoje q 1 (atitinkamai, sustabdymo būsenoje q 0).

Jei apdorojant žodį b Tiuringo mašina patenka į galutinę būseną, tada sakoma, kad ji taikoma b, kitu atveju netaikoma b (mašina veikia neribotą laiką)

Apsvarstykite pavyzdį:

Turingo mašina su išorine abėcėle A \u003d (0, 1) (čia 0 yra tuščio langelio simbolis), vidinių būsenų Q \u003d (q 0, q 1, q 2 ) abėcėlė ir tokia funkcinė diagrama (programa):

q 1 0 > 1 L q 2;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 C q 1;

Šią programą galima parašyti naudojant lentelę

Pirmuoju žingsniu veikia komanda: q 1 0 > 1 Л q 2 (valdymo įrenginys yra q1 būsenoje, o stebimame langelyje rašoma raidė 0, langelyje vietoj 0 rašoma 1, galvutė pasislenka į kairę, valdymo įtaisas persijungia į q2 būseną), dėl to mašinoje sukuriama tokia konfigūracija:

Galiausiai, įvykdžius komandą q 2 0 > 0 P q 0, sukuriama konfigūracija

Ši konfigūracija yra galutinė, nes mašina yra sustabdyta q 0 .

Taigi, originalus žodis 110 mašina paverčiamas žodžiu 101.

Gautą konfigūracijų seką galima parašyti trumpiau (stebimos ląstelės turinys rašomas dešinėje nuo būsenos, kurioje šiuo metu yra įrenginys):

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

Tiuringo mašina yra ne kas kita, kaip kažkokia taisyklė (algoritmas) abėcėlės A Q žodžių konvertavimui, t.y. konfigūracijos. Taigi, norint apibrėžti Tiuringo mašiną, reikia nurodyti jos išorinę ir vidinę abėcėlę, programą ir nurodyti, kuris iš simbolių žymi tuščią langelį ir galutinę būseną.

Turingo mašina yra vienas įdomiausių ir įdomiausių XX amžiaus intelektualinių atradimų. Tai paprastas ir naudingas abstraktus skaičiavimo modelis (kompiuterinis ir skaitmeninis), kuris yra pakankamai bendras bet kokiai kompiuterio užduočiai įgyvendinti. Ačiū paprastas aprašymas ir atliekant matematinę analizę, ji sudaro teorinės informatikos pagrindą. Šis tyrimas leido giliau suprasti skaitmeninius kompiuterius ir skaičiavimus, įskaitant supratimą, kad yra tam tikrų skaičiavimo problemų, kurių negalima išspręsti bendriems kompiuteriams.

Kas tai yra ir kas jį sukūrė

Alanas Turingas siekė apibūdinti patį primityviausią mechaninio įrenginio modelį, kuris turėtų tas pačias pagrindines galimybes kaip ir kompiuteris. Pirmą kartą Turingas aprašė mašiną 1936 m. „On Computable Numbers with Application to the Decidability Problem“, kuris pasirodė Londono matematikos draugijos darbuose.

Tiuringo mašina – tai skaičiavimo įrenginys, sudarytas iš skaitymo/rašymo galvutės (arba „skenerio“) su popierine juostele. Juosta padalinta į kvadratus, kurių kiekvienas turi vieną simbolį – „0“ arba „1“. Mechanizmo paskirtis yra ta, kad jis veiktų ir kaip įėjimo ir išėjimo priemonė, ir kaip darbinė atmintis tarpinių skaičiavimo etapų rezultatams saugoti.

Iš ko pagamintas prietaisas?

Kiekviena tokia mašina susideda iš dviejų komponentų:

1. Neribota juosta. Jis yra begalinis abiem kryptimis ir yra padalintas į ląsteles.
2. Aparatas yra valdoma programa, skaitytuvo galvutė duomenims nuskaityti ir rašyti. Bet kuriuo momentu jis gali būti vienoje iš daugelio būsenų.

Kiekviena mašina susieja dvi baigtines duomenų eilutes: įvesties simbolių abėcėlę A = (a0, a1, ..., am) ir būsenų abėcėlę Q = (q0, q1, ..., qp). Būsena q0 vadinama pasyvia. Manoma, kad atsitrenkęs prietaisas baigia savo darbą. Būsena q1 vadinama pradine būsena – mašina pradeda savo skaičiavimus, būdama joje pradžioje. Įvesties žodis įrašomas į juostą po vieną raidę iš eilės kiekvienoje pozicijoje. Abiejose jo pusėse yra tik tuščios ląstelės.

Kaip veikia mechanizmas

Turingo mašina turi esminį skirtumą nuo skaičiavimo įrenginių – jos saugojimo įrenginys turi begalinę juostą, o skaitmeniniams įrenginiams toks įrenginys turi tam tikro ilgio juostelę. Kiekviena užduočių klasė sprendžiama tik viena sukonstruota Tiuringo mašina. Kitokio tipo užduotys apima naujo algoritmo rašymą.

Valdymo įtaisas, būdamas vienoje būsenoje, gali judėti bet kuria juosta kryptimi. Jis rašo į ląsteles ir iš jų nuskaito paskutinės abėcėlės simbolius. Perkėlimo metu išskiriamas tuščias elementas, kuris užpildo pozicijas, kuriose nėra įvesties duomenų. Turingo mašinos algoritmas apibrėžia valdymo įrenginio perėjimo taisykles. Jie nustato tokius rašymo-skaitymo galvutės parametrus: naujo simbolio įrašymas į langelį, perėjimas į naują būseną, judėjimas į kairę arba dešinę juostoje.

Judėjimo savybės

Tiuringo mašina, kaip ir kitos skaičiavimo sistemos, turi būdingų savybių ir yra panašios į algoritmų savybes:

1. diskretiškumas. Skaitmeninė mašina pereina prie kito žingsnio n+1 tik atlikus ankstesnį. Kiekvienas atliktas žingsnis nurodo, kas bus n+1.
2. Aiškumas. Įrenginys atlieka tik vieną veiksmą tai pačiai ląstelei. Jis įveda simbolį iš abėcėlės ir atlieka vieną judesį: kairėn arba dešinėn.
3. Ryžtingumas. Kiekviena mechanizmo padėtis atitinka vienintelį pateiktos schemos variantą, o kiekviename etape veiksmai ir jų vykdymo seka yra vienareikšmiai.
4. Efektyvumas. Tikslų kiekvieno žingsnio rezultatą nustato Tiuringo mašina. Programa vykdo algoritmą ir per baigtinį žingsnių skaičių pereina į būseną q0.
5. Masinis personažas. Kiekvienas įrenginys apibrėžiamas virš leidžiamų žodžių, įtrauktų į abėcėlę.

Turingo mašinos funkcijos

Sprendžiant algoritmus dažnai reikalingas funkcijos įgyvendinimas. Priklausomai nuo galimybės parašyti skaičiavimo grandinę, funkcija vadinama algoritmiškai sprendžiama arba neapsprendžiama. Kaip aibė natūralių arba racionalių skaičių, žodžių baigtinėje abėcėlėje N mašinai laikoma aibės B seka - žodžiai dvejetainio kodo abėcėlės rėmuose B=(0,1). Be to, skaičiavimo rezultate atsižvelgiama į „neapibrėžtą“ reikšmę, kuri atsiranda, kai algoritmas „užstringa“. Funkcijai įgyvendinti svarbu, kad baigtinėje abėcėlėje būtų formali kalba ir teisingų aprašymų atpažinimo problema būtų išspręsta.

Įrenginio programinė įranga

Turingo mechanizmo programos yra išdėstytos lentelėse, kurių pirmoje eilutėje ir stulpelyje yra išorinės abėcėlės simboliai ir galimų vidinių automato būsenų reikšmės - vidinė abėcėlė. Lenteliniai duomenys yra komandos, kurias priima Tiuringo mašina. Problemos sprendimas vyksta taip: raidė, kurią skaito galva ląstelėje, kuri šiuo metu yra aukščiau, ir vidinė automato galvutės būsena nustato, kuri iš komandų turi būti vykdoma. Tiksliau, tokia komanda yra išorinės ir vidinės abėcėlės simbolių sankirtoje, esančioje lentelėje.

Komponentai skaičiavimams

Norint sukurti Tiuringo mašiną, skirtą vienai konkrečiai problemai išspręsti, būtina apibrėžti šiuos jos parametrus.

išorinė abėcėlė. Tai yra tam tikras baigtinis simbolių rinkinys, žymimas ženklu A, kurio sudedamosios dalys vadinamos raidėmis. Vienas iš jų – a0 – turi būti tuščias. Pavyzdžiui, Turingo įrenginio, dirbančio su dvejetainiais skaičiais, abėcėlė atrodo taip: A = (0, 1, a0).

Juostoje įrašyta ištisinė raidžių-simbolių grandinė vadinama žodžiu.

Automatas – tai įrenginys, veikiantis be žmogaus įsikišimo. Tiuringo mašinoje ji turi keletą skirtingų būsenų problemoms spręsti ir tam tikromis sąlygomis pereina iš vienos padėties į kitą. Tokių vežimo būsenų rinkinys yra vidinė abėcėlė. Jis turi raidės žymėjimas formos Q=(q1, q2...). Viena iš šių pozicijų – q1 – turi būti pradinė, tai yra ta, kuri paleidžia programą. Kitas būtinas elementas yra būsena q0, kuri yra galutinė būsena, ty ta, kuri baigia programą ir perkelia įrenginį į sustabdymo padėtį.

Šokinėjimo stalas. Šis komponentas yra įrenginio vežimėlio veikimo algoritmas, priklausantis nuo esamos mašinos būsenos ir skaitomo simbolio reikšmės.

Automato algoritmas

Turingo įrenginio nešimas veikimo metu yra valdomas programa, kuri kiekviename žingsnyje atlieka šių veiksmų seką:

1. Išorinės abėcėlės simbolio įrašymas į vietą, įskaitant tuščią, pakeičiant joje esantį elementą, įskaitant tuščią.
2. Perkelkite vieną langelį į kairę arba į dešinę.
3. Pakeiskite savo vidinę būseną.

Taigi, rašant programas kiekvienai simbolių porai ar pozicijoms, būtina tiksliai apibūdinti tris parametrus: a i - elementas iš pasirinktos abėcėlės A, vežimo poslinkio kryptis ("←" į kairę, "→" į dešinėn, "taškas" - nejuda) ir q k - nauja įrenginio būsena. Pavyzdžiui, 1 komanda "←" q 2 turi reikšmę "pakeisti simbolį 1, perkelkite vežimėlio galvutę į kairę vienu žingsniu, ir pereiti į būseną q 2 “.

Tiuringo mašina: pavyzdžiai

1 pavyzdys Užduotis yra sukurti algoritmą, kuris prideda vieną prie paskutinio nurodyto skaičiaus, esančio juostoje, skaitmens. Įvesties duomenys – žodis – viso dešimtainio skaičiaus skaitmenys, įrašyti iš eilės juostos langeliuose. Pradiniu momentu įrenginys yra priešais dešinįjį ženklą - skaičiaus skaitmenį.

Sprendimas. Jei paskutinis skaitmuo yra 9, jis turi būti pakeistas 0 ir pridėti vieną prie ankstesnio simbolio. Programa šiuo atveju tam tikram Turingo įrenginiui gali būti parašyta taip:

Čia q 1 yra skaitmens keitimo būsena, q 0 yra stabdis. Jei q 1 automatas fiksuoja elementą iš 0..8 eilutės, tai atitinkamai jį pakeičia vienu iš 1..9, o tada persijungia į būseną q 0, tai yra, įrenginys sustoja. Jei vežimėlis fiksuoja skaičių 9, tada jis pakeičia jį 0, tada juda į kairę, sustodamas q 1 būsenoje. Šis judėjimas tęsiasi tol, kol prietaisas užfiksuoja skaitmenį, mažesnį nei 9. Jei visi simboliai lygūs 9, jie pakeičiami nuliais, vietoje aukščiausio elemento bus rašomas 0, vežimėlis pajudės į kairę ir įrašys 1 į tuščia ląstelė. Kitas žingsnis bus perėjimas į būseną q 0 – stop.

2 pavyzdys Pateikta eilė simbolių, žyminčių atidarymo ir uždarymo skliaustus. Būtina sukurti Turingo įrenginį, kuris pašalintų porą abipusių skliaustų, ty elementus, išdėstytus iš eilės - „()“. Pavyzdžiui, pradiniai duomenys: ") (() (()", atsakymas turėtų būti: ") . . . ((". Sprendimas: mechanizmas, būdamas q 1 , analizuoja kairiausią eilutės elementą).

Būsena q 1: jei aptinkamas simbolis „(“, perjunkite į dešinę ir eikite į q 2 padėtį; jei apibrėžtas „a 0“, sustokite.

q 2 būsena: skliaustelis „(“ analizuojamas, ar nėra susiejimo, jei sutampa, „)“ turėtų būti gautas. Jei elementas yra pora, grįžkite į kairę ir eikite į q 3 .

Būsena q 3: pirmiausia ištrinkite simbolį „(“, o tada „)“ ir pereikite prie q 1 .

Iki šiol mums buvo patogu remtis programavimo patirtimi, kai kalbame apie algoritmus, programas, interpretatorius, žingsniavimą ir pan. Tai leido nekreipti dėmesio į tam tikrų algoritmų kūrimo detales, apsimetant pretekstu, kad skaitytojas gali nesunkiai juos atkurti (ar bent patikėti, juk ne kiekvienas skaitytojas savo gyvenime rašė Paskalio interpretatorių Pascal).

Tačiau kai kuriais atvejais to nepakanka. Tarkime, norime įrodyti kokios nors problemos, kurios apibrėžimas nieko nepasako apie programas, algoritminį neišsprendžiamumą (pavyzdžiui, šioje dalyje įrodysime žodžio lygybės problemos neišsprendžiamumą generatorių pateiktose pusgrupėse ir santykiai). Paprastai tai daroma taip. Mes parodome, kad sustabdymo problema sumažėja iki šios problemos. Norėdami tai padaryti, mes modeliuojame savavališko algoritmo veikimą pagal nagrinėjamą problemą (ką tai reiškia, parodysime toliau pateiktame pavyzdyje). Kartu mums svarbu, kad algoritmo apibrėžimas būtų kuo paprastesnis.

Taigi mūsų planas yra toks. Aprašysime gana lengvai apibrėžtą mašinų klasę (ją galima rinktis įvairiai, naudosime vadinamąsias Tiuringo mašinas), tada deklaruosime, kad tokioje mašinoje galima įvertinti bet kokią skaičiuojamą funkciją, o tada parodysime kad Tiuringo mašinos sustabdymo klausimą galima redukuoti iki žodžių lygybės pusgrupėje klausimo.

Kita priežastis, kodėl paprasti skaičiavimo modeliai yra svarbūs (yra daug skirtingi tipai Tiuringo mašinos, adresų mašinos ir kt.) yra susijęs su skaičiavimo sudėtingumo teorija, kai mus domina pristatymo laikas programas. Tačiau šis klausimas peržengia klasikinę algoritmų teoriją.

Tiuringo mašinos: apibrėžimas

Turingo mašina turi begalinį abiem kryptimis juosta, padalintas į kvadratus ( ląstelės). Kiekviename langelyje gali būti tam tikras simbolis iš fiksuoto (tam tikroje mašinoje) baigtinio rinkinio, vadinamo abėcėlės tvarkaši mašina. Vienas iš abėcėlės simbolių yra paryškintas ir vadinamas „tarpu“, daroma prielaida, kad iš pradžių visa juosta yra tuščia, tai yra, užpildyta tarpais.

Turingo mašina gali pakeisti juostos turinį naudodama specialų skaitytuvą ir rašiklį. galvos, kuris juda juosta. Kiekvieną akimirką galva yra vienoje iš ląstelių. Turingo mašina iš galvos gauna informaciją apie tai, kokį simbolį mato, ir pagal tai (ir nuo jo vidinės būsenos) nusprendžia, ką daryti, tai yra, kokį simbolį įrašyti dabartinėje ląstelėje ir kur judėti po to (kairėje, teisinga arba likti vietoje). Tai taip pat keičia vidinę mašinos būseną (manome, kad mašina, be juostos, turi baigtinę atmintį, tai yra baigtinį skaičių vidinių būsenų). Taip pat turime susitarti, nuo ko pradedame ir kada baigsime darbus.

Taigi, norint apibrėžti Tiuringo mašiną, reikia nurodyti šiuos objektus:

Šuolių lentelė yra išdėstyta taip: kiekvienai porai nurodomas trigubas. Čia poslinkis yra vienas iš skaičių -1 (kairėje), 0 (vietoje) ir 1 (dešinėje). Taigi, perėjimo lentelė yra tipo S x A -> S x A x (-1,0,1) funkcija, apibrėžta tose porose, kuriose būsena nėra galutinė.

Belieka apibūdinti Tiuringo mašinos elgesį. Kiekvieną akimirką yra keletas konfigūracija, susidedantis iš juostos turinio (formaliai kalbant, juostos turinys yra savavališkas atvaizdavimas Z -> A ), dabartinės galvutės padėties (kai kuris sveikasis skaičius ) ir esamos mašinos būsenos (elementas S ). Konfigūracijos transformacija į kitą vyksta pagal natūralias taisykles: lentelėje žiūrime, ką reikia padaryti tam tikrai būsenai ir tam tikram simboliui, tai yra, sužinome naują mašinos būseną, keičiame simbolį į nurodytą, tada perkelkite galvą į kairę, dešinę arba palikite ją vietoje. Tokiu atveju, jei nauja būsena yra viena iš galutinių, mašinos veikimas baigiasi. Belieka susitarti, kaip pateikiame informaciją į mašinos įvestį ir kas yra laikoma jos darbo rezultatu. Darysime prielaidą, kad mašinos abėcėlėje, be tarpo, yra simboliai 0 ir 1 (taip pat, galbūt, kai kurie kiti simboliai). Mašinos įvestis ir išvestis bus baigtinės nulių ir vienetų sekos (dvejetainiai žodžiai). Įvesties žodis užrašomas ant tuščios juostos, mašinos galvutė įdedama į pirmąjį langelį, mašina inicijuojama ir paleidžiama. Jei mašina sustoja, rezultatas yra dvejetainis žodis, kurį galima skaityti pradedant nuo galvos padėties ir judant į dešinę (kol pasirodys kitas simbolis nei 0 ir 1).

Taigi bet kuri Tiuringo mašina apibrėžia tam tikrą dvejetainių žodžių dalinę funkciją. Natūralu vadinti visas tokias funkcijas apskaičiuojamas Tiuringo mašinomis.

Tiuringo mašinos: diskusija

Žinoma, mūsų apibrėžime yra daug konkrečių detalių, kurias galima pakeisti. Pavyzdžiui, juosta gali būti begalė tik viena kryptimi. Galite duoti mašinai dvi juostas. Galime manyti, kad mašina gali parašyti naują simbolį arba judėti, bet ne abu. Galima apriboti abėcėlę, tarkime, kad ją turi sudaryti lygiai 10 simbolių. Galite reikalauti, kad pabaigoje ant juostos nieko nebūtų, išskyrus darbo rezultatą (likusios ląstelės turi būti tuščios). Visi šie ir daugelis kitų pakeitimų nekeičia Tiuringo mašinose apskaičiuojamų funkcijų klasės. Žinoma, nėra ir nekenksmingų pokyčių. Pavyzdžiui, jei uždrausite automobiliui judėti į kairę, tai iš esmės pakeis situaciją, juosta taps nenaudinga, nes nebebus galima grįžti prie senų įrašų.

Kaip suprasti, kurie pokyčiai yra nekenksmingi, o kurie ne? Čia, matyt, reikia tam tikros praktinio programavimo Tiuringo mašinose patirties, bent jau nedidelės. Po to jau galima įsivaizduoti mašinos galimybes visiškai neišrašant programų, o vadovaujantis tik apytiksliu aprašymu. Kaip pavyzdį apibūdinkime mašiną, kuri padvigubina įvesties žodį (sukuria žodį XX, jei įvestis buvo žodis X).

Jei aparatas mato tarpą (įvesties žodis tuščias), jis išjungiamas. Jei ne, įsimena esamą simbolį ir deda ženklą (abėcėlėje, be simbolių 0 ir 1, bus ir jų „pažymėti variantai“ ir ). Tada ji pereina į dešinę į tuščią langelį, po to ten įrašo prisiminto veikėjo kopiją. Tada ji juda į kairę iki ženklo; palaidojęs save ženkle, atsitraukia ir prisimena kitą veikėją ir taip toliau, kol nukopijuoja visą žodį.

Turėdami tam tikrą patirtį, už visų šių frazių galite pamatyti konkrečias Turingo mašinos programos dalis. Pavyzdžiui, žodžiai „įsiminti simbolį ir pereiti į dešinę“ reiškia, kad yra dvi būsenų grupės: viena skirta situacijai, kai išsaugomas nulis, kita, kai saugomas vienas, ir kiekvienoje grupėje judėjimas į dešinę. yra užprogramuotas pirmame tuščiame langelyje.

Turėdami šiek tiek daugiau patirties, galite suprasti, kad šiame aprašyme yra klaida, nes nenukopijuojamas visas žodis, nes simbolių kopijos nesiskiria nuo pradinio žodžio simbolių. Taip pat aišku, kaip ištaisyti klaidą, reikia rašyti specialiuosius simbolius ir kaip kopijas, o paskutiniame etape pašalinti visus ženklus.

77 . Parodykite, kad atvirkštinė funkcija, kuri apverčia žodį atgal, yra apskaičiuojama Tiuringo mašinoje.

Kitas neformalaus samprotavimo pavyzdys: paaiškinkime, kodėl negalima naudoti papildomų simbolių, išskyrus 0 , 1 ir tuščią simbolį. Tegul būna mašina su didele N simbolių abėcėle. Sukurkime naują mašiną, kuri imituos senosios veikimą, bet kiekviena senosios ląstelė atitiks naujojo k ląstelių bloką. Bloko dydis (skaičius k) bus fiksuotas taip, kad bloko viduje būtų galima užkoduoti visus didžiosios abėcėlės ženklus nuliais ir vienetais. Pradiniai simboliai 0 , 1 ir tuščias bus užkoduoti kaip 0, po kurio seka (k-1) tušti simboliai, 1, po kurio seka (k-1) tušti simboliai ir k tuščių simbolių grupė. Pirmiausia reikia perkelti įvesties žodžio raides atstumu k, o tai galima padaryti be papildomų simbolių (pasiekus paskutinę raidę atitolinti, tada pasiekus kitą, perkelti ją ir paskutinę ir pan. ); tereikia suprasti, kad žodžio pabaigą galima identifikuoti kaip poziciją, po kurios seka daugiau nei k tuščių simbolių. Akivaizdu, kad šiame procese atmintyje turime saugoti ribotą informacijos kiekį, todėl tai įmanoma. Po to jau galima žingsnis po žingsnio imituoti originalios mašinos veikimą, o tam irgi pakanka baigtinės atminties (e baigtinio būsenų skaičiaus), nes tik nedidelė imituojamos mašinos galvutės kaimynystė mums svarbu. Galiausiai turime suspausti rezultatą atgal.

Norėdami baigti diskusiją, pateikiame aukščiau žadėtą ​​argumentą, kad bet kuri apskaičiuojama funkcija yra apskaičiuojama Tiuringo mašinoje. Tegul būna funkcija, kurią žmogus gali apskaičiuoti. Tuo pačiu metu jis, žinoma, turi naudoti pieštuką ir popierių, nes informacijos kiekis kad jis gali išlaikyti „savo mintyse“ yra ribotas. Darysime prielaidą, kad jis rašo ant atskirų popieriaus lapų. Be dabartinio lapo, dešinėje yra šūsnis popierių, o kairėje – šūsnis; Dabartinį lapą galite įdėti į bet kurį iš jų, užbaigdami su juo darbą, o kitą paimkite iš kitos krūvos. Vyras turi pieštuką ir trintuką. Kadangi labai mažų raidžių nesimato, aiškiai išskiriamų lapo būsenų skaičius yra baigtinis, ir galime daryti prielaidą, kad kiekvieną akimirką lape užrašoma po vieną raidę iš kokios nors baigtinės (nors ir labai didelės) abėcėlės. Žmogus taip pat turi baigtinę atmintį, todėl jo būsena yra kokios nors baigtinės aibės elementas. Tuo pačiu galima sudaryti kokią nors lentelę, kurioje parašyta, kaip baigsis jo darbas nurodyto turinio lape, pradėtas tam tikroje būsenoje (kas bus lape, kokios būsenos bus žmogus ir iš kurios pakuotės bus paimtas kitas lapas). Dabar jau aišku, kad žmogaus veiksmai kaip tik atitinka Tiuringo mašinos, turinčios didelę (bet baigtinę) abėcėlę ir didelį (bet baigtinį) skaičių vidinių būsenų, darbą.

simuliatorius, skirtas studijuoti universalų atlikėją

Kas tai yra?

Tiuringo mašinos simuliatorius yra universalaus vykdytojo (abstrakčiojo kompiuterio) mokymo modelis, kurį 1936 metais pasiūlė A. Turingas, siekiant patikslinti algoritmo sampratą. Pagal Tiuringo tezę, bet kurį algoritmą galima parašyti kaip programą Tiuringo mašinai. Įrodyta, kad Tiuringo mašina savo galimybėmis prilygsta Posto mašinai ir įprastiems Markovo algoritmams.

Tiuringo mašina susideda iš vežimėlio (skaitymo ir rašymo galvučių) ir begalinės juostos, padalytos į ląsteles. Kiekviename juostos langelyje gali būti simbolis iš tam tikros abėcėlės A=(a 0 ,a 1 ,…,a N ) . Bet kurioje abėcėlėje yra tarpo simbolis, kuris žymimas 0 arba Λ. Įvedant komandas, tarpas pakeičiamas apatiniu brūkšniu „_“.

Tiuringo mašina yra automatas, valdomas stalu. Lentelės eilutės atitinka pasirinktos abėcėlės A simbolius, o stulpeliai – automato būsenas Q=(q 0 ,q 1 ,…,q M ) . Operacijos pradžioje Tiuringo mašina yra būsenoje q 1 . Būsena q 0 yra galutinė būsena: patekęs į ją, automatas baigia savo darbą.

Kiekviename lentelės langelyje, atitinkančiame tam tikrą simbolį a i ir tam tikrą būseną q j , yra komanda, susidedanti iš trijų dalių:

1. simbolis iš abėcėlės A ;
2. judėjimo kryptis: > (dešinėn),
3. naujos mašinos būklė

žinios

1. Falina I.N. Tema „Turingo mašina“ informatikos mokyklos kurse (inf.1september.ru).
2. Mayeris R.V. Pašto ir Tiuringo mašinos (komp-model.narod.ru).
3. Pilščikovas V.N., Abramovas V.G., Vylitok A.A., Karštas I.V. Turingo mašinos ir Markovo algoritmai. Problemų sprendimas, Maskva: Maskvos valstybinis universitetas, 2006 m.
4. Beckmanas I.N. Informatika. 7 paskaita. Algoritmai (profbeckman.narod.ru)
5. Solovjovas A. Diskretioji matematika be formulių (lib.rus.ec)
6. Ershovas S.S. Algoritmų teorijos elementai, Čeliabinskas, SUSU leidybos centras, 2009 m.
7. Varpakhovskis F.L. Algoritmų teorijos elementai, M: Apšvietos, 1970 m.
8. Vereshchagin N.K., Shen A. Skaičiuojamosios funkcijos, M: MTsNMO, 1999.

Ką su juo daryti?

Programos viršuje yra redaktoriaus laukas, kuriame galite laisva forma įvesti problemos sąlygą.

Juostelė perkeliama į kairę ir į dešinę, naudojant mygtukus, esančius kairėje ir dešinėje. Dukart spustelėję juostelės langelį (arba spustelėdami dešiniuoju pelės klavišu ant jo), galite pakeisti jo turinį.

Meniu naudojimas Juostelė galite išsaugoti juostos būseną vidiniame buferyje ir atkurti juostą iš buferio.

Lauke Abėcėlė nustatomi pasirinktos abėcėlės simboliai. Tarpas automatiškai pridedamas prie įvestų simbolių.

Programa įvedama į lentelę lango apačioje. Pirmame stulpelyje yra abėcėlės simboliai ir jis pildomas automatiškai. Pirmoje eilutėje pateikiamos visos galimos būsenos. Galite pridėti ir pašalinti lentelės (būsenos) stulpelius naudodami virš lentelės esančius mygtukus.

Įvesdami komandą į lentelės langelį, pirmiausia turite įvesti naujas simbolis, tada perėjimo kryptis ir būsenos numeris. Jei simbolis praleistas, pagal numatytuosius nustatymus jis nesikeičia. Jei valstybės numeris yra praleistas, automato būsena pagal nutylėjimą nesikeičia.

Tiesiai lauke komentuoti galite komentuoti sprendimą bet kokia forma. Dažniausiai jie paaiškina, ką reiškia kiekviena Turingo mašinos būsena.

Programa gali būti vykdoma nuolat (F9) arba žingsniais (F8). Komanda, kuri dabar bus vykdoma, paryškinta žaliame fone. Vykdymo greitis reguliuojamas meniu Greitis.

Tiuringo mašinos užduotys gali būti saugomos failuose. Išsaugoma užduoties sąlyga, abėcėlė, programa, komentarai ir pradinė juostos būsena. Įkeliant užduotį iš failo ir išsaugant ją į failą, juostos būsena automatiškai įrašoma į buferį.

Jei pastebėjote klaidą ar turite pasiūlymų, pastabų, nusiskundimų, prašymų ir pareiškimų, rašykite el.

Techniniai reikalavimai

Programa veikia pagal linijos operacines sistemas Windows bet kuriame šiuolaikiniame kompiuteryje.

Licencija

Programa yra nemokama nekomerciniam naudojimui. Programos šaltinio kodas nėra platinamas.

Programa ateina su kaip yra“, tai yra, autorius neprisiima jokios atsakomybės už visas galimas jo naudojimo pasekmes, įskaitant moralinius ir materialinius nuostolius, įrangos gedimą, fizinius ir psichinius sužalojimus.

Pateikiant programą kitose svetainėse, būtina nuoroda į šaltinį.

1. 1) bet kokios formos medžiagos publikavimas, įskaitant medžiagos skelbimą kitose interneto svetainėse;
2. 2) nebaigtų ar pakeistų medžiagų platinimas;
3. 3) medžiagos įtraukimas į rinkinius bet kurioje laikmenoje;
4. 4) komercinės naudos gavimas pardavus ar kitaip naudojant medžiagas.

Medžiagos atsisiuntimas reiškia, kad sutikote su šios licencijos sutarties sąlygomis.

parsisiųsti

Išpakavus archyvą, programa veikia ir nereikalauja jokių papildomų instaliacijų.

1. Tiuringo mašinos aprašymas. 3

1.1 Tiuringo mašinos kaip algoritmo savybės. 5

2. Algoritmų sudėtingumas. 7

2.1 Problemų sudėtingumas.. 9

3. Tiuringo mašina ir algoritmiškai neišsprendžiamos problemos.. 12

Išvada. 16

Literatūra.. 18

Įvadas

Turingo mašina yra labai paprastas skaičiavimo įrenginys. Jį sudaro begalinio ilgio juosta, padalinta į langelius, ir galvutė, kuri juda juosta ir gali skaityti bei rašyti simbolius. Taip pat Tiuringo mašina turi tokią charakteristiką kaip būsena, kurią galima išreikšti sveikuoju skaičiumi nuo nulio iki tam tikros didžiausios vertės. Priklausomai nuo būsenos, Tiuringo mašina gali atlikti vieną iš trijų dalykų: įrašyti simbolį langelyje, perkelti vieną langelį į dešinę arba į kairę ir nustatyti vidinę būseną.

Turingo mašina yra labai paprasta, tačiau ji gali paleisti beveik bet kurią programą. Visiems šiems veiksmams atlikti pateikiama speciali taisyklių lentelė, kurioje nurodyta, ką daryti su įvairiais esamų būsenų ir iš juostos nuskaitytų simbolių deriniais.

1947 m. Alanas Turingas išplėtė apibrėžimą ir apibūdino „universalią Tiuringo mašiną“. Vėliau, sprendžiant tam tikrų klasių problemas, buvo įvesta jos įvairovė, kuri leido atlikti ne vieną, o kelias užduotis.

1. Tiuringo mašinos aprašymas

Šio kūrinio sukūrimo priešistorė susijusi su Davido Hilberto neišspręstų matematinių problemų formulavimu Tarptautiniame matematikų kongrese Paryžiuje 1900 m. Vienas iš jų buvo paprastosios aritmetikos aksiomų sistemos nuoseklumo įrodymo uždavinys, kurį Hilbertas vėliau patikslino kaip „sprendžiamumo problemą“ – radimas. bendras metodas, nustatyti duoto teiginio formaliosios logikos kalba pagrįstumą.

Turingo straipsnis kaip tik davė atsakymą į šią problemą – antroji Hilberto problema pasirodė neišsprendžiama. Tačiau Turingo darbo reikšmė gerokai viršijo problemą, dėl kurios jis buvo parašytas.

Pateikiame šio Johno Hopcrofto darbo aprašymą: „Dirbdamas ties Hilberto problema, Turingas turėjo aiškiai apibrėžti pačią metodo sąvoką Pradedant nuo intuityvios idėjos apie metodą kaip tam tikrą algoritmą, t.y. procedūra, kurią galima atlikti mechaniškai, be kūrybinio įsikišimo“, – jis parodė, kaip šią idėją galima įkūnyti kaip detalų skaičiavimo proceso modelį. Gautas skaičiavimo modelis, kuriame kiekvienas algoritmas buvo suskirstytas į paprastų seką. , elementarūs žingsniai, buvo logiška konstrukcija, vėliau pavadinta Tiuringo mašina.

Tiuringo mašina yra baigtinio automato modelio plėtinys, plėtinys, apimantis potencialiai begalinę atmintį su galimybe judėti (judėti) iš šiuo metu žiūrimos ląstelės į kairę arba dešinę kaimynę.

Formaliai Tiuringo mašiną galima apibūdinti taip. Tegu duota:

baigtinė būsenų rinkinys – Q, kurioje gali būti Tiuringo mašina;

baigtinis juostos simbolių rinkinys - Г;

funkcija δ (perėjimo funkcija arba programa), kuri gaunama susiejant porą iš Dekarto sandaugos Q x T (mašina yra qi būsenoje ir apžvelgia simbolį gi) į Dekarto sandaugos Q x T x (L) trigubą. , R) (aparatas pereina į būseną qi, pakeičia simbolį gi simboliu gj ir juda į kairę arba į dešinę po vieną juostos simbolį) – Q x G --> Q x G x (L,R)

vienas simbolis iš G-->e (tuščias);

poaibis Σ є Г - -> apibrėžiamas kaip juostos įvesties simbolių poaibis, o e є (Г - Σ);

viena iš būsenų - q0 є Q yra pradinė mašinos būsena.

Spręstinas uždavinys pateikiamas užrašant į juostą baigtinį skaičių simbolių iš aibės Σ є Г - Si є Σ:

eS1S2S3S4... ... ...Sne

po kurio mašina perkeliama į pradinę būseną, o galvutė nustatoma ties kairiausiu netuščiu simboliu (q0,w) –, po to pagal nurodytą perėjimo funkciją (qi,Si) - -> (qj, Sk, L arba R), aparatas pradeda keisti simbolius, kuriuos reikia peržiūrėti, judinti galvą į dešinę arba į kairę ir pereiti į kitas būsenas, kurias numato perėjimo funkcijos.

Mašina sustoja, jei porai (qi,Si) neapibrėžta perėjimo funkcija.

Alanas Turingas pasiūlė, kad bet koks algoritmas intuityvia šio žodžio prasme gali būti pavaizduotas lygiaverte Tiuringo mašina. Ši prielaida žinoma kaip Bažnyčios-Turingo tezė. Kiekvienas kompiuteris gali imituoti Tiuringo mašiną (ląstelių perrašymo, palyginimo ir perkėlimo į kitą gretimą langelį operacijos, atsižvelgiant į mašinos būsenos pokyčius). Todėl jis gali modeliuoti algoritmus bet kokiu formalizmu, o iš šios tezės išplaukia, kad visi kompiuteriai (nepriklausomai nuo galios, architektūros ir pan.) yra lygiaverčiai pagal esminę algoritminių uždavinių sprendimo galimybę.

1.1 Tiuringo mašinos kaip algoritmo savybės

Turingo mašinos pavyzdyje gerai atsekamos algoritmų savybės. Paprašykite mokinių parodyti, kad Tiuringo mašina turi visas algoritmo savybes.

diskretiškumas. Įvykdžius kiekvieną žingsnį Tiuringo mašina gali pereiti tik į (k + 1)-ąjį žingsnį, nes kiekvienas veiksmas lemia, koks bus (k + 1)-asis žingsnis.

Aiškumas. Kiekviename žingsnyje į langelį įrašomas simbolis iš abėcėlės, automatas atlieka vieną judesį (L, P, N), o Tiuringo mašina pereina į vieną iš aprašytų būsenų.

Ryžtingumas. Kiekvienoje Tiuringo mašinos lentelės langelyje įrašoma tik viena parinktis. Kiekviename žingsnyje rezultatas apibrėžiamas vienareikšmiškai, todėl problemos sprendimo žingsnių seka yra vienareikšmiškai apibrėžta, t.y. jei Tiuringo mašinai tiekiamas tas pats įvesties žodis, tada išvesties žodis bus tas pats kiekvieną kartą.

Efektyvumas. Kalbant apie turinį, kiekvieno žingsnio rezultatai ir visa veiksmų seka yra vienareikšmiškai nulemti, todėl teisingai parašyta Tiuringo mašina pereis į būseną q0 per baigtinį žingsnių skaičių, per baigtinį žingsnių skaičių bus gautas atsakymas į problemos klausimą.

Masinis personažas. Kiekviena Turingo mašina apibrėžiama per visus galiojančius abėcėlės žodžius, ir tai yra masės savybė. Kiekviena Tiuringo mašina skirta spręsti vienos klasės uždavinius, t.y. Kiekviena užduotis turi savo (naują) Tiuringo mašiną.

2. Algoritmų sudėtingumas

Algoritmo sudėtingumą lemia skaičiavimo galia, reikalinga jam vykdyti. Algoritmo skaičiavimo sudėtingumas dažnai matuojamas dviem terminais: T (laiko sudėtingumas) ir S (erdvės sudėtingumas arba atminties reikalavimai). Tiek T, tiek S paprastai pateikiamos kaip n funkcijos, kur n yra įvesties dydis. (Yra ir kitų sudėtingumo matavimo būdų: atsitiktinių bitų skaičius, ryšio kanalo plotis, duomenų kiekis ir kt.)

Paprastai algoritmo skaičiavimo sudėtingumas išreiškiamas naudojant "Big O" žymėjimą, ty jis apibūdinamas skaičiavimo sudėtingumo dydžiu. Tai tiesiog sudėtingumo išplėtimo terminas, kuris sparčiausiai auga su n, visi žemesnės eilės terminai yra ignoruojami. Pavyzdžiui, jei tam tikro algoritmo sudėtingumas laike yra 4n2+7n+12, tai skaičiavimo sudėtingumas yra n2 dydžio, parašytas kaip O(n2).

Tokiu būdu išmatuotas laiko sudėtingumas nepriklauso nuo įgyvendinimo. Nereikia žinoti tikslaus įvairių komandų vykdymo laiko, bitų skaičiaus, naudojamų įvairiems kintamiesiems pavaizduoti, ar net procesoriaus greičio. Vienas kompiuteris gali būti 50 procentų greitesnis už kitą, o trečiojo duomenų magistralė gali būti dvigubai platesnė, tačiau algoritmo sudėtingumas, matuojamas pagal dydį, nepasikeistų. Tai nėra sukčiavimas, kai kalbama apie tokius sudėtingus algoritmus, kaip aprašyti šioje knygoje, visa kita gali būti nepaisoma (iki pastovaus faktoriaus), palyginti su sudėtingumo dydžiu.

Šis žymėjimas leidžia pamatyti, kaip įvesties dydis turi įtakos laiko ir atminties reikalavimams. Pavyzdžiui, jei T = O(n), tada padvigubinus įvestį, taip pat padvigubės algoritmo vykdymo laikas. Jei T=O(2n), tai pridėjus vieną bitą prie įvesties duomenų, algoritmo vykdymo laikas padvigubės.

Paprastai algoritmai klasifikuojami pagal jų laiko ar erdvės sudėtingumą. Algoritmas vadinamas konstanta, jei jo sudėtingumas nepriklauso nuo n: 0(1). Algoritmas yra tiesinis, jei jo sudėtingumas laike yra O(n). Algoritmai gali būti kvadratiniai, kubiniai ir kt. Visi šie algoritmai yra polinominiai, jų sudėtingumas yra O(m), kur m yra konstanta. Polinominio laiko sudėtingumo algoritmai vadinami daugianario laiko algoritmais

Algoritmai, kurių sudėtingumas lygus O(tf(n)), kur t yra didesnė už 1 konstanta, o f(n) yra tam tikra n daugianario funkcija, vadinami eksponeniniais. Eksponentinių algoritmų poaibis, kurio sudėtingumas yra O(cf(n)), kur c yra konstanta, o f(n) auga greičiau nei konstanta, bet lėčiau nei tiesinė funkcija, vadinamas superpolinominiu.

Idealiu atveju kriptografas norėtų teigti, kad geriausias algoritmas, skirtas sulaužyti sukurtą šifravimo algoritmą, turi eksponentinį laiko sudėtingumą. Praktiškai stipriausi teiginiai, kuriuos galima pateikti, atsižvelgiant į dabartinę skaičiavimo sudėtingumo teorijos būklę, yra tokios formos: „visi žinomi algoritmai, skirti sulaužyti tam tikrą kriptosistemą, turi superpolinominį laiko sudėtingumą“. Tai reiškia, kad žinomi atakos algoritmai turi superpolinominį laiko sudėtingumą, tačiau kol kas neįmanoma įrodyti, kad negalima atrasti skrodimo algoritmo, turinčio daugianario laiko sudėtingumą. Skaičiavimo sudėtingumo teorijos plėtra kada nors gali leisti sukurti algoritmus, kuriems matematiniu tikslumu būtų galima atmesti algoritmų su polinominiu atidarymo laiku egzistavimą.