Povedzme, že už dávno ... Ale v skutočnosti pred vytvorením Turingovho stroja boli stroje vytvorené na vykonávanie rôznych akcií. Napríklad, musíte vziať logaritmus, nuka, ale poďme nitovať stroj, ktorý prečíta číslo a vezme logaritmus. Alebo potrebujete, povedzme, dve čísla na sčítanie – tu je stroj na sčítanie dvoch čísel. A aj teraz existujú také stroje, napríklad kalkulačky. Čo môžu urobiť? Sčítanie, odčítanie, násobenie a inžinierstvo - dokonca aj kosínus alebo sínus. Ukazuje sa, že tieto hlúpe stroje, okrem akcií, ktoré sú v nich zaznamenané, môžu a nemôžu vykonávať nič.

Bolo by teda veľmi zaujímavé vytvoriť taký stroj, ktorý by nečítal čísla a nie symboly, ale algoritmus a vykonával by ho, teda vytvoril by programovateľný stroj. To je to, čo urobil Turing (poviem, že existuje veľa takýchto abstrakcií okrem Turinga). A prišiel s modelom takéhoto auta. Ukázalo sa, že na vykonávanie zložitých algoritmov potrebujete iba vozík, nekonečnú pásku a schopnosť meniť hodnoty zaznamenané na páske a pohybovať sa po nej. Ukazuje sa, že táto abstrakcia sa dá v skutočnosti zmeniť na skutočný stroj, jediný, s tým obmedzením, že stroju nemôžeme poskytnúť nekonečnú pásku, ale môžeme vyrobiť veľmi dlhú pásku;)

Ustúpiť. O fungovaní Turingovho stroja sa vlastne ani netreba baviť, ako som povedal, dá sa nájsť veľmi jednoducho. Preto budeme predpokladať, že už viete, ako to funguje.

Turingov stroj vykonáva niekoľko jednoduchých algoritmov, to je nesporné. Ale čo tie záludné? A ako napríklad zorganizovať cyklus pomocou MT? Alebo ako zistíte vetvenie? Ukazuje sa, že existujú teorémy, ktoré dokazujú, že MT môže vykonávať slučky a vetvy, čo nám hovorí, že pomocou veľmi jednoduchého mechanizmu je možné poskladať programy z jednoduchých blokov, ako sú vetvy a slučky, čo znamená, že všetko, čo sa dá naprogramovať, môže byť naprogramovaný. A tu by teoreticky malo byť vysvetlenie, že existujú aj nevyčísliteľné funkcie, a teda neriešiteľné problémy, a tieto problémy nemožno vyriešiť pomocou MT. Tu je návod.

Nikto však nevynašiel nič lepšie ako Turingov stroj, takže všetky programovacie jazyky, ktoré teraz používame, nedokážu naprogramovať viac ako Turingov stroj. Odtiaľ pochádza koncept Turingovej úplnosti, čo znamená, že jazyk (alebo niečo iné) je Turingov kompletný, ak ho možno použiť na písanie všetkých algoritmov, ktoré bežia na Turingovom stroji. A že jazyk je Turingov kompletný, môžete dokázať tak, že do neho napíšete emulátor Turingovho stroja. Toto sú koláče.

Z pohľadu matematiky je príspevok svinstvo, ale je jasné, na čo sme potrebovali Turingov stroj. Vlastne písanie algoritmov pre tento stroj je zaujímavá hádanka. Verím tým, ktorí hovoria, že po naprogramovaní exp (x) na Turingovom stroji skutočne pochopil, čo je algoritmus. Ešte som to neskúšal, ale je to zaujímavá výzva.

tréningový simulátor pre univerzálnych umelcov

Čo to je?

Simulátor "Turingov stroj" je tréningový model univerzálneho vykonávateľa (abstraktný počítačový stroj), ktorý v roku 1936 navrhol A. Turing na objasnenie konceptu algoritmu. Podľa Turingovej tézy môže byť akýkoľvek algoritmus napísaný ako program pre Turingov stroj. Je dokázané, že Turingov stroj je svojimi schopnosťami ekvivalentný Postovmu stroju a normálnym Markovovým algoritmom.

Turingov stroj pozostáva z vozíka (čítacej a zapisovacej hlavy) a nekonečnej pásky rozdelenej na bunky. Každá bunka na páske môže obsahovať symbol z nejakej abecedy A = (a 0, a 1,…, a N). Každá abeceda obsahuje znak medzery, ktorý je označený ako 0 alebo Λ. Pri zadávaní príkazov sa medzera nahradí znakom podčiarknutia „_“.

