{{TOC float}}
{{Sources| Tohle je poněkud obšírnější výcuc ke z pro obory a , pocházející ze Strojilových skript, papírových zápisků A. Kazdy a zápisků z předmětu Vyčíslitelnost I ze -- 14:01, 17 Aug 2010 (CEST)
}}
Turingovy stroje
Definice (Turingův stroj)
Deterministický Turingův stroj (DTS) <math> M\,\!</math> s <math> k\,\!</math>-páskami, kde <math> k\,\!</math> je konstanta, je pětice
:<math> M=(Q,\Sigma,\delta,q_0,F) \,\!</math>
<math> Q = \,\!</math> konečná množina stavů řídící jednotky
<math> \Sigma = \,\!</math> konečná pásková abeceda
<math> \delta: (Q\backslash F) \times \Sigma^k \mapsto Q \times \Sigma^{k} \times \{L,N,R\}^k \,\!</math> je přechodová funkce (částečná)
<math> q_0 \in Q = \,\!</math> počáteční stav
<math> F \subseteq Q = \,\!</math> množina přijímajících stavů
Definice (Konfigurace TS/Postovo slovo)
Konfigurace (jednopáskového) TS, neboli Postovo slovo, je obsah nejmenší souvislé části pásky, která obsahuje všechna neprázdná a čtené políčko; poloha hlavy a stav. Zapisujeme:
:<math>UqsV\,\!</math>
kde <math> U, V\,\!</math> jsou části pásky nalevo a napravo od hlavy, <math> q\,\!</math> je stav a <math> s\,\!</math> čtené políčko.
Poznámka (Kombinování TS)
Spojení dvou TS: napřed počítá <math> M1\,\!</math>, na výsledek pustím <math> M2\,\!</math>, tj. <math> M1 \wedge M2\,\!</math>
Větvení (if-then-else): ve stroji <math> M1\,\!</math> ze stavu <math> q_0\,\!</math> přechod do (poč. stavu) <math> M2\,\!</math>, z <math> q_1\,\!</math> do <math> M3\,\!</math>
While-cyklus: složené spojení a větvení
Nutná opatrnost -- stejná vnější abeceda, disjunktní vnitřní stavy atd.
Poznámka (Modifikace a omezení (stručně))
Omezení pohybu na jeden směr -- síla stroje klesne na úroveň konečných automatů
Omezení na povinný pohyb (L/P) -- OK
Jen jedna činnost v taktu (buď zápis, nebo posuv) -- OK
Jednostranně omezená páska, více pásek, více hlav -- stále stejná síla
Okraje pásky z obou stran -- páska není nekonečná, mám jen konfiguraci stroje -- můžu mít potřebu pásku zvětšovat a zmenšovat (je možné)
Omezení na 2 aktivní stavy -- OK (jeden ale nestačí)
Omezení na 2 symboly abecedy -- OK (z toho jedno je "blank")
K simulaci TS stačí 2 zásobníkové automaty -- z jednoho zásobníku uděláme obsah pásky nalevo, z druhého napravo (vč. čteného znaku) a přehazujeme znaky.
Univerzální Turingův stroj
Věta (Univ. Turingův stroj)
Máme dánu abecedu <math> A\,\!</math>. Existuje univerzální TS <math> \mathcal{U}\,\!</math> nad <math> A\,\!</math>, který pro každý TS nad <math> A\,\!</math> simuluje výpočet.
:<math>\mathcal{U}(\mathrm{k\acute{o}d}(T) + \mathrm{k\acute{o}d}(S))\simeq T(S)\,\!</math>
Důkaz
Vezmeme <math> A=\{\lambda, |\}\,\!</math>, což stačí. BÚNO má každý TS jediný koncový stav <math> q_f\,\!</math>, počáteční stav buď <math> q_s\,\!</math>. Počet stavů -- <math> m\,\!</math> -- může být velký. Kód stavu <math> q_i\,\!</math> budiž blok znaků délky <math> m+2\,\!</math> (<math> |\,\!</math> + <math> i\,\!</math>-krát <math> |\,\!</math> + <math> m-i\,\!</math>-krát <math> \lambda\,\!</math> + <math> \lambda\,\!</math>).
Pro <math> i\geq 1\,\!</math> máme vždy dvě instrukce (jedna pro <math> \lambda\,\!</math>, druhá pro <math> |\,\!</math>). Ty se dají zakódovat do bloku <math> \times O_1\times O_2\times O_3\dots \times O_m\times \,\!</math>, kde <math> \times \,\!</math> je pomocný symbol (v abecedě <math> \mathcal{U}\,\!</math> být může) a <math> O_i\,\!</math> jsou kódy obou instrukcí pro stav <math> r_i\,\!</math> -- kód zapisovaného písmene, pohybu a cílového stavu.
Páska <math> \mathcal{U}\,\!</math> pak vypadá následovně:<center><math>Y[\mbox{blok1}]Y[\mbox{blok2}]\Delta[\mbox{blok3}] \times O_1\times O_2\dots \times O_m\times\,\!</math></center>
"blok1" je konfigurace pův. stroje, jen obsah právě čteného pole je nahrazen pomocným symbolem <math> M\,\!</math>.
"blok2" kóduje aktuální stav pův. stroje.
"blok3" je jedna buňka, v níž je uložen obsah právě čteného pole.
Univerzální stroj potom sestává z testu bloku2, zda obsahuje koncový stav, procedury vyčištění pásky a vydání výsledku a odsimulování jednoho kroku práce původního stroje
Simulace:
najít relevantní blok <math> O_i\,\!</math> -- stav <math> i\,\!</math> si nelze pamatovat přímo, proto musím z bloku 2 postupně umazávat <math> |\,\!</math> a posouvat nějaký spec. symbol "zarážku" doprava
posunout zarážku na konkrétní instrukci podle bloku3 (čteného znaku)
provést instrukci (po kouskách přenést nový stav do bloku 2, pak 6 možností zapisování písmene a pohybu, při pohybu a mazání pozor na okraje pásky)
Důsledek
Díky tomu lze všechny TS očíslovat.
Věta (Halting problém)
Halting problém není algoritmicky rozhodnutelný.
Důkaz
Sporem nechť máme TS <math> H(T,K)\,\!</math> rozhodující, zda se TS <math> T\,\!</math> zastaví nad daty <math> K\,\!</math> (a <math> H\,\!</math> se zastaví vždy a vydá buď 0 nebo 1). Potom lze vyrobit <math> Alg(K)\,\!</math> takový, že <math> Alg(K)\,\!</math> se zastaví, právě když <math> \mathcal{U}(K + K)\,\!</math> se nezastaví (pomocí <math> H\,\!</math>). Pak <math> Alg(K)\,\!</math> má nějaký kód, nazveme jej <math> Q\,\!</math>. Pak ale
:<math>Alg(Q)\mbox{ zastavi}\Leftrightarrow \mathcal{U}(Q + Q)\mbox{ nezastavi} \Leftrightarrow Alg(Q)\mbox{ nezastavi}\,\!</math>
a to je spor.
Poznámka (Silně a slabě omezené mazání)
Omezíme mazání v TS:
slabě -- máme spec. symbol "kaňka" (<math> *\,\!</math>) a pravidla:
<math>\lambda \to \mbox{cokoliv} </math>
<math>\mbox{cokoliv}\neq \lambda \to *\,\!</math>
silně -- máme abecedu jen <math> \{\lambda,*\}\,\!</math> a povolený jen přepis <math> \lambda\to *\,\!</math>.
Oba dva případy mají stejnou sílu jako běžný TS (silné se slabým dá simulovat: kaňku kódovat jako blok samých kaněk, převést abecedu; normální TS se dá simulovat slabým postupným překreslováním konfigurací vedle sebe na pásku se současným měněním stavu).
Lze algoritmicky rozhodnout, zda TS <math> T\,\!</math> s konfigurací <math> K\,\!</math> někdy přepíše <math> \lambda\,\!</math> na něco jiného (existuje horní odhad počtu kroků v popsané části pásky). Nelze ale rozhodnout, zda TS <math> T\,\!</math> s konfigurací <math> K\,\!</math> někdy přepíše ne-<math> \lambda\,\!</math> na <math> \lambda\,\!</math> -- to je ekvivalentní Halting problému (<math> T\,\!</math> simulujme silně omezeným <math> T_1\,\!</math> a přidejme <math> T_2\,\!</math>, který smaže 1 kaňku. Pokud se <math> T_1T_2\,\!</math> zastaví, musel se zastavit i <math> T_1\,\!</math> a tím bychom rozhodli zastavení <math> T\,\!</math>).
{{Statnice I3}}