Výraz po dvadsiatych rokoch minulého storočia Počítací stroj sa týka akéhokoľvek stroja, ktorý vykonával prácu ľudský počítač, najmä na tie, ktoré boli vyvinuté v súlade s účinné metódy Cirkev - Turingova téza. Táto práca je formulovaná takto: „Akýkoľvek algoritmus môže byť špecifikovaný vo forme vhodného Turingovho stroja alebo čiastočne rekurzívnej definície a trieda vypočítateľných funkcií sa zhoduje s triedou čiastočne rekurzívnych funkcií a s triedou funkcií vypočítateľných na Turingových strojoch. . " Inými slovami, téza Church-Turinga je definovaná ako hypotéza o povahe mechanických výpočtových zariadení, akými sú napríklad elektronické počítače. Akýkoľvek možný výpočet je možné vykonať na počítači za predpokladu, že je k dispozícii dostatok času a úložného priestoru.

Mechanizmy pracujúce na výpočte s nekonečnom sa stali známymi ako analógový typ. Hodnoty v týchto mechanizmoch boli reprezentované spojitými číselnými hodnotami, napríklad uhlom rotácie hriadeľa alebo rozdielom elektrického potenciálu.

Na rozdiel od analógových strojov mali digitálne stroje schopnosť reprezentovať stav číselnej hodnoty a ukladať každú číslicu oddelene. Digitálne stroje používali pred vynálezom zariadenia RAM rôzne procesory alebo relé.

názov Počítací stroj od štyridsiatych rokov minulého storočia ho koncept začal nahrádzať počítač... Tieto počítače boli schopné robiť výpočty, ktoré robili úradníci. Odkedy hodnoty už neboli závislé na fyzických vlastnostiach (ako v analógových strojoch), logický počítač založený na digitálnom hardvéri dokázal urobiť všetko, čo sa dalo popísať. čisto mechanický systém .

Turingove stroje boli navrhnuté tak, aby formálne matematicky definovali, čo je možné vypočítať za obmedzení výpočtového výkonu. Ak Turingov stroj dokáže splniť úlohu, potom je táto úloha považovaná za Turingovu vypočítateľnú. Turing sa zameral predovšetkým na navrhnutie stroja, ktorý by dokázal určiť, čo sa dá vypočítať. Turing dospel k záveru, že pokiaľ existuje Turingov stroj, ktorý dokáže vypočítať aproximáciu čísla, je táto hodnota spočítateľná. Okrem toho môže Turingov stroj interpretovať logické operátory, ako sú AND, OR, XOR, NOT a If-Then-Else, aby určil, či

Často riešime problémy rôznej zložitosti: každodenné, matematické atď. Niektoré sú ľahko riešiteľné, nad niektorými musíme veľa premýšľať, pre niektoré nikdy nenájdeme riešenie.

Vo všeobecnom prípade môže byť spôsob riešenia problému (ak existuje) opísaný pomocou konečného počtu elementárnych akcií.

Riešenie napríklad kvadratickej rovnice:

Priveďte rovnicu do kanonického tvaru \ (a x ^ 2 + b x + c = 0 \)
Ak \ (a = 0 \), tak toto lineárna rovnica s riešením \ (x = \ frac (-c) (b) \). Problém je vyriešený. V opačnom prípade prejdite na krok 3.
Vypočítajte diskriminant \ (D = b ^ 2-4 a c \)
Vypočítajte riešenia rovnice \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... Problém je vyriešený.

Môžete zaviesť nasledujúci intuitívny koncept algoritmu:

Algoritmus je sada inštrukcií opisujúcich poradie akcií vykonávateľa na dosiahnutie výsledku riešenia problému konečným počtom akcií pre akýkoľvek súbor počiatočných údajov.

Toto samozrejme nie je striktná definícia, ale opisuje podstatu pojmu algoritmus.

Algoritmy sú zostavené na základe konkrétneho interpret, a preto by mali byť navrhnuté v jazyku, ktorému interpret dokáže rozumieť.

Vykonávateľom algoritmu môže byť osoba, alebo to môže byť počítač alebo iný stroj, napríklad tkáčsky stav.

Zvýraznené sú nasledujúce vlastnosti algoritmov:

Diskrétnosť algoritmu by mala byť určitou postupnosťou oddelených, jasne definovaných krokov (akcií). Každá z týchto akcií musí byť časovo obmedzená. Determinizmus v každom kroku algoritmu, ďalší krok je jednoznačne určený aktuálnym stavom systému. V dôsledku toho algoritmus na rovnakých počiatočných údajoch vracia zakaždým rovnaké výsledky bez ohľadu na to, koľkokrát sa vykoná. Zrozumiteľnosť Algoritmus by mal byť formulovaný v jazyku zrozumiteľnom pre interpreta. Ak prichádza v počítači musí algoritmus používať iba tie príkazy, ktoré sú počítaču známe a ktorých výsledok je prísne definovaný. Konečnosť algoritmu musí byť dokončená v konečnom počte krokov. Masívnosť algoritmu by mala byť použiteľná pre rôzne sady vstupných údajov. Inými slovami, algoritmus musí byť vhodný na riešenie triedaúlohy. Keď sa vrátime k kvadratickému príkladu, algoritmus je vhodný na riešenie zo všetkých kvadratické rovnice, nielen jeden alebo viac. Účinnosť algoritmu musí skončiť s určitým výsledkom. Povedzme, vyriešením problému alebo zistením, že neexistujú žiadne riešenia. Ak algoritmus nevedie k výsledku, nie je jasné, prečo je vôbec potrebný.

Nie každý spôsob, ako vyriešiť problém, je algoritmus. Povedzme, že algoritmus neznamená žiadnu voľbu. Väčšina receptov napríklad nie je algoritmom, pretože používajú frázy ako „soľ podľa chuti“. V dôsledku toho je porušená požiadavka determinizmu.

Nie pre každý problém, na ktorý existuje riešenie, existuje aj algoritmus riešenia. Napríklad problém rozpoznávania obrazu je stále do značnej miery nevyriešený a určite nepoužíva rigorózny algoritmus. Použitie neurónových sietí však prináša celkom dobré výsledky.

Obvykle existujú sady pre algoritmus prípustné vstupné Data. Bolo by divné pokúsiť sa použiť algoritmus riešenia rovníc na varenie večere alebo naopak.