Turingov stroj je stroj poháňaný stolom. Riadky v tabuľke zodpovedajú symbolom zvolenej abecedy A a stĺpce zodpovedajú stavom automatu Q = (q 0, q 1,…, q M). Na začiatku prevádzky je Turingov stroj v stave q 1. Stav q 0 je konečný stav: po jeho vstupe automat ukončí svoju prácu.

Každá bunka tabuľky zodpovedajúca nejakému symbolu a i a nejakému stavu q j obsahuje príkaz pozostávajúci z troch častí:

1. znak z abecedy A;
2. smer pohybu:> (vpravo),
3. nový stav stroja

správy

1. Falina I.N. Téma "Turingov stroj" v školskom kurze informatiky (inf.1september.ru).
2. Mayer R.V. Post a Turingove stroje (komp-model.narod.ru).
3. Pil'shikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Turingov stroj a Markovove algoritmy. Riešenie problémov, Moskva: Moskovská štátna univerzita, 2006.
4. Bekman I.N. Počítačová veda. Prednáška 7. Algoritmy (profbeckman.narod.ru)
5. A. Diskrétna matematika bez vzorcov (lib.rus.ec)
6. Ershov S.S. Prvky teórie algoritmov, Čeľabinsk, SUSU Publishing Center, 2009.
7. Varpakhovsky F.L. Elements of the theory of algorithms, M: Education, 1970.
8. Vereshchagin N.K., Shen A. Vypočítateľné funkcie, Moskva: MTsNMO, 1999.

čo s tým robiť?

V hornej časti programu je pole editora, kde môžete zadať problémový stav vo voľnej forme.

Páska sa posúva doľava a doprava pomocou tlačidiel umiestnených naľavo a napravo od nej. Dvojitým kliknutím na bunku na páse s nástrojmi (alebo kliknutím pravým tlačidlom myši) môžete zmeniť jej obsah.

Pomocou ponuky stuha môžete si zapamätať stav pásky vo vnútornej vyrovnávacej pamäti a obnoviť pásku z vyrovnávacej pamäte.

V teréne Abeceda znaky zvolenej abecedy sú nastavené. K zadaným znakom sa automaticky pridá medzera.

Program sa zadáva do tabuľky v spodnej časti okna. Prvý stĺpec obsahuje znaky abecedy, vypĺňa sa automaticky. V prvom riadku sú uvedené všetky možné stavy. Stĺpce tabuľky (stavy) môžete pridávať a odoberať pomocou tlačidiel umiestnených nad tabuľkou.

Pri zadávaní príkazu do bunky tabuľky je potrebné najskôr zadať nový znak, potom smer prechodu a číslo stavu. Ak je znak vynechaný, štandardne sa nezmení. Ak je číslo stavu vynechané, predvolene sa stav stroja nezmení.

Vpravo v poli Komentár k riešeniu môžete zadať akúkoľvek formu komentárov. Najčastejšie vysvetľujú, čo jednotlivé stavy Turingovho stroja znamenajú.

Program je možné vykonávať nepretržite (F9) alebo krok za krokom (F8). Príkaz, ktorý sa teraz vykoná, je zvýraznený zeleným pozadím. Rýchlosť vykonávania nastaviteľná cez menu Rýchlosť.

Problémy Turingovho stroja je možné uložiť do súborov. Uloží sa problémový stav, abeceda, program, komentáre a počiatočný stav pásky. Keď sa úloha načíta zo súboru a uloží do súboru, stav pásky sa automaticky zapíše do vyrovnávacej pamäte.

Ak si všimnete chybu alebo máte návrhy, pripomienky, sťažnosti, žiadosti a vyjadrenia, napíšte.

Technické požiadavky

Program beží pod operačnými systémami linky Windows na všetkých moderných počítačoch.

Licencia

Program je zadarmo na nekomerčné použitie. Zdrojový kód programu nie je distribuovaný.

Program dodáva " ako je“ To znamená, že autor nenesie žiadnu zodpovednosť za všetky možné následky jeho použitia, vrátane morálnych a materiálnych strát, zlyhania zariadenia, fyzických a duševných zranení.

Pri umiestnení programu na iné webové stránky je potrebný odkaz na zdroj.

1. 1) zverejňovanie materiálov v akejkoľvek forme vrátane zverejňovania materiálov na iných webových stránkach;
2. 2) distribúcia nekompletných alebo upravených materiálov;
3. 3) zahrnutie materiálov do zbierok na akomkoľvek médiu;
4. 4) získavanie komerčných výhod z predaja alebo iného použitia materiálov.

Stiahnutím materiálov potvrdzujete, že ste prijali podmienky tejto licenčnej zmluvy.

