{{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:

  1. 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

  2. posunout zarážku na konkrétní instrukci podle bloku3 (čteného znaku)

  3. 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}}