Okrem toho je tiež obmedzený súbor možných akcií interpreta, pretože ak by boli povolené akékoľvek akcie, potom by medzi nimi museli byť aj „neprijateľné“.

Prísna definícia algoritmu

Definícia vyššie uvedeného algoritmu nie je striktná. To spôsobuje určité ťažkosti. Najmä pri takejto definícii nie je možné dôsledne dokázať, či je daná trieda problémov riešiteľná algoritmom.

Ukazuje sa, že existuje trieda algoritmicky neriešiteľné problémy- problémy, pre ktoré nie je možné zostaviť algoritmus riešenia. Na to, aby ste mohli dôsledne dokázať algoritmickú nerozhodnuteľnosť, však musíte najskôr dôsledne definovať algoritmus.

V 20.-30. rokoch 20. storočia pracovali na probléme presnej definície algoritmu rôzni matematici, najmä Alan Turing, Emil Leon Post, Andrei Andreevich Markov, Andrei Nikolaevich Kolmogorov, Alonzo Church a ďalší. Ich práca nakoniec viedla k vzniku a rozvoju teórie algoritmov, teórie počtu a rôznych prístupov k počtu a mimochodom k programovaniu všeobecne. Jedným z výsledkov ich práce bol vznik niekoľkých striktných definícií algoritmu zavedených rôznymi spôsobmi, ale navzájom rovnakých.

Budeme sa podrobne zaoberať definíciou Turinga a povrchne analyzovať ekvivalentné definície Post, Church a Markov.

Turingov stroj

Na zavedenie formálnej definície algoritmu Turing prišiel s popisom abstraktného výpočtového stroja nazývaného Turingov počítač alebo jednoducho Turingov stroj.

Alan Turing (1912-1954)

Anglický matematik, logik, kryptograf, možno prvý „hacker“ na svete, stál pri počiatkoch počítačovej vedy a teórie umelej inteligencie. Významne prispel k víťazstvu spojeneckých síl v druhej svetovej vojne.

Vstupné údaje pre Turingov stroj sú slová zostavené s pomocou istého abeceda, teda súprava postavy.

Výsledkom práce Turingovho stroja sú tiež slová.

Volá sa slovo, na ktoré je algoritmus použitý vstup... Slovo, ktoré pochádza z práce víkend.

Nazýva sa skupina slov, na ktoré sa algoritmus aplikuje rozsah algoritmu.

Presne povedané, nie je možné dokázať, že akýkoľvek predmet môže byť reprezentovaný vo forme slov zložených v nejakej abecede - na to by sme potrebovali striktnú definíciu objektu. Môžete však skontrolovať, či je možné ľubovoľný náhodný algoritmus, ktorý funguje na objektoch, transformovať tak, aby pracoval so slovami bez zmeny podstaty algoritmu.

Popis Turingovho stroja

Turingov stroj obsahuje pásku, ktorá je neobmedzená v oboch smeroch, rozdelená do buniek a kontrolné zariadenie (nazývané tiež hlava na čítanie a zápis, alebo jednoducho stroj), schopné byť v jednom z mnohých štátov. Počet možných stavov riadiaceho zariadenia je konečný a presne špecifikovaný.

Ovládacie zariadenie sa môže pohybovať vľavo a vpravo po páske, čítať a zapisovať znaky určitej konečnej abecedy do buniek. Pridelí sa špeciálny prázdny znak označený \ (a_0 \) alebo \ (\ Lambda \), ktorý vyplní všetky bunky na páske, okrem tých z nich (konečný počet), na ktorých sú zapísané vstupné údaje.

Ovládač pracuje podľa prechodových pravidiel, ktoré predstavujú algoritmus implementovaný daným Turingovým strojom. Každé pravidlo prechodu inštruuje stroj, v závislosti od aktuálneho stavu a symbolu pozorovaného v aktuálnej bunke, aby do tejto bunky zapísali nový symbol, prepli sa do nového stavu a presunuli jednu bunku doľava alebo doprava. Niektoré stavy Turingovho stroja môžu byť označené ako terminálne a prechod na ktorýkoľvek z nich znamená koniec práce, zastavenie algoritmu.

Napriek tomu, že je Turingov stroj abstraktný koncept, stačí si ho jednoducho predstaviť (aj keď s obmedzenou páskou) a existujú dokonca aj demo stroje, ako je tento:

Algoritmus pre Turingov stroj je vhodné reprezentovať vo forme tabuľky: stĺpce tabuľky zodpovedajú aktuálnemu (pozorovanému) symbolu na páske, riadky zodpovedajú aktuálnemu stavu stroja a bunky obsahujú príkaz, ktorý má vykonať stroj.

Príkaz môže mať zase nasledujúcu štruktúru:

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

Najprv príde symbol abecedy, ktorý musí byť napísaný v aktuálnej bunke \ (a_k \), potom bude pohyb stroja doľava (L), doprava (P) alebo nikam (zostaňte na mieste, H) uvedené. Na konci je naznačený nový stav, do ktorého by mal ísť automat \ (q_m \).

Bunka tabuľky je jasne definovaná aktuálnym symbolom \ (a_i \) a aktuálnym stavom počítača \ (q_j \).

Dohodnime sa, že na začiatku práce je Turingov stroj in počiatočný stav, označené \ (q_1 \) a pri prechode na stav zastavenia\ (q_0 \) algoritmus je dokončený a stroj sa zastaví.

Príklad

Zostavme algoritmus pre Turingov stroj, ktorý k vstupnému slovu pridá 1, čo je desatinné číslo.

Potom je možné algoritmus deskriptívne formulovať takto:

Posuňte sa doprava a nájdite začiatok vstupného slova
Posuňte sa doprava a nájdite koniec vstupného slova
Pridajte jeden k aktuálnemu bitu vstupného slova. Ak existuje číslo od 0 do 8, výjdite. V opačnom prípade napíšte 0, posuňte sa doľava a vráťte sa ku kroku 3.

Napíšte tento algoritmus vo forme tabuľky. Abeceda pozostáva z číslic od 0 do 9 a prázdneho znaku \ (\ Lambda \). Potrebujeme tiež 4 stavy automatu, počítajúce stav zastavenia, zodpovedajúce krokom v popise algoritmu.

Dohodnime sa, že počiatočný stav \ (1 \) je hľadanie začiatku vstupného slova, \ (2 \) je hľadanie konca vstupného slova, \ (3 \) je pridanie 1.