Stiahnuť ▼

Po rozbalení archívu je program funkčný a nevyžaduje žiadne ďalšie inštalácie.

Turingov stroj (MT)- abstraktný vykonávateľ (abstraktný počítací stroj). V roku 1936 navrhol Alan Turing formalizovať koncept algoritmu.

Turingov stroj je rozšírením konečného stroja a podľa Church - Turingovej tézy, schopný napodobniť všetkých účinkujúcich(špecifikovaním prechodových pravidiel), ktoré nejakým spôsobom implementujú proces výpočtu krok za krokom, v ktorom je každý krok výpočtu celkom elementárny.

To znamená, že pomocou nejakého Turingovho stroja možno implementovať akýkoľvek intuitívny algoritmus.

Collegiate YouTube

1 / 5

✪ 09 - Úvod do algoritmov. Turingov stroj

✪ Turingov stroj - Alexander Shen

✪ Prednáška 20: Turingov stroj

✪ Turingov stroj. Príklad práce

✪ 16 - Vypočítateľnosť. Turingove stroje. Motivácia a príklady

titulky

Konštrukcia Turingovho stroja

Turingov stroj obsahuje neobmedzené v oboch smeroch stuha(Možné sú Turingove stroje, ktoré majú niekoľko nekonečných pások), rozdelených na bunky a ovládacie zariadenie(tiež nazývaný hlava na čítanie a zápis (GZCH)), schopný byť v jednom z súbor štátov... Počet možných stavov riadiaceho zariadenia je konečný a presne špecifikovaný.

Ovládacie zariadenie sa môže pohybovať po páske doľava a doprava, čítať a zapisovať do buniek znaky nejakej konečnej abecedy. Vyniká špeciálne prázdny znak, ktorý vyplní všetky bunky pásky, okrem tých z nich (konečný počet), na ktoré sa zapisujú vstupné dáta.

Riadiace zariadenie pracuje v súlade s pravidlá prechodu ktoré predstavujú algoritmus, realizovateľné tento Turingov stroj. Každé pravidlo prechodu predpisuje stroj v závislosti od Aktuálny stav a symbol pozorovaný v aktuálnej bunke, napíšte do tejto bunky nový symbol, prepnite sa do nového stavu a posuňte sa o jednu bunku doľava alebo doprava. Niektoré stavy Turingovho stroja možno označiť ako terminál a prechod na ktorýkoľvek z nich znamená koniec práce, zastavenie algoritmu.

Turingov stroj je tzv deterministický ak sa s každou kombináciou symbolu štátu a prúžku v tabuľke zhoduje najviac jedno pravidlo. Ak existuje dvojica „prúžkovaný symbol – stav“, pre ktorú existujú 2 a viac inštrukcií, takýto Turingov stroj je tzv. nedeterministické.

Popis Turingovho stroja

Konkrétny Turingov stroj je špecifikovaný vymenovaním prvkov množiny písmen abecedy A, množiny stavov Q a množiny pravidiel, podľa ktorých stroj funguje. Majú tvar: qiaj → q i1 a j1 dk (ak je hlava v stave qi a v pozorovanej bunke je napísané písmeno aj, hlava prejde do stavu q i1, do bunky je napísané a j1 namiesto aj robí hlava pohyb dk, ktorý má tri možnosti: jedna bunka doľava (L), jedna bunka doprava (R), zostať na mieste (N)). Pre všetky možné konfigurácie existuje presne jedno pravidlo (pre nedeterministický Turingov stroj môže existovať veľká kvantita pravidlá). Neexistujú žiadne pravidlá iba pre konečný stav, v ktorom raz auto zastaví. Okrem toho musíte určiť koncový a počiatočný stav, počiatočnú konfiguráciu na páse a umiestnenie hlavy stroja.

Príklad Turingovho stroja

Uveďme príklad MT na násobenie čísel v unárnej číselnej sústave. Záznam pravidla "qiaj → q i1 a j1 R / L / N" je potrebné chápať takto: qi je stav, v ktorom sa toto pravidlo vykonáva, aj je údaj v bunke, v ktorej sa nachádza hlava, q i1 je stav, do ktorého je potrebné prejsť, a j1 - čo je potrebné zapísať do bunky, R / L / N - príkaz na pohyb.

Stroj funguje podľa nasledujúcich pravidiel:

Popis stavov:

Vynásobte pomocou MT 3 x 2 v jednotkovej sústave. V protokole sú uvedené počiatočné a konečné stavy MT, počiatočná konfigurácia na páse a umiestnenie hlavy stroja (podčiarknutý symbol).

