{{TOC float}}
{{Sources|
''Tohle je poněkud obšírnější výcuc ke [[Státnice|státnicovým okruhům]] z [[Státnice_-_Informatika_-_Vyčíslitelnost|vyčíslitelnosti]] pro obory [[Státnice_-_Informatika_-_I3:_Matematická_lingvistika|Matematická lingvistika]] a [[Státnice_-_Informatika_-_I2:_Softwarové_systémy|Softwarové systémy]], pocházející ze [http://ladislav.strojil.cz/ Strojilových skript], papírových zápisků [http://atrey.karlin.mff.cuni.cz/~alexak/ A. Kazdy] a zápisků z předmětu [[Vyčíslitelnost I]] ze [[Studnice vědomostí|Studnice]] -- [[User:Tuetschek|Tuetschek]] 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}}