\ (_ (q_j) \ spätné lomítko ^ (a_i) \)	Λ	0	1	2	3	4	5	6	7	8	9
1	1П1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	.3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Sledujme činnosť tohto algoritmu na príklade. Prvý riadok zodpovedá páske, druhý označuje polohu stroja a jeho aktuálny stav.

	1	9	9
1

V stave 1 je automat nad prázdnou bunkou. Zodpovedajúci príkaz z tabuľky „ΛП1“, to znamená, že nechajte bunku prázdnu, presuňte sa doprava a zostaňte v stave 1:

	1	9	9
	1

Automat teraz monitoruje hodnotu „1“. Zodpovedajúci príkaz „1H2“, to znamená, že nechajte „1“ v bunke, nehýbte sa a choďte do stavu „2“:

	1	9	9
	2

V stave „2“ stroj dodržiava hodnotu „1“. Zodpovedajúci príkaz „1P2“, to znamená, že nechajte „1“, presuňte sa doprava a zostaňte v stave „2“:

Situácia sa opakuje:

Teraz, v stave 3 a pri sledovaní symbolu „9“, stroj vykoná príkaz „0L3“:

	1	9	0
		3

Situácia sa opakuje:

Stav „0“ - stav zastavenia. Algoritmus bol dokončený.

Formálny popis

Matematicky možno Turingov stroj opísať nasledovne:

Turingov stroj (MT)

toto je systém formulára \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), kde

\ (A \) - konečná množina symbolov abecedy MT
\ (a_0 \ v A \) - prázdny znak abecedy
\ (Q \) je konečná množina stavov MT
\ (q_1 \ v Q \) - počiatočný stav MT
\ (q_0 \ v Q \) - konečný stav MT (stav zastavenia)
\ (T = \ (A, P, H \) \) je množina posunov MT
\ (\ tau \) - program MT, to znamená funkcia, ktorá špecifikuje mapovanie \ (\ tau: A \ times Q \ spätné lomítko \ (q_0 \) \ rightarrow A \ times T \ times Q \)

Kľúč v teórii algoritmov je Turingova téza.

Voľne formulovaná Turingova téza je formulovaná nasledovne:

Turingova práca na akýkoľvek algoritmicky riešiteľný problém, existuje Turingov stroj, ktorý tento problém rieši. v opačnom prípade pre akýkoľvek algoritmus existuje ekvivalentný Turingov stroj.

Turingova práca nám umožňuje hovoriť o algoritmoch pomocou pomerne jednoduchého matematického aparátu. Navyše je to samotný Turingov stroj univerzálny pohon, a samotná možnosť vytvorenia takého imaginárneho stroja sa stala dôvodom na rozhovor o vytvorení univerzálnej výpočtovej technológie.

Definície alternatívnych algoritmov

Okrem Turingovho stroja existuje niekoľko nezávislých definícií, ktoré sú ekvivalentné s Turingovou definíciou.

Konkrétne ide o definíciu normálneho Markovovho algoritmu prostredníctvom zariadenia Post, prostredníctvom lambda kalkulu Cirkvi.

Uvažujme o týchto metódach.

Poštový stroj

Rok po Turingovi americký matematik Emile Leon Post nezávisle navrhol ďalší abstraktný univerzálny výpočtový stroj, ktorý je v porovnaní s Turingovým strojom trochu zjednodušený.

Poštový stroj pracuje s dvojcifernou abecedou a vnútorný stav zariadenia je nahradený symbolom programový riadok.

V opačnom prípade je stroj Post podobný stroju Turing: existuje automat a existuje nekonečná páska s bunkami.

Poštový stroj môže vykonávať nasledujúce príkazy:

Napíšte 1, prejdite na i-tý riadok programu
Napíšte 0, prejdite na i-tý riadok programu
Posuňte sa doľava, prejdite na i-tý riadok programu
Posuňte sa doprava, prejdite na i-tý riadok programu
Podmienený skok: ak je v pozorovanej bunke 0, prejdite na i-tý riadok programu, v opačnom prípade prejdite na j-tý riadok programu.
Prestaň

Zariadenie Post má tiež niekoľko zakázaných príkazov:

Zápis do bunky 1, ak už existuje 1.
Zápis do bunky 0, ak už existuje 0.

Takéto udalosti vedú k havárii.

Na písanie programov pre poštový stroj môžete použiť nasledujúci zápis:

∨ i - napíšte 1, prejdite na i -tý riadok programu
× i - napíšte 0, prejdite na i -tý riadok programu
← i - vykonajte posun doľava, prejdite na i -tý riadok programu
→ i - vykonajte posun doprava, prejdite na i -tý riadok programu
? ja; j-podmienený skok: ak je v pozorovanej bunke 0, prejdite na i-tý riadok programu, v opačnom prípade prejdite na j-tý riadok programu.
! - zastaviť sa.

Ukážkový program:

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

Tento program vymaže prvý štítok (1) umiestnený napravo od počiatočnej polohy zariadenia a zastaví stroj v cele naľavo od neho.

Celkovo je Postovo auto predchodcom imperatív programovacie jazyky, napríklad C, Fortran atď.

Stĺpik je ekvivalentný stroju Turing. Inými slovami, pre akýkoľvek program pre Turingov stroj môžete napísať ekvivalentný program pre poštový stroj a naopak.

Jedným z dôležitých dôsledkov tejto ekvivalencie je to akúkoľvek abecedu je možné redukovať na binárny kód.

Podobne ako Turingova téza existuje aj Postova téza.

Príspevková práca Akýkoľvek algoritmus môže byť reprezentovaný formou poštového stroja.

Normálny Markov algoritmus

Bežné Markovove algoritmy sú navrhnuté tak, aby sa dali použiť na slová v rôznych abecedách.

Definícia akéhokoľvek normálneho algoritmu pozostáva z dvoch častí:

Abeceda algoritmus
Schémy algoritmus

Je použitý samotný algoritmus slová, to znamená sekvencie postáv abeceda.