Štart. Sme v stave q 0, do stroja sme zadali údaje: * 111x11 = *, hlava stroja sa nachádza na prvom znaku *.

1. krok. Pozrime sa na tabuľku pravidiel, čo stroj urobí, keď bude v stave q 0 a nad symbolom „*“. Toto je pravidlo z 1. stĺpca 5. riadku - q 0 * → q 0 * R. To znamená, že prejdeme do stavu q 0 (teda nemeníme), symbol sa zmení na „*“ (čiže sa nezmení) a po texte, ktorý sme zadali „* 111x11 = *“ sa presunieme na pravá pozícia (R), potom je na 1. znaku 1. Stav q 0 1 (1. stĺpec 1. riadok) je spracovaný podľa pravidla q 0 1 → q 0 1R. To znamená, že opäť je tu jednoducho prechod doprava o 1 pozíciu. Toto sa deje dovtedy, kým sa nepostavíme pri symbole „x“. A tak ďalej: zoberieme stav (index na q), vezmeme symbol, na ktorom stojíme (podčiarknutý symbol), spojíme ich a sledujeme spracovanie výslednej kombinácie podľa tabuľky pravidiel.

Jednoducho povedané, algoritmus násobenia je nasledovný: označte 1. jednotku 2. faktora, nahraďte ju písmenom „a“ a preneste celý 1. faktor za znamienko rovnosti. Prevod sa vykonáva striedavým nahradením jednotiek 1. faktora za „a“ a pridaním rovnakého počtu jednotiek na koniec riadku (vľavo od „*“) úplne vpravo. Potom zmeníme všetky „a“ ​​na znak násobenia „x“ späť na jednotky. A cyklus sa opakuje. Koniec koncov, A vynásobené B môže byť reprezentované ako A + A + A B krát. Teraz označíme 2. jednotku 2. činiteľa písmenom „a“ a znova prenesieme jednotky. Ak pred znakom "=" nie sú žiadne jednotky, násobenie je dokončené.

Turingova úplnosť

Dá sa povedať, že Turingov stroj je najjednoduchší výpočtový stroj s lineárnou pamäťou, ktorý podľa formálnych pravidiel transformuje vstupné dáta pomocou sekvencie elementárne úkony.

Elementárna povaha akcií spočíva v tom, že akcia mení len malý údaj v pamäti (v prípade Turingovho stroja iba jednu bunku) a počet možných akcií je konečný. Napriek jednoduchosti Turingovho stroja sa dá použiť na výpočet všetkého, čo sa dá vypočítať na akomkoľvek inom stroji, ktorý vykonáva výpočty pomocou postupnosti elementárnych akcií. Táto vlastnosť je tzv úplnosť.

Jedným z prirodzených spôsobov, ako dokázať, že výpočtové algoritmy, ktoré môžu byť implementované na jednom stroji, môžu byť implementované na inom stroji, je napodobniť prvý stroj na druhom.

Imitácia je nasledovná. Pri vstupe do druhého stroja je uvedený popis programu (prevádzkového poriadku) prvého stroja D (\ štýl zobrazenia D) a vstupné údaje X (\ štýl zobrazenia X), ktoré mali prísť ku vchodu prvého auta. Je potrebné opísať takýto program (pravidlá pre činnosť druhého stroja), aby sa v dôsledku výpočtov ukázalo, že výstup je rovnaký, aký by vrátil prvý stroj, ak by dostal dáta ako vstup X (\ štýl zobrazenia X).

Ako bolo povedané, na Turingovom stroji je možné simulovať (nastavením pravidiel prechodu) všetky ostatné vykonávače, ktoré nejakým spôsobom implementujú proces výpočtov krok za krokom, v ktorom je každý krok výpočtu dosť elementárny.

Na Turingovom stroji môžete napodobniť Postov stroj, normálne Markovove algoritmy a akýkoľvek program pre bežné počítače, ktorý pomocou nejakého algoritmu konvertuje vstupné dáta na výstupné dáta. Turingov stroj je zase možné napodobniť na rôznych abstraktných interpretoch. Interpreti, u ktorých je to možné, sú povolaní Turing dokončený(Turing dokončený).

Existujú programy pre bežné počítače, ktoré simulujú činnosť Turingovho stroja. Treba však poznamenať, že táto imitácia je neúplná, pretože v Turingovom stroji je abstraktná nekonečná páska. Nekonečná páska s údajmi sa nedá úplne simulovať na počítači s konečnou pamäťou (celková pamäť počítača je RAM, pevné disky, rôzne externé pamäťové médiá, registre a vyrovnávacia pamäť procesora atď. - môžu byť veľmi veľké, no napriek tomu sú vždy konečné).