Schéma normálneho algoritmu sa nazýva konečná usporiadaná množina tzv substitučné vzorce, z ktorých každý môže byť jednoduché alebo finálny... Výrazy tvaru \ (L \ až D \) sa nazývajú jednoduché substitučné vzorce, kde \ (L \) a \ (D \) sú dve ľubovoľné slová zložené z abecedy algoritmu (nazývanej ľavá a pravá strany substitučného vzorca). Podobne sú konečné substitučné vzorce výrazmi tvaru \ (L \ až \ cdot D \), kde \ (L \) a \ (D \) sú dve ľubovoľné slová zložené z abecedy algoritmu.

Predpokladá sa, že pomocné znaky \ (\ to \) a \ (\ to \ cdot \) nepatria do abecedy algoritmu.

Proces aplikácie normálneho algoritmu na ľubovoľné slovo \ (V \) je nasledujúci sled akcií:

Nech \ (V "\) je slovo získané v predchádzajúcom kroku algoritmu (alebo pôvodné slovo, ak je aktuálny krok prvým).
Ak medzi substitučnými vzorcami neexistuje žiadna substitúcia, ktorej ľavá strana by bola zahrnutá do \ (V "\), potom je práca algoritmu považovaná za dokončenú a výsledkom tejto práce je slovo \ (V" \ ).
V opačnom prípade je medzi substitučnými vzorcami, ktorých ľavá strana je zahrnutá v \ (V "\), vybraná úplne prvá.
Zo všetkých možných reprezentácií slova \ (V "\) v tvare \ (RLS \) (kde \ (R \) je predpona a \ (L \) je prípona), jedno je zvolené tak, že \ (R \) je najkratšia a nasleduje substitúcia \ (V "= RDS \).
Ak bol substitučný vzorec konečný, potom je algoritmus dokončený s výsledkom \ (V "\). V opačnom prípade prejdite na krok 1 (ďalší krok).

Každý normálny algoritmus je ekvivalentný nejakému Turingovmu stroju a naopak - každý Turingov stroj je ekvivalentný nejakému normálnemu algoritmu.

Obvykle sa nazýva analóg Turingovej tézy pre normálne algoritmy princíp normalizácie.

Príklad

Tento algoritmus prevádza binárne čísla na „jednotky“ (v ktorých je záznam nezáporného celého čísla N reťazcom N tyčiniek). Binárne číslo 101 sa napríklad prevedie na 5 paličiek: |||||.

Abeceda: (0, 1, |) Pravidlá:

1 → 0|
|0 → 0||
0 -> (prázdny reťazec)

Pôvodný riadok: 101 Vykonanie:

0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

Rekurzívne funkcie

Systém ekvivalentný Turingovmu stroju je možné postaviť na základe matematických funkcií. Na to musíme zaviesť nasledujúce triedy funkcií:

primitívne rekurzívne funkcie
všeobecné rekurzívne funkcie
čiastočne rekurzívne funkcie

Posledná uvedená trieda sa bude zhodovať s triedou Turingov-vypočítateľných funkcií (to znamená funkcií, na ktorých výpočet je možné zostrojiť algoritmus pre Turingov stroj).

Definícia algoritmu prostredníctvom rekurzívnych funkcií je v podstate v jadre lambda kalkulu a prístup je postavený na jeho základe. funkčné programovanie.

Primitívne rekurzívne funkcie

Trieda primitívnych rekurzívnych funkcií obsahuje základné funkcie a všetky funkcie odvodené od základných pomocou operátorov substitúcie a primitívna rekurzia.

Medzi základné funkcie patrí:

Nulová funkcia \ (O () = 0 \) je funkcia bez argumentov, ktorá vždy vracia \ (0 \).
Funkcia postupnosti \ (S (x) = x + 1 \) je funkcia, ktorá ľubovoľná prirodzené číslo\ (x \) sa zhoduje s nasledujúcim číslom \ (x + 1 \)
Funkcie \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), kde \ (0

Na zostrojenie ostatných funkcií triedy sa používajú operátory:

Striedania. Pre funkciu \ (f \) z \ (m \) premenných a \ (m \) funkcií \ (g_1, \ ldots, g_m \) z \ (n \) premenných každá, výsledok substitúcie \ (g_k \) v \ (f \) je funkcia \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \) z \ (n \) premenných.
Primitívna rekurzia. Nech \ (f (x_1, \ ldots, x_n) \) je funkciou \ (n \) premenných a \ (g (x_1, \ ldots, x_ (n + 2)) \) funkciou \ (n + 2 \) premenné. Potom je výsledkom použitia primitívneho operátora rekurzie na funkcie \ (f \) a \ (g \) funkcia \ (h \) z \ (n + 1 \) premennej tvaru: \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Čiastočne rekurzívne funkcie

Trieda čiastočne rekurzívnych funkcií zahŕňa primitívne rekurzívne funkcie a navyše všetky funkcie, ktoré sú získané z primitívnych rekurzívnych funkcií pomocou operátora minimalizácie argumentov:

Operátor minimalizácie argumentov

Nech \ (f \) je funkciou \ (n \) premenných \ (x_i \ v \ mathbb (N) \). Potom je výsledkom použitia operátora minimalizácie argumentov na funkciu \ (f \) funkcia \ (h \) argumentu \ (n-1 \), definovaná ako:

\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \] kde \ To znamená, že \ (h \) vráti minimálnu hodnotu posledného argumentu do funkcie \ (f \), pri ktorej je \ (f \) nula.

Aj keď primitívne rekurzívne funkcie sú vždy vypočítateľné, čiastočne rekurzívne funkcie nemusia byť pre niektoré hodnoty argumentov definované.

Prísnejšie by sa čiastočne rekurzívne funkcie mali nazývať „čiastočne definované rekurzívne funkcie“, pretože sú definované iba na zlomku možných hodnôt argumentov.

Všeobecné rekurzívne funkcie

Všeobecné rekurzívne funkcie sú podtriedou všetkých čiastočne rekurzívnych funkcií, ktoré sú definované pre akúkoľvek hodnotu argumentu. Problém určenia, či je daná čiastočne rekurzívna funkcia generálna rekurzívna, je algoritmicky nerozhodnuteľné... Tým sa dostávame k téme teórie vypočítateľnosti a problému zastavenia.

Teória vypočítateľnosti a problém zastavenia

Naše predstavy spravidla umožňujú existenciu neriešiteľných problémov, to znamená problémov, pre ktoré nie je možné zostaviť algoritmus.

Teória výpočtovej techniky sa zaoberá takýmito problémami.

Príklady algoritmicky neriešiteľných problémov sú zastaviť problém a problém rozpoznávania liahnivosti... Pozrime sa na ne podrobnejšie.

Problém so zastavením Na základe popisu algoritmu A a vstupných údajov \ (x \) je potrebné zistiť, či sa algoritmus \ (A \) zastaví na vstupných údajoch \ (x \).

Problém zastavenia je algoritmicky neriešiteľný. Dokážme to.

\ (\ Delta \)

Nech existuje univerzálny algoritmus, ktorý rieši problém zastavenia. Uvažujme teda o triede algoritmov, ktorá spracováva texty popisujúce algoritmy.

Vzhľadom na existenciu univerzálneho algoritmu na riešenie problému zastavenia existuje algoritmus, ktorý určuje, či sa algoritmus zo spomínanej triedy zastaví na vlastnom texte alebo nie. Označme takýto algoritmus \ (B \).

Zostavme algoritmus \ (C \), ktorého vstupnými údajmi je text algoritmu \ (A \), ktorý spracováva svoj vlastný text:

Vykonajte algoritmus \ (B \) cez \ (A \).
Ak algoritmus \ (B \) určí, že \ (A \) sa zastaví na svojom texte, prejdite na krok 1. V opačnom prípade prejdite na krok 3.
Koniec algoritmu \ (C \).

Keď sme sa pokúsili použiť algoritmus \ (C \) na algoritmus \ (C \), prichádzame k zjavnému rozporu: ak sa \ (C \) zastaví vo vlastnom texte, potom sa nemôže zastaviť a naopak. Preto neexistuje žiadny \ (B \) algoritmus. \ (\ not \ Delta \)

Obecnejšou formuláciou problému zastavenia je problém definovania liahnuteľnosti.

Problém s rozpoznaním liahnutia

Nech je definovaná určitá abeceda, slová (vzorce) tejto abecedy a systém formálnych transformácií nad slovami tejto abecedy (tj. Je postavený logický počet)

Existujú v rámci tohto logického počtu pre dve slová \ (R \) a \ (S \) deduktívny reťazec vedúci z \ (R \) do \ (S \)?

V roku 1936 Alonzo Church potvrdil Cirkevnú vetu.

Cirkevná veta Problém rozpoznania dedukovateľnosti je algoritmicky neriešiteľný.

Cirkev na to dokázala formalizmus lambda kalkulu. V roku 1937, nezávisle od neho, Turing dokázal rovnakú vetu pomocou formalizmu Turingovho stroja.

Pretože všetky definície algoritmov sú navzájom ekvivalentné, existuje systém konceptov, ktorý nie je spojený so špecifickou definíciou algoritmu a funguje s týmto konceptom. vypočítateľná funkcia.

Vypočítateľná funkcia Funkcia, ktorú je možné vypočítať pomocou algoritmu.

Existujú problémy, v ktorých vzťah medzi vstupnými a výstupnými údajmi nemožno opísať pomocou algoritmu. Takými funkciami sú nevypočítateľné.

Príklad neprehliadnuteľnej funkcie

Funkciu \ (h (n) \) definovanú pre \ (\ forall n \ in \ mathbb (N) \) vezmite takto:

\ [h (n) = \ begin (prípady) 1, & \ text (ak je) \ pi \ text (existuje presná sekvencia) n \ text (9-k) \\ 0, & \ text (inak ) \ end (prípady) \]

Pre túto funkciu môžeme získať hodnotu \ (1 \), ale aby sme získali hodnotu \ (0 \), musíme skontrolovať nekonečné desatinné rozšírenie čísla \ (\ pi \), čo je evidentne nemožné v konečný čas. Táto funkcia preto nie je vypočítateľná.

Jednou z najdôležitejších otázok modernej informatiky je, či existuje formálny exekútor, pomocou ktorého je možné napodobniť akéhokoľvek formálneho exekútora. odpoveď na túto otázku získali takmer súčasne dvaja vynikajúci vedci - A. Turing a E. Post. Interpreti, ktorých navrhli, sa navzájom líšili, ale ukázalo sa, že sa môžu navzájom napodobňovať, a čo je najdôležitejšie, napodobňovať prácu akéhokoľvek formálneho interpreta.

Čo je formálny dodávateľ? Čo to znamená - jeden formálny umelec napodobňuje prácu iného formálneho interpreta? Ak ste hrali počítačové hry, predmety na obrazovke bez pochýb poslúchajú príkazy hráča. Každý objekt má množinu platných príkazov. Samotný počítač je zároveň exekútorom, a nie virtuálnym, ale skutočným. Ukazuje sa teda, že jeden formálny umelec napodobňuje prácu iného formálneho interpreta.

Zvážte, ako funguje Turingov stroj.

Turingov stroj je nekonečná páska rozdelená do buniek a vozík (čítačka a tlačiareň), ktorý sa pohybuje po páske.

Turingov stroj je teda formálne popísaný súborom dvoch abeced:

A = (a1, a2, a3, ..., an) - externá abeceda, ktorá sa používa na zaznamenávanie počiatočných údajov

Q = (q1, q2, q3, ..., qm) - interná abeceda, opisuje množinu stavov čítačky a tlačového zariadenia.

Každá bunka pásky môže obsahovať symbol z vonkajšej abecedy A = (a0, a1, ..., an) (V našom prípade A = (0, 1))

Platné činnosti Turingovho stroja sú nasledujúce:

1) napíšte ľubovoľný znak externej abecedy do bunky kazety (prepíše sa znak, ktorý tu bol predtým)

2) presuňte sa do susednej bunky

3) zmeňte stav na jeden zo stavov označených symbolom vnútornej abecedy Q

Turingov stroj je stôl poháňaný stroj.

Riadky v tabuľke zodpovedajú symbolom zvolenej abecedy A a stĺpce zodpovedajú stavom automatu Q = (q0, q1, ..., qm). Na začiatku prevádzky je Turingov stroj v stave q1. Stav q0 je konečný stav; akonáhle sa do neho automat dostane, dokončí svoju prácu.

Každá bunka tabuľky zodpovedajúca nejakému symbolu ai a nejakému stavu qj obsahuje príkaz pozostávajúci z troch častí
Postava z abecedy A
· Smer pohybu: ">" (vpravo), "<» (влево) или «.» (на месте)
Nový stav stroja

Vo vyššie uvedenej tabuľke je abeceda A = (0, 1, _) (obsahuje 3 znaky) a vnútorná abeceda Q = (q1, q2, q3, q4, q0), q0 je stav, ktorý spôsobuje, že sa vozík zastaví.

Uvažujme niekoľko úloh riešením. Turingov stroj si môžete stiahnuť na webovej stránke v sekcii.

Úloha 1. Nech A = (0, 1, _). Bunky na páske obsahujú znaky z abecedy v nasledujúcom poradí 0011011. Strieška je nad prvým znakom. Je potrebné napísať program, ktorý nahradí 0 1, 1 0 a vráti vozík do pôvodnej polohy.