Varianty Turingovho stroja

Model Turingovho stroja je rozšíriteľný. Môžeme zvážiť Turingove stroje s ľubovoľným počtom pások a viacrozmerné pásky s rôznymi obmedzeniami. Všetky tieto stroje sú však kompletné Turing a sú modelované konvenčným Turingovým strojom.

Turingov stroj bežiaci na polonekonečnom páse

Ako príklad takejto redukcie zvážte nasledujúcu vetu: Pre každý Turingov stroj existuje ekvivalentný Turingov stroj pracujúci na polonekonečnej páske (teda na páske, ktorá je nekonečná v jednom smere).

Zvážte dôkaz, ktorý podal Yu. G. Karpov v knihe „Teória automatov“. Dôkaz tejto vety je konštruktívny, to znamená, že uvedieme algoritmus, pomocou ktorého možno zostrojiť ekvivalentný Turingov stroj s deklarovanou vlastnosťou pre akýkoľvek Turingov stroj. Najprv ľubovoľne očíslujeme bunky pracovnej pásky MT, to znamená, že definujeme nové umiestnenie informácií na páske:

Potom bunky prečíslujeme a budeme predpokladať, že symbol "*" nie je obsiahnutý v MT slovníku:

Nakoniec zmeníme Turingov stroj zdvojnásobením počtu jeho stavov a zmeníme posun hlavy na čítanie a zápis tak, aby v jednej skupine stavov bola činnosť stroja ekvivalentná jeho prevádzke v tieňovanej oblasti a v druhej skupine skupina stavov, v ktorých by stroj fungoval ako pôvodný stroj v netienenej oblasti. Ak sa počas prevádzky MT objaví symbol '*', potom čítacia a zapisovacia hlava dosiahla hranicu zóny:

Počiatočný stav nové auto Turing je inštalovaný v jednej alebo druhej zóne v závislosti od toho, ktorá časť pôvodnej pásky bola v pôvodnej konfigurácii čítacou a zapisovacou hlavou. Je zrejmé, že naľavo od ohraničujúcich značiek „*“ sa páska nepoužíva v ekvivalentnom Turingovom stroji.

Dvojrozmerné Turingove stroje

• Langtonov mravec

pozri tiež

• JFLAP multiplatformový programový simulátor automatov, Turingových strojov, gramatiky, kreslí graf automatu

Turingov stroj je súborom nasledujúcich objektov

• 1) externá abeceda A = (a 0, a 1,…, a n);
• 2) vnútorná abeceda Q = (q 1, q 2,…, q m) je množina stavov;
• 3) sada riadiacich znakov (P, L, S)
• 4) nekonečná páska v oboch smeroch rozdelená na bunky, z ktorých do každej je možné v ľubovoľnom časovom okamihu napísať iba jeden znak z abecedy A;
• 5) ovládacie zariadenie schopné byť v jednom z mnohých stavov

Symbol pre prázdnu bunku je vonkajšie písmeno abecedy a 0.

Medzi stavmi sa rozlišuje počiatočný q 1, v ktorom stroj začína pracovať, a konečný (alebo stop stav) q 0, v ktorom sa stroj zastaví.

Ovládacie zariadenie sa môže pohybovať po páske doľava a doprava, čítať a zapisovať do buniek na páske písmená abecedy A. Ovládacie zariadenie pracuje podľa príkazov, ktoré majú nasledujúci tvar

q i a j> a p X q k

Záznam znamená nasledovné: ak je ovládacie zariadenie v stave qi a v skúmanej bunke je napísané písmeno aj, potom (1) je v bunke napísané ap namiesto aj, (2) stroj prejde na zobrazenie nasledujúcu pravú bunku od tej, ktorá bola práve zobrazená, ak X = P, alebo zobraziť ďalšiu ľavú bunku, ak X = L, alebo pokračovať v prieskume tej istej bunky na páske, ak X = C, (3) riadiace zariadenie prejde do stavu q k.

Keďže činnosť stroja je podľa stavu úplne určená jeho stavom q, v tento moment a obsah bunky, ktorá sa práve pozerá, potom pre každú možnú konfiguráciu q i a j existuje práve jedno pravidlo. Neexistujú žiadne pravidlá iba pre konečný stav, v ktorom auto zastaví. Preto program Turingovho stroja s vonkajšou abecedou A = (a0, a1,…, an) a vnútornou Q = (q1, q2,…, qm) obsahuje najviac m (n + 1) inštrukcií.

Slovo v abecede A alebo v abecede Q alebo v abecede A Q je ľubovoľná sekvencia písmen zodpovedajúcej abecedy. K-tou konfiguráciou rozumieme obraz pásky stroja s informáciou na nej vytvorenou na začiatku k-tého kroku (alebo slovo v abecede A napísané na páske na začiatku k- krok), označujúci, ktorá bunka sa v tomto kroku prezerá a v akom stave je auto. Zmysel majú len finálne konfigurácie, t.j. tie, v ktorých sú všetky bunky pásky, možno s výnimkou konečného počtu, prázdne. Konfigurácia sa nazýva konečná, ak je stav, v ktorom sa stroj nachádza, konečný.

Ak si ako počiatočnú zvolíme akúkoľvek nefinálnu konfiguráciu Turingovho stroja, potom úlohou stroja bude postupne (krok za krokom) transformovať počiatočnú konfiguráciu v súlade s programom stroja až do dosiahnutia finálnej konfigurácie. Potom sa práca Turingovho stroja považuje za dokončenú a výsledkom práce je dosiahnutá konečná konfigurácia.

Povieme, že neprázdne slovo b v abecede A (a 0) = (a 1, ..., an) stroj vníma v štandardnej polohe, ak je napísané v po sebe nasledujúcich bunkách pásky, všetky ostatné bunky sú prázdne a zariadenie sa pozerá na bunku úplne vľavo alebo vpravo od tých, v ktorých je napísané slovo b. Štandardná poloha sa nazýva počiatočná (konečná) poloha, ak stroj, ktorý vníma slovo v štandardnej polohe, je v počiatočnom stave q 1 (resp. v stave zastavenia q 0).

Ak spracovanie slova b prevedie Turingov stroj do konečného stavu, potom hovoria, že je použiteľné pre b, inak neplatí pre b (stroj beží neurčito)

Uvažujme o príklade:

Daný Turingov stroj s vonkajšou abecedou A = (0, 1) (tu je 0 symbol prázdnej bunky), abecedou vnútorných stavov Q = (q 0, q 1, q 2) a s nasledujúcim funkčným diagramom (program):

q10> 1 L q2;

q11> 0 C q2;

q20> 0 Pq0;

q21> 1C q1;

Tento program je možné napísať pomocou tabuľky

V prvom kroku pôsobí nasledujúci príkaz: q 1 0> 1 Л q 2 (riadiace zariadenie je v stave q1 a v pozorovanej bunke je zapísané písmeno 0, namiesto 0 je do bunky zapísaná 1, hlava sa posunie doľava, ovládacie zariadenie prejde do stavu q2), v dôsledku čoho sa na stroji vytvorí nasledujúca konfigurácia:

Nakoniec sa po vykonaní príkazu q 2 0> 0 P q 0 vytvorí konfigurácia

Táto konfigurácia je konečná, pretože stroj bol v stave zastavenia q 0.

Pôvodné slovo 110 teda stroj spracuje na slovo 101.

Výslednú postupnosť konfigurácií je možné zapísať kratším spôsobom (obsah pozorovanej bunky sa zapíše napravo od stavu, v ktorom sa stroj práve nachádza):

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

Turingov stroj nie je nič iné ako pravidlo (algoritmus) na transformáciu slov abecedy A Q, t.j. konfigurácie. Ak teda chcete definovať Turingov stroj, musíte určiť jeho vonkajšiu a vnútornú abecedu, program a uviesť, ktorý zo symbolov označuje prázdnu bunku a konečný stav.

Turingov stroj je jedným z najzaujímavejších a najvzrušujúcejších intelektuálnych objavov 20. storočia. Je to jednoduchý a užitočný abstraktný výpočtový model (počítačový a digitálny), ktorý je dostatočne všeobecný na implementáciu akejkoľvek počítačovej úlohy. Vďaka jednoduchý popis a vykonávanie matematickej analýzy tvorí základ teoretickej informatiky. Tento výskum viedol k hlbšiemu pochopeniu digitálnych počítačov a kalkulu, vrátane pochopenia, že existujú niektoré výpočtové problémy, ktoré nemožno vyriešiť na bežných používateľských počítačoch.

Čo to je a kto vytvoril

Alan Turing sa snažil opísať najprimitívnejší model mechanického zariadenia, ktoré by malo rovnaké základné možnosti ako počítač. Turing prvýkrát opísal stroj v roku 1936 v článku „O vyčísliteľných číslach s aplikáciou na problém riešiteľnosti“, ktorý vyšiel v časopise Proceedings of the London Mathematical Society.