Teraz definujme stavy prepravy. Hovorím im „kočiarové túžby niečo urobiť“.

q1) Vozík musí ísť doprava: ak vidí 0, zmení ho na 1 a zostane v stave q1, ak vidí 1, zmení ho na 0 a zostane v stave q1, ak vidí _, vráti 1 bunku „chce niečo iné“, to znamená, že prejde do stavu q2. Napíšte svoje úvahy do tabuľky interpreta. Syntax nájdete v pomocníkovi programu)

q2) Teraz popíšeme „prianie v kočíku“ q2. Musíme sa vrátiť do pôvodnej polohy. Ak to chcete urobiť: ak vidíme 1, nechajte ho a zostaňte v stave q2 (s rovnakou túžbou dosiahnuť koniec radu symbolov); ak vidíme 0, opustíme to a pokračujeme v pohybe doľava v stave q2; vidíme _ - je posunutá doprava o 1 bunku. Tu ste tam, kde je to potrebné vo vyhlásení o probléme. prejdeme do stavu q0.

Prácu programu si môžete pozrieť vo videu:

Problém 2. Zadaný: konečná postupnosť 0 a 1 (001101011101). Po tejto sekvencii je potrebné ich vypísať cez prázdnu bunku a v tejto sekvencii ich nahradiť číslom 0. Napríklad:

Z 001101011101 dostaneme 000000000000 1111111.

Ako vidíte, sedem je napísaných za touto sekvenciou a na ich miestach sú nuly.

Poďme k úvahám. Zistite, ktoré stavy sú potrebné na prepravu a koľko.

q1) píla 1 - opravte ju na nulu a prejdite do iného stavu q2 (zavedie sa nový stav, aby vozík v jednom priechode nezmenil všetky na nuly)

q2) nič nemeňte, presuňte sa na koniec sekvencie

q3) hneď ako striekačka uvidí prázdnu bunku, urobí krok doprava a jednu nakreslí, ak ju uvidí, potom prejde a podpíše postavu na konci. Hneď ako nakreslíme jednotku, prejdeme do stavu q4

q4) prechádzame zapísanými jednotkami bez toho, aby sme niečo zmenili. Hneď ako sa dostaneme do prázdnej bunky oddeľujúcej sekvenciu od tých, prejdeme z nového stavu q5

q5) v tomto stave ideme na začiatok sekvencie bez toho, aby sme niečo zmenili. Dostaneme sa do prázdnej cely, otočíme sa a prejdeme do stavu q1

Vozík prevezme stav q0, keď prejde v stave q1 na koniec tejto sekvencie a narazí na prázdnu bunku.

Získame nasledujúci program:

Prácu Turingovho stroja si môžete pozrieť vo videu nižšie.

Turingov stroj je zbierka nasledujúcich predmetov

1) vonkajšia 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) páska nekonečná v oboch smeroch, rozdelená do buniek, z ktorých v každom môže byť v akomkoľvek diskrétnom čase zapísaný iba jeden znak z abecedy A;
5) riadiace zariadenie, ktoré môže byť v jednom z mnohých stavov

Symbolom prázdnej bunky je 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 stav zastavenia) q 0, v ktorom sa stroj zastaví.

Ovládacie zariadenie sa môže pohybovať vľavo a vpravo pozdĺž pásky, čítať a zapisovať písmená abecedy A do buniek pásky. Ovládacie zariadenie pracuje podľa príkazov, ktoré sú nasledujúce

q i a j> a p X q k

Záznam znamená nasledovné: ak je riadiace zariadenie v stave čchi a do pozorovanej bunky je zapísané písmeno aj, potom (1) namiesto aj, ap je do bunky zapísané, (2) stroj sa prepne na zobrazenie nasledujúca pravá bunka z tej, ktorá bola práve zobrazená, ak X = P, alebo na zobrazenie ďalšej ľavej bunky, ak X = L, alebo pokračuje v skúmaní tej istej bunky pásky, ak X = C, (3) riadiace zariadenie prejde do stavu q k.

Pretože práca stroja je podľa podmienok úplne určená jeho stavom q, v tento moment a obsah bunky, ktorý je v tomto okamihu prezeraný, potom pre každú možnú konfiguráciu q i a j existuje presne jedno pravidlo. Neexistujú žiadne pravidlá iba pre konečný stav, v ktorom auto zastaví. Program Turingovho stroja s externou abecedou A = (a0, a1, ..., an) a interným Q = (q1, q2, ..., qm) preto obsahuje maximálne m (n + 1) pokynov.

Slovo v abecede A alebo v abecede Q alebo v abecede A Q je ľubovoľný sled písmen príslušnej abecedy. K-tou konfiguráciou rozumieme obraz pásky stroja s informáciami, ktoré sú na ňom vytvorené na začiatku k-tého kroku (alebo slovo v abecede A napísané na páske na začiatku k- krok), čo naznačuje, ktorá bunka sa v tomto kroku zobrazuje a v akom stave je auto. Zmysel majú iba konečné konfigurácie, t.j. tie, v ktorých sú všetky bunky pásky, s možnou 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 ako počiatočnú zvolíme akúkoľvek nefinálnu konfiguráciu Turingovho stroja, potom bude prácou stroja postupná (krok za krokom) transformácia počiatočnej konfigurácie v súlade s programom stroja, až kým sa nedosiahne konečná konfigurácia. . 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) je strojom vnímané v štandardnej polohe, ak je zapísané v po sebe nasledujúcich bunkách pásky, všetky ostatné bunky sú prázdne a stroj sa pozrie na bunku úplne vľavo alebo vpravo od buniek, v ktorých je napísané slovo b. Štandardná poloha sa nazýva počiatočná (konečná) poloha, ak je stroj, ktorý vníma slovo v štandardnej polohe, v počiatočnom stave q 1 (respektíve v stave zastavenia q 0).