Turingov stroj je výpočtové zariadenie, ktoré pozostáva z čítacej/zápisovej hlavy (alebo „skenera“), cez ktorú prechádza papierová páska. Stuha je rozdelená na štvorce, z ktorých každý nesie jeden znak - "0" alebo "1". Účelom mechanizmu je, že funguje ako prostriedok na vstup a výstup, ako aj ako pracovná pamäť na ukladanie výsledkov medzistupňov výpočtov.

Z čoho sa zariadenie skladá

Každý takýto stroj pozostáva z dvoch komponentov:

1. Neobmedzené krmivo. Je nekonečná v oboch smeroch a je rozdelená na bunky.
2. Automat - riadený program, head-scanner na čítanie a zápis dát. Môže to byť kedykoľvek v jednom z mnohých štátov.

Každý stroj spája dva konečné rady údajov: abecedu prichádzajúcich symbolov A = (a0, a1, ..., am) a abecedu stavov Q = (q0, q1, ..., qp). Stav q0 sa nazýva pasívny. Predpokladá sa, že zariadenie končí svoju prácu, keď naň narazí. Stav q1 sa nazýva počiatočný stav - stroj začína svoje výpočty, pričom je v ňom na začiatku. Vstupné slovo sa nachádza na páske, jedno písmeno v rade na každej pozícii. Na jeho oboch stranách sa nachádzajú iba prázdne bunky.

Ako mechanizmus funguje

Turingov stroj má zásadný rozdiel z výpočtových zariadení - jeho pamäťové zariadenie má nekonečnú pásku, zatiaľ čo v digitálnych zariadeniach má takéto zariadenie pásik určitej dĺžky. Každá trieda úloh je riešená iba jedným zostrojeným Turingovým strojom. Problémy iného druhu zahŕňajú písanie nového algoritmu.

Ovládacie zariadenie, ktoré je v jednom stave, sa môže pohybovať v akomkoľvek smere pozdĺž pásu. Zapisuje a číta z buniek znaky konečnej abecedy. Počas pohybu sa vyberie prázdny prvok, ktorý vyplní pozície, ktoré neobsahujú vstupné údaje. Algoritmus Turingovho stroja definuje pravidlá prechodu pre riadiace zariadenie. Hlave na čítanie a zápis nastavili tieto parametre: zápis nového znaku do bunky, prepnutie do nového stavu, pohyb doľava alebo doprava po páske.

Vlastnosti mechanizmu

Turingov stroj ako iné výpočtových systémov, má svoje vlastné vlastnosti a sú podobné vlastnostiam algoritmov:

1. Diskrétnosť. Digitálny stroj prejde na ďalší krok n + 1 až po dokončení predchádzajúceho. Každá dokončená etapa určuje, čo bude n + 1.
2. Zrozumiteľnosť. Zariadenie vykoná iba jednu akciu pre tú istú bunku. Napíše znak z abecedy a urobí jeden pohyb: doľava alebo doprava.
3. Determinizmus. Každá poloha v mechanizme zodpovedá jediná možnosť vykonávanie danej schémy a v každej fáze sú činnosti a postupnosť ich implementácie jednoznačné.
4. Účinnosť. Presný výsledok pre každý stupeň určuje Turingov stroj. Program vykoná algoritmus a v konečnom počte krokov prejde do stavu q0.
5. Hromadný charakter. Každé zariadenie je definované cez platné abecedné slová.

Funkcie Turingovho stroja

Pri riešení algoritmov je často potrebná implementácia funkcie. V závislosti od možnosti zápisu reťazca na výpočet sa funkcia nazýva algoritmicky rozhodnuteľná alebo nerozhodnuteľná. Za množinu prirodzených alebo racionálnych čísel, slov v konečnej abecede N pre stroj, považujeme postupnosť množiny B - slov v rámci binárnej kódovej abecedy B = (0,1). Výsledok výpočtu tiež zohľadňuje „nedefinovanú“ hodnotu, ktorá nastane, keď algoritmus „zamrzne“. Na implementáciu funkcie je dôležité, aby existoval formálny jazyk v konečnej abecede a aby bol problém rozpoznania správnych popisov riešiteľný.

Program zariadenia

Programy pre Turingov mechanizmus sú formátované tabuľkami, v ktorých prvý riadok a stĺpec obsahujú symboly externej abecedy a hodnoty možných vnútorných stavov stroja - internej abecedy. Tabuľkové údaje sú príkazy, ktoré vníma Turingov stroj. Riešenie problémov je nasledovné: písmeno prečítané hlavou v bunke, nad ktorou sa práve nachádza, a vnútorný stav hlavy stroja určujú, ktorý z príkazov sa musí vykonať. Konkrétne sa takýto príkaz nachádza na priesečníku symbolov vonkajšej a vnútornej abecedy, ktoré sú v tabuľke.