Ak spracovanie slova b prevedie Turingov stroj do konečného stavu, potom sa hovorí, že je použiteľný pre b, inak nie je použiteľný pre b (stroj beží neobmedzene)

Uvažujme o príklade:

Vzhľadom na Turingov stroj s externou abecedou A = (0, 1) (tu 0 je symbol prázdnej bunky), abeceda vnútorných stavov Q = (q 0, q 1, q 2) a nasledujúci funkčný diagram (program):

q 1 0> 1 L q 2;

q 1 1> 0 C q2;

q 2 0> 0 P q 0;

q 2 1> 1 C q 1;

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

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

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

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

Pôvodné slovo 110 je teda strojom spracované 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ácií. Aby ste teda definovali Turingov stroj, musíte zadať jeho vonkajšiu a vnútornú abecedu, program a určiť, ktorý zo symbolov označuje prázdnu bunku a konečný stav.

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

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

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

Collegiate YouTube

1 / 5

✪ 09 - Úvod do algoritmov. Turingov stroj

Uring Turingov stroj - Alexander Shen

Cture Prednáška 20: Turingov stroj

Uring Turingov stroj. Ukážka práce

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

Titulky

Turingova štruktúra stroja

Stroj Turing obsahuje neobmedzené v oboch smeroch stužka(Sú možné turingove stroje, ktoré majú niekoľko nekonečných stužiek), rozdelených do buniek a ovládacie zariadenie(tiež nazývaný hlava na čítanie a zápis (GZCH)), schopný byť v jednom z množina štátov... Počet možných stavov riadiaceho zariadenia je konečný a presne špecifikovaný.

Ovládacie zariadenie sa môže pohybovať vľavo a vpravo po páske, čítať a zapisovať znaky určitej konečnej abecedy do buniek. Vyniká zvláštnosťou prázdny znak, ktorý vypĺňa všetky bunky pásky, okrem tých z nich (konečné číslo), na ktoré sú zapísané vstupné údaje.

Ovládacie zariadenie pracuje v súlade s prechodné pravidlá ktoré predstavujú algoritmus, realizovateľné tento Turingov stroj. Každé pravidlo prechodu inštruuje stroj, v závislosti od aktuálneho stavu a symbolu pozorovaného v aktuálnej bunke, aby do tejto bunky zapísali nový symbol, prepli sa do nového stavu a presunuli jednu bunku doľava alebo doprava. Niektoré stavy Turingovho stroja môžu byť označené ako terminál, a prechod na ktorýkoľvek z nich znamená koniec práce, zastavenie algoritmu.

Turingov stroj sa nazýva deterministický ak každej kombinácii stavu a symbolu pásu v tabuľke zodpovedá maximálne jedno pravidlo. Ak existuje pár „pruhovaný symbol - stav“, pre ktorý existujú 2 alebo viac pokynov, takýto Turingov stroj sa nazýva nedeterministické.

Popis Turingovho stroja

Konkrétny Turingov stroj je špecifikovaný vymenovaním prvkov zo sady písmen abecedy A, sady stavov Q a súboru pravidiel, podľa ktorých stroj funguje. Majú tvar: qiaj → q i1 a j1 dk (ak je hlava v stave qi a v sledovanej bunke je napísané písmeno aj, potom hlava prejde do stavu q i1, do bunky sa napíše j1 namiesto aj robí hlava pohyb dk, ktorý má tri možnosti: jedna bunka vľavo (L), jedna bunka vpravo (R), zostaň na mieste (N)). Pre každú možnú konfiguráciu 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 auto zastaví. Okrem toho musíte zadať stav konca a začiatku, počiatočnú konfiguráciu na páse a umiestnenie hlavy stroja.

Príklad Turingovho stroja

Uveďme príklad MT na vynásobenie čísel v unárnom číselnom systéme. Záznam pravidla „qiaj → q i1 a j1 R / L / N“ by sa mal chápať takto: qi je stav, v ktorom sa toto pravidlo vykonáva, aj sú údaje 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 presunúť.

Stroj pracuje podľa nasledujúceho súboru pravidiel:

	q 0	q 1	q 2	q 3	q 4	q 5	q 6	q 7	q 8
1	q 0 1 → q 0 1R	q 1 1 → q 2 aR	q 2 1 → q 2 1L	q 3 1 → q 4 aR	q 4 1 → q 4 1R			q 7 1 → q 2 aR
×	q 0 × → q 1 × R		q 2 × → q 3 × L		q 4 × → q 4 × R		q 6 × → q 7 × R		q 8 × → q 9 × N.
=			q 2 = → q 2 = L		q 4 = → q 4 = R			q 7 = → q 8 = L
a			q 2 a → q 2 aL	q 3 a → q 3 aL	q 4 a → q 4 aR		q 6 a → q 6 1R	q 7 a → q 7 aR	q 8 a → q 8 1L
*	q 0 * → q 0 * R			q 3 * → q 6 * R	q 4 * → q 5 1R
						q 5 → q 2 * L

Popis štátov:

Začnite
q 0	počiatočný stav. Hľadáme „x“ napravo. Po nájdení prejdeme do stavu q1
q 1	nahradíme „1“ „a“ a prejdeme do stavu q2
Preneste všetky „1“ z prvého čísla do výsledku
q 2	hľadáte „x“ vľavo. Keď sa nájde, prejdeme do stavu q3
q 3	vľavo hľadáme „1“, nahradíme ho „a“ a prejdeme do stavu q4. Ak sa „1“ skončí, nájdeme „*“ a prejdeme do stavu q6
q 4	prejdite na koniec (vpravo hľadajte „“), nahraďte „“ výrazom „1“ a prejdite na stav q5
q 5	pridajte "*" na koniec a prejdite na stav q2
Každú číslicu druhého čísla spracujeme
q 6	hľadajte „x“ napravo a choďte do stavu q7. Kým sa pozeráme, nahradíme „a“ výrazom „1“
q 7	vpravo hľadajte „1“ alebo „=“ pri hľadaní „1“ ho nahradíme „a“ a prejdeme do stavu q2 keď sa nájde „=“, prejdeme do stavu q8
Koniec
q 8	hľadáte „x“ vľavo. Keď je nájdený, prejdeme do stavu q9. Kým sa pozeráme, nahradíme „a“ výrazom „1“
q 9	stav terminálu (algoritmus zastavenia)