Výpočtové komponenty

Na zostrojenie Turingovho stroja na riešenie jedného konkrétneho problému je potrebné preň definovať nasledujúce parametre.

Externá abeceda. Ide o nejakú konečnú množinu symbolov, označenú znakom A, ktorej základné prvky sú pomenované písmenami. Jeden z nich – a0 – musí byť prázdny. Napríklad abeceda Turingovho zariadenia pracujúceho s binárne čísla, vyzerá takto: A = (0, 1, a0).

Neprerušený reťazec písmenových symbolov zaznamenaný na páske sa nazýva slovo.

Automat je zariadenie, ktoré funguje bez ľudského zásahu. V Turingovom stroji má niekoľko rôznych stavov na riešenie problémov a za určitých podmienok sa pohybuje z jednej polohy do druhej. Zbierka takýchto stavov vozňa je vnútorná abeceda. Má písmenový zápis v tvare Q = (q1, q2 ...). Jedna z týchto pozícií – q1 – by mala byť počiatočná, teda tá, ktorá spúšťa program. Ďalší podstatný prvok je stav q0, ktorý je konečný, teda ten, ktorý ukončí program a uvedie zariadenie do polohy stop.

Skokový stôl. Tento komponent je algoritmus pre správanie vozíka zariadenia v závislosti od stavu stroja a hodnoty práve čítaného znaku.

Algoritmus pre automat

Pohyb Turingovho zariadenia počas prevádzky je riadený programom, ktorý v každom kroku vykonáva nasledujúcu postupnosť akcií:

1. Zápis znaku externej abecedy na pozíciu, vrátane prázdnej, nahradenie prvku v nej vrátane prázdneho.
2. Posuňte sa o jeden bunkový krok doľava alebo doprava.
3. Zmena vášho vnútorného stavu.

Pri písaní programov pre každú dvojicu znakov alebo pozícií je teda potrebné presne popísať tri parametre: ai - prvok z vybranej abecedy A, smer posunu vozíka ("←" doľava, "→" do vpravo, "bod" - žiadny pohyb) a qk - nový stav zariadenia Napríklad príkaz 1 "←" q 2 má hodnotu "nahradiť znak o 1, posunúť hlavu vozíka doľava o jeden krok bunky a urobiť prechod do stavu q 2“.

Turingov stroj: príklady

Príklad 1Úlohou je zostaviť algoritmus, ktorý pridá jednu k poslednej číslici daného čísla umiestneného na páske. Vstupné údaje - slovo - celé desiatkové číslo zapísané v po sebe nasledujúcich bunkách na páske. V počiatočnom momente je zariadenie umiestnené oproti symbolu úplne vpravo - číslici čísla.

Riešenie. Ak je posledná číslica 9, musí sa nahradiť 0 a potom sa musí k predchádzajúcemu znaku pridať jedna. Program v tomto prípade pre toto zariadenie Turing môže byť napísaný takto:

Tu q 1 je stav zmeny číslice, q 0 je stop. Ak v q 1 automat zafixuje prvok z radu 0..8, potom ho nahradí jedným z 1..9 a potom sa prepne do stavu q 0, to znamená, že sa zariadenie zastaví. Ak vozík zafixuje číslo 9, potom ho nahradí 0, potom sa posunie doľava a zastaví sa v stave q 1. Tento pohyb pokračuje, kým zariadenie neopraví číslicu menšiu ako 9. Ak sú všetky znaky rovné 9, nahradia sa nulami, na miesto úvodného prvku sa zapíše 0, vozík sa posunie doľava a zapíše 1 do prázdnej bunky . Ďalším krokom bude prechod do stavu q 0 - stop.

Príklad 2 Dostanete sériu symbolov pre otvorené a zatvorené zátvorky. Je potrebné postaviť Turingovo zariadenie, ktoré by odstránilo pár vzájomných zátvoriek, to znamená prvky umiestnené v rade - „()“. Napríklad počiatočné údaje: „“) (() (()“, odpoveď by mala byť takáto: „).. ((“. Riešenie: mechanizmus, ktorý je v q 1, analyzuje prvok úplne vľavo v riadku.

Stav q 1: ak sa objaví symbol „(“, posuňte sa doprava a prejdite na pozíciu q 2; ak je definované „a 0“, zastavte.

Stav q 2: zátvorka „(“ sa analyzuje na prítomnosť párovania, v prípade zhody by mala byť „“)“. Ak je položka pár, vráťte sa vozíkom doľava a prejdite na q 3.

Stav q 3: vymažte najskôr symbol „(“ a potom „“)“ a prejdite na q 1.