Násobte 3 x 2 pomocou MT v jednotkovom systéme. Protokol uvádza počiatočný a konečný stav MT, počiatočnú konfiguráciu na páse a umiestnenie hlavy stroja (podčiarknutý symbol).

Začnite. Nachádzame sa v stave q 0, zadali sme údaje do stroja: *111x11 = *, hlava stroja sa nachádza na prvom znaku *.

1. krok. Pozrime sa na tabuľku pravidiel, čo bude stroj robiť, keď je v stave q 0 a nad symbolom „*“. Toto je pravidlo z 1. stĺpca 5. riadka - q 0 * → q 0 * R. To znamená, že prejdeme do stavu q 0 (to znamená, že ho nezmeníme), zo symbolu sa stane „*“ (to znamená, že sa nezmení) a pohybujeme sa pozdĺž textu, ktorý sme zadali „*111x11 =*“ napravo o jednu pozíciu (R), potom je na 1. znak 1. Stav q 0 1 (1. stĺpec 1. riadok) je zase spracovaný pravidlom q 0 1 → q 0 1R. To znamená, že opäť dochádza jednoducho k prechodu doprava o 1 pozíciu. Stáva sa to, kým nestojíme pri symbole „x“. A tak ďalej: vezmeme 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é, multiplikačný algoritmus je nasledujúci: označíme 1. jednotku 2. faktora, nahradíme ho písmenom „a“ a celý 1. faktor prenesieme za znamienko rovnosti. Prenos sa vykonáva striedaním nahradením jednotiek 1. faktora „a“ a pripočítaním rovnakého počtu jednotiek na koniec riadka (vľavo od pravého „*“). Potom zmeníme všetky „a“ na znamienko násobenia „x“ späť na jedničky. A cyklus sa opakuje. Koniec koncov, A vynásobené B môže byť reprezentované ako A + A + A B krát. 2. jednotku 2. faktora teraz označíme písmenom „a“ a jednotky opäť prenesieme. Ak pred znamienkom „=“ nie sú žiadne jednotky, násobenie je dokončené.

Turingova úplnosť

Môžeme povedať, že Turingov stroj je najjednoduchší počítač s lineárnou pamäťou, ktorý podľa formálnych pravidiel transformuje vstupné údaje pomocou postupnosti elementárne akcie.

Elementárna povaha akcií spočíva v tom, že akcia zmení iba malý kúsok údajov 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 je možné ho použiť na výpočet všetkého, čo je možné vypočítať na akomkoľvek inom počítači, ktorý vykonáva výpočty pomocou postupnosti elementárnych akcií. Táto vlastnosť sa nazýva úplnosť.

Jeden z prirodzených spôsobov, ako dokázať, že výpočtové algoritmy, ktoré je možné implementovať na jednom počítači, je možné implementovať na inom počítači, je napodobniť prvý stroj na druhom.

Imitácia je nasledovná. Pri vchode do druhého automatu je uvedený popis programu (pravidlá prevádzky) prvého stroja D (\ Displaystyle D) a vstupné údaje X (\ Displaystyle X), ktoré mali doraziť k vchodu prvého auta. Je potrebné popísať taký program (pravidlá prevádzky druhého stroja), aby v dôsledku výpočtov bol výstup rovnaký, ako keby sa prvý stroj vrátil, ak by ako vstup prijal údaje X (\ Displaystyle X).

Ako bolo povedané, na Turingovom stroji je možné simulovať (nastavením pravidiel prechodu) všetkých ostatných vykonávateľov, 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.

Na Turingovom stroji môžete napodobniť poštový stroj, bežné Markovove algoritmy a akýkoľvek program pre bežné počítače, ktorý pomocou nejakého algoritmu prevádza vstupné údaje na výstupy. Na druhej strane je možné Turingov stroj napodobniť na rôznych abstraktných interpretoch. Pozývajú sa interpreti, pre ktorých je to možné Turing dokončený(Turing dokončený).

Existujú programy pre bežné počítače, ktoré simulujú činnosť Turingovho stroja. Je však potrebné poznamenať, že táto imitácia je neúplná, pretože v Turingovom stroji je abstraktná nekonečná páska. Nekonečnú pásku s údajmi nie je možné ú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é, ale napriek tomu sú vždy konečné).

Varianty turingovho stroja

Model stroja Turing je predĺžiteľný. Môžeme uvažovať o Turingových strojoch s ľubovoľným počtom pások a viacrozmerných páskach s rôznymi obmedzeniami. Všetky tieto stroje sú však Turingove kompletné a sú modelované konvenčným Turingovým strojom.

Turingov stroj bežiaci na napoly nekonečnom páse

Ako príklad takéhoto zníženia uveďme nasledujúcu vetu: Pre každý Turingov stroj existuje ekvivalentný Turingov stroj fungujúci na polovičnej nekonečnej páske (to znamená na páske, ktorá je nekonečná v jednom smere).

Zamyslite sa nad dôkazom, ktorý predložil Yu G. Karpov v knihe Teória automatov. Dôkaz tejto vety je konštruktívny, to znamená, že poskytneme algoritmus, pomocou ktorého je možné skonštruovať ekvivalentný Turingov stroj s deklarovanou vlastnosťou pre akýkoľvek Turingov stroj. Najprv svojvoľne očíslujeme bunky pracovnej pásky MT, to znamená, že definujeme nové umiestnenie informácií na páske:

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

Nakoniec zmeníme Turingov stroj zdvojnásobením počtu jeho stavov a zmeníme posun čítacej a zapisovacej hlavy tak, aby v jednej skupine stavov bola prevádzka stroja ekvivalentná prevádzke v tieňovanej oblasti a v druhej skupine stavov. stroj by fungoval ako pôvodný stroj. v netienenej oblasti. Ak sa počas prevádzky MT vyskytne symbol „*“, hlava na čítanie a zápis dosiahla hranicu zóny:

Počiatočný stav nového Turingovho stroja je nastavený v jednej alebo druhej zóne podľa toho, ktorá časť pôvodnej pásky bola v pôvodnej konfigurácii čítacou a zapisovacou hlavou. Je zrejmé, že vľ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, Turingove stroje, gramatiky, nakreslí automatový graf