Skip to content
Snippets Groups Projects
Select Git revision
  • 4ca5da364c26e388342237bb2eaa7497cf37a535
  • master default
2 results

recursive.tex

Blame
  • recursive.tex 52.87 KiB
    \ifx\chapter\undefined
    \input adsmac.tex
    \singlechapter{3}
    \fi
    
    \def\LL{\hbox{\tt <}}
    \def\RR{\hbox{\tt >}}
    
    \chapter[rl]{Rozhodnutelné jazyky}
    
    Počátkem 20. století se matematici zabývali otázkami \uv{mechanické}
    řešitelnosti různých problémů -- kořeny celočíselných polynomiálních rovnic,
    dokazatelnost tvrzení v~logice apod. Zásadním problémem se ale ukázala sama
    definice mechanického výpočtu. Podali ji až ve 30. letech Alonzo Church
    ($\lambda$-kalkulus), Stephen Kleene (kalkulus rekurzivních funkcí) a Alan
    Turing (stroj s~páskou). Právě Turingovou definicí výpočtu se nyní budeme
    zabývat. Ostatní modely výpočtu jsou s~Turingovým strojem ekvivalentní,
    alespoň co se týče toho, na jaké otázky dovedou odpovídat.
    
    \section[tm]{Turingovy stroje}
    
    Turingův stroj je motivovaný představou matematika, který má k~dispozici
    tabuli a svou mysl. Zatímco tabule je potenciálně nekonečně velká, do mysli
    se vejde pouze konečné množství informací.
    
    Tabuli budeme modelovat oboustranně nekonečnou \em{páskou} rozdělenou na \em{políčka.}
    Na každém políčku se vyskytuje jeden znak z~konečné abecedy.
    Po pásce se pohybuje \em{hlava} stroje, která se vždy dívá na jedno políčko a umí znak z~tohoto
    políčka přečíst, přepsat na jiný a posunout se o~jedno políčko doleva nebo
    doprava.
    
    Matematikovu mysl si budeme představovat jako \em{řídicí jednotku} stroje, která
    se v~každém okamžiku nachází v~jednom z~konečně mnoha \em{stavů} (stejně jako
    konečný automat). V~každém kroku výpočtu se jednotka podle svého stavu a znaku,
    který přečte hlava, rozhodne, jakou instrukci stroje provést. Instrukce určí,
    jaký znak na aktuální políčko pásky zapsat, do jakého stavu řídicí jednotky
    se přepnout a~zda se hlava posune doleva nebo doprava, případně zůstane na místě.
    Rozhodování řídicí jednotky popíšeme \em{přechodovou funkcí.}
    
    Na počátku výpočtu je na pásce napsán vstup, zbývající políčka pásky jsou
    vyplněna speciálním symbolem~\sp{} (\em{mezera}). Hlava se dívá na první znak
    vstupu. Řídicí jednotka se nachází v~počátečním stavu~$q_0$.
    
    Výpočet končí tím, že se řídicí jednotka přepne do jednoho z~\em{koncových stavů.}
    Ty jsou dva ($q_+$ a~$q_-$). Jeden odpovídá přijetí vstupu, druhý jeho odmítnutí.
    
    Nyní stroj a jeho výpočet nadefinujeme podobně, jako jsme to udělali u~konečných
    automatů.
    
    \defn{\em{Turingův stroj} (Turing Machine, zkráceně TM) se skládá z~následujících částí:
    \list{o}
    \:$Q$ je konečná neprázdná množina \em{stavů} stroje,
    \:$q_0\in Q$ je \em{počáteční stav,}
    \:$q_+,q_-\in Q$ jsou \em{koncové stavy: přijímací a odmítací} ($q_0$, $q_+$, $q_-$ navzájem různé),
    \:$\Sigma$ je konečná neprázdná \em{vstupní abeceda} (v~ní je zadán vstup),
    \:$\Gamma\supset\Sigma$ je konečná \em{pracovní abeceda} znaků používaných na pásce,
    \:$\sp\in\Gamma\setminus\Sigma$ je znak pro \em{mezeru,}
    \:$\delta: (Q\setminus\{q_+,q_-\}) \times \Gamma \rightarrow Q\times \Gamma\times \{\leftarrow,\bullet,\rightarrow\}$
      je \em{přechodová funkce.}
    \endlist
    }
    
    \defn{\em{Konfigurace} Turingova stroje je uspořádaná trojice $(s,\pi,i)$, kde:
    \list{o}
    \:$s\in Q$ je stav stroje.
    \:$\pi$~obsah pásky popsaný funkcí z~nějakého intervalu $\{\ell,\ell+1,\ldots,r\}$
    celých čísel do~$\Gamma$ -- chová se tedy jako řetězec, ale je indexovaný celými čísly,
    přičemž index~0 odpovídá počátečnímu políčku pásky. Interval od~$\ell$ do~$r$ obsahuje
    právě právě ta políčka, jež hlava dosud navštívila. Na všech ostatních políčkách jsou
    mezery.
    \:$i$ je index políčka pásky, na němž stojí hlava stroje.
    \endlist
    }
    
    \defn{\em{Následník} konfigurace $(s,\pi,i)$ je konfigurace $(s',\pi',i')$,
    do níž stroj přejde jedním \em{krokem.} Definujeme ji takto:
    \list{o}
    \:Podle $\delta(s,\pi[i])$ zjistíme, jakou instrukci $(s',x',\<pohyb>)$
      má stroj vykonat.
    \:Zapíšeme znak~$x'$ na pásku: položíme $\pi'=\pi$ všude kromě $\pi'[i]=x'$.
    \:Posuneme hlavu:
    	\list{o}
    	\:Pokud $\<pohyb>=\bullet$, položíme $i'=i$.
    	\:Pokud $\<pohyb>=\rightarrow$, položíme $i'=i+1$.
    	\:Pokud $\<pohyb>=\leftarrow$, položíme $i'=i-1$.
    	\endlist
    \:Není-li $\pi'[i']$ dosud definované, položíme $\pi'[i']=\sp$.
    \endlist
    }
    
    \defn{\em{Výpočet stroje} pro vstup $\alpha\in\Sigma^*$ je konečná nebo
    nekonečná posloupnost konfigurací $K_0,K_1,K_2,\ldots$, kde $K_0$ je počáteční
    konfigurace $(q_0, \alpha, 0)$ s~dodefinovaným $\alpha[0]=\sp$, pokud~$\alpha$
    byla prázdná. Dále pro všechna $i$~platí, že $K_{i+1}$ je následníkem~$K_i$.
    Je-li výpočet konečný, poslední konfigurace obsahuje jeden z~koncových stavů
    stroje. V~žádné jiné konfiguraci se koncový stav nevyskytuje.
    }
    
    Výpočet je jednoznačně určen vstupem stroje. Buďto je konečný a stroj \em{se zastaví,}
    nebo je nekonečný a stroj \em{diverguje.} Možnost divergence stroje způsobuje,
    že jazyk rozpoznávaný strojem můžeme definovat dvěma způsoby:
    
    \defn{Stroj \em{přijme} slovo~$\alpha\in\Sigma^*$, pokud se jeho výpočet se vstupem~$\alpha$
    zastaví ve stavu~$q_+$. Slovo \em{odmítne,} pokud se zastaví v~$q_-$. Jestliže se stroj nezastaví,
    vstup ani nepřijme, ani neodmítne.
    Množině slov přijímaných strojem~$M$ říkáme \em{jazyk přijímaný strojem~$M$} a~značíme ho $L(M)$.
    }
    
    \defn{Jazyk $L$ je \em{částečně rozhodnutelný} neboli \em{rekurzivně spočetný,}
    pokud existuje Turingův stroj přijímající jazyk~$L$. Třídu všech takových jazyků
    značíme~$\cc{RE}$.\foot{Terminologie je zde trochu zavádějící. Nejde o~rekurzi v~dnešním
    obvyklém smyslu, nýbrž o~Kleeneho kalkulus rekurzivních funkcí. Rekurzivně spočetné
    jsou anglicky \em{recursively enumerable,} což znamená spíš rekurzivně vyjmenovatelné.
    Tento vztah dále zkoumáme v~cvičení \exref{recenum}.
    }}
    
    \defn{Stroj \em{rozhoduje} jazyk~$L$, pokud přijímá jazyk~$L$ a navíc se
    pro každý vstup $\alpha\in\Sigma^*$ zastaví.
    (Pro každé slovo~$\alpha$ tedy výpočet skončí ve stavu~$q_+$, pokud
    $\alpha\in L$, a~jinak skončí v~$q_-$.)
    }
    
    \defn{Jazyk $L$ je \em{rozhodnutelný} neboli \em{rekurzivní,}
    pokud existuje Turingův stroj rozhodující jazyk~$L$. Třídu všech takových jazyků
    značíme~$\cc{R}$.
    }
    
    \note{Zjevně je $\cc{R}\subseteq\cc{RE}$. Časem dokážeme, že inkluze je ostrá, a~také prozkoumáme vztahy
    s~třídami jazyků z~předchozích kapitol.
    }
    
    Turingův stroj můžeme také použit k~výpočtu funkcí:
    
    \defn{Funkce~$f: \Sigma^* \rightarrow \Sigma^*$ je \em{vyčíslitelná} neboli \em{rekurzivní,}
    pokud existuje Turingův stroj, který se pro každé $\alpha\in\Sigma^*$ zastaví a vydá výstup
    $f(\alpha)$. \em{Výstupem} stroje myslíme obsah pásky~$\pi$ z~poslední konfigurace výpočtu
    po odstranění mezer zleva i zprava. Požadujeme, aby výstup byl tvořen jen znaky z~abecedy~$\Sigma$.
    }
    
    \defn{Funkce~$f: \Sigma^* \rightarrow \Sigma^* \cup \{\uparrow\}$ je \em{částečně vyčíslitelná}
    neboli \em{částečně rekurzivní,} pokud existuje stroj, který se pro vstup~$\alpha\in\Sigma^*$
    zastaví právě tehdy, když $f(\alpha)\ne\mathord\uparrow$, a~pokud se zastaví, je jeho výstupem $f(\alpha)$.
    }
    
    \obs{Jazyk~$L$ je rozhodnutelný právě tehdy, když je vyčíslitelná jeho charakteristická funkce.
    Jazyk~$L$ je částečně rozhodnutelný právě tehdy, když je částečně vyčíslitelná funkce $f: f(\alpha)={\tt 1}$
    pro $\alpha\in L$ a $f(\alpha)=\mathord\uparrow$ pro $\alpha\not\in L$.
    }
    
    \example{Sestrojíme Turingův stroj rozhodující jazyk $\{ \0^n\1^n \mid n\in\N \}$.
    Stroj bude opakovaně odebírat znak~$\0$ ze začátku slova a $\1$ z~konce slova. Pokud se tím
    podaří slovo vyprázdnit, stroj přijme. Pokud odebírání selže (na začátku nenajde~$\0$ nebo
    na konci~$\1$), stroj odmítne.
    
    Stroj bude mít vstupní abecedu $\Sigma=\{\0,\1\}$, pracovní abecedu $\Gamma=\{\0,\1,\sp\}$,
    množinu stavů $Q=\{q_0,q_+,q_-,r,j,\ell\}$ a~přechodovou funkci definovanou tabulkou na obrázku \figref{tmanbn}.
    }
    
    \texfigure[tmanbn]{
    	\vbox{\halign{\hfil$#$\hfil&&\qquad\hfil$#$\hfil\cr
    		\omit\em{stav/znak}\hfil
    			& \0			& \1			& \sp			\cr
    		\noalign{\smallskip\hrule\smallskip}
    		q_0	& (r,\sp,\rightarrow)	& q_-			& q_+			\cr
    		r	& (r,\0,\rightarrow)	& (r,\1,\rightarrow)	& (j,\sp,\leftarrow)	\cr
    		j	& q_-			& (\ell,\sp,\leftarrow)	& q_-			\cr
    		\ell	& (\ell,\0,\leftarrow)	& (\ell,\1,\leftarrow)	& (q_0,\sp,\rightarrow)	\cr
    	}}
    }{Turingův stroj rozhodující jazyk $\{\0^n\1^n\mid n\in\N\}$.
    Tam, kde přecházíme do stavu $q_+$ nebo~$q_-$, nezáleží na novém znaku ani pohybu hlavy.}
    
    Na rozdíl od konečných automatů mohou být různé TM pro tentýž vstup rozdílně rychlé
    (některé se ani nemusí zastavit). Hodí se proto umět efektivitu stroje měřit:
    
    \defn{\em{Čas výpočtu} definujeme jako počet konfigurací, kterými výpočet stroje projde.
    \em{Prostor výpočtu} je počet políček pásky, která během výpočtu navštívila hlava stroje.
    }
    
    \defn{\em{Časová složitost} stroje je funkce, která každé délce vstupu~$n$ přiřadí
    maximální čas výpočtu pro vstupy z~$\Sigma^n$. Podobně prostorová složitost
    přiřadí délce vstupu maximální prostor výpočtu. Pokud se některý výpočet
    nezastaví, časová složitost bude nekonečná a prostorová možná také.}
    
    \examplen{proměnné ve stavu}{Často se hodí, aby si stroj pamatoval několik
    \uv{proměnných}. Pokud mají omezený rozsah, můžeme je všechny zakódovat do stavu
    stroje: stav bude uspořádaná $k$-tice, jejíž složky budou odpovídat hodnotám
    jednotlivých proměnných.
    }
    
    \examplen{vícestopá paska}{Podobně můžeme na jedno políčko pásky uložit několik
    různých druhů informací, když jako znaky pracovní abecedy použijeme uspořádané
    $\ell$-tice. Můžeme si to představit jako \em{$\ell$-stopou pásku,} jejíž stopy
    používáme nezávisle. Všechny stopy ovšem sdílí polohu hlavy. Pozor na to, že na
    začátku výpočtu musíme překódovat vstupní abecedu do $\ell$-tic, a~na konci
    zase $\ell$-tice výstupu dekódovat.
    }
    
    \exercises
    
    \excmt{Sestrojte Turingovy stroje řešící následující úlohy. Pokaždé stanovte
    jejich časovou a prostorovou složitost.}
    
    \ex{Rozhodnout jazyk všech slov nad abecedou $\{\0,\1\}$, v~nichž je stejně nul jako jedniček.}
    
    \ex{K~zadanému řetězci~$\alpha$ spočítat jeho otočení~$\alpha\rev$.}
    
    \ex{Rozhodnout jazyk všech závorkování z~cvičení \exref{zavorky}.}
    
    \ex{Pro slovo $\0^n$ spočítat zápis čísla~$n$ ve dvojkové soustavě.}
    
    \ex{Pro číslo~$n$ zapsané ve dvojkové soustavě vytvořit slovo $\0^n$.}
    
    \ex{Rozhodnout jazyk $\|a|^n\|b|^n\|c|^n$.}
    
    \ex{Sečíst, odečíst nebo vynásobit dvě přirozená čísla zapsaná ve dvojkové soustavě.}
    
    \endexercises
    
    \section[tmvariants]{Varianty Turingových strojů}
    
    Výhodou definice Turingova stroje je, že se snadno upravuje, čímž vznikají
    další druhy strojů.
    
    \subsection{Konečné automaty}
    
    Uvažujme stroj, jehož instrukce používají pouze pohyb doprava.
    Navíc přečte-li stroj mezeru, přejde vždy do stavu $q_+$ nebo~$q_-$.
    Takové stroje jsou zjevně ekvivalentní s~konečnými automaty, takže
    rozhodují právě regulární jazyky.
    
    \subsection{Obousměrné automaty}
    
    \em{Obousměrný konečný automat} je Turingův stroj, který má zakázáno
    měnit obsah pásky -- instrukce tedy musí vždy zapsat ten symbol, který byl
    z~pásky přečten. Vstup je navíc stroji dodán ohraničený: pro vstup~$\alpha$
    je počátečním obsahem pásky slovo $\|<|\alpha\|>|$, kde \|<| a~\|>| jsou
    znaky pracovní abecedy zvané \em{zarážky.} Hlava začíná na prvním znaku
    slova~$\alpha$. Pokud stroj narazí na~zarážku~\|<|, nesmí vykonat pohyb
    doleva; pokud narazí na~\|>|, nesmí jít doprava.
    
    Obousměrné automaty se tedy mohou po vstupu libovolně pohybovat, ale nesmí
    ho měnit. Na rozdíl od obyčejných automatů mohou divergovat.
    Překvapivě opět rozhodují jenom regulární jazyky (toto tvrzení dokážeme
    v~oddílu \secref{tfa}).
    
    \subsection{Vícepáskové stroje}
    
    Zajímavější je vybavit Turingův stroj více páskami. Mějme tedy $k$ oboustranně
    nekonečných pásek. Každá má svou vlastní hlavu, která se pohybuje
    nezávisle na ostatních hlavách. Přechodová funkce se rozhoduje podle
    stavu a symbolů přečtených všemi $k$~hlavami. Instrukce stroje zapíše znaky
    na všech $k$ pásek a každé hlavě řekne, kam se má pohnout. Přechodová funkce
    tedy vede z~$Q\times\Gamma^k$ do $Q\times\Gamma^k\times\{\leftarrow,\bullet,\rightarrow\}^k$.
    
    Konfigurace stroje se skládá ze stavu řídicí jednotky a obsahů všech pásek; každou
    pásku opět rozdělíme na část nalevo a napravo od příslušné hlavy. Krok stroje a výpočet
    se rozšíří zjevným způsobem.
    
    Při spuštění stroje je vstup napsán na první pásce. Pokud stroj vrací výstup,
    napíše ho opět na první pásku.
    
    Někdy se také určuje speciální vstupní a výstupní páska:
    
    \list{o}
    \:\em{Vstupní pásku} je povoleno pouze číst (stroj tedy musí zapsat ten znak, který právě přečetl).
    Navíc hlava nesmí opustit bezprostřední okolí vstupu. To obvykle řešíme ohraničením vstupu
    zarážkami a požadavkem, aby přechodová funkce na levé zarážce nepředepsala pohyb doleva,
    ani na pravé zarážce pohyb doprava.
    
    \:Na \em{výstupní pásku} je povoleno pouze zapisovat (přechodová funkce musí pro všechny možné znaky
    z~této pásky vracet stejnou instrukci). Navíc se po ní hlava musí posunout doprava, pokud zapsala
    nemezerový znak, a~jinak musí zůstat na místě.
    
    \:Ostatním páskám se říká \em{pracovní} a do využitého prostoru počítáme jenom je.
    \endlist
    
    \theorem{Vícepáskový stroj je možné převést na jednopáskový, který přijímá/rozhoduje
    tentýž jazyk a vyčísluje tutéž funkci.
    }
    
    \proofsketch
    Budeme $k$-páskový stroj simulovat jednopáskovým strojem, jehož pásku rozdělíme na $2k$ stop.
    Stopy budou tvořit $k$~párů. Každý pár bude odpovídat jedné pásce simulovaného stroje
    a bude v~něm \em{datová stopa} s~obsahem pásky a \em{řídicí stopa}, v~níž bude vyznačena
    pozice hlavy simulovaného stroje. Stav simulovaného stroje si budeme pamatovat ve stavu
    nového stroje.
    
    Na začátku výpočtu překódujeme vstup do $2k$-stopé abecedy, vyznačíme počáteční polohy všech hlav
    a přejdeme do počátečního stavu simulovaného stroje.
    
    Jeden krok stroje odsimulujeme takto: Nejprve projdeme celou pásku zleva doprava a kdykoliv
    v~nějaké řídicí stopě najdeme značku polohy hlavy, zapamatujeme si ve stavu znak z~příslušné
    datové stopy. Po přečtení všech $k$ znaků vyhodnotíme přechodovou funkci (bude zakódovaná
    do naší přechodové funkce), zjistíme, jakou instrukci máme vykonat, a~zapamatujeme si to ve stavu.
    Pak znovu projdeme celou pásku a kdykoliv narazíme v~řídicí stopě na značku
    hlavy, zapíšeme do odpovídající datové stopy nový znak a posuneme značku hlavy
    správným směrem. Nakonec se přepneme do nového stavu simulovaného stroje.
    
    Na konci výpočtu dekódujeme obsah pásky z~$2k$-stopé abecedy do původní.
    
    Zbývá dořešit jeden problém: jak při procházení celé pásky poznat, kde začíná a končí.
    Mohli bychom si v~další stopě udržovat zarážky na začátku/konci využitého úseku pásky
    a podle potřeby je posouvat. Ale jednodušší je pamatovat si ve stavu stroje, kolik simulovaných
    hlav zrovna leží nalevo od aktuální pozice na pásce.
    \qed
    
    \subsection{Nedeterministické stroje}
    
    Podobně jako jsme zavedli nedeterministický konečný automat, můžeme definovat nedeterministickou
    verzi Turingova stroje. Jeho přechodová funkce bude místo jedné instrukce přiřazovat množinu
    instrukcí. Jeden krok výpočtu tedy může pro jednu konfiguraci určit více možných následníků
    (relace následníka již není funkce).
    Pro jeden vstup pak může existovat mnoho různých výpočtů, dokonce některé konečné a jiné nekonečné.
    
    Stroj přijme slovo, pokud se alespoň jeden z~možných výpočtů zastaví v~přijímacím stavu.
    Později dokážeme, že nedeterministické stroje přijímají tytéž jazyky jako deterministické stroje.
    
    Výpočty nedeterministického stroje můžeme popsat stromem konfigurací: v~kořeni
    je počáteční konfigurace, potomci každé konfigurace jsou ty, do kterých se dá dostat
    jedním krokem výpočtu. Listy stromu odpovídají zastavení výpočtu v~koncovém stavu,
    ale strom může mít i nekonečné větve.
    
    Dodejme, že počet možností v~jednom kroku výpočtu můžeme omezit na dvě za cenu zpomalení výpočtu
    konstanta-krát.
    
    \subsection{Randomizované stroje}
    
    Stroj můžeme vybavit generátorem náhodných bitů. Pořídíme mu \em{náhodnou pásku,} která bude
    na začátku výpočtu obsahovat nekonečnou posloupnost nezávislých náhodných bitů.
    Po této pásce bude povoleno pohybovat se pouze doprava.
    
    Podobné jako u~nedeterministických strojů není ani zde výpočet jednoznačně
    určen: k~jedné konfiguraci mohou existovat dvě následující a možné výpočty
    můžeme popsat stromem. Každému výpočtu
    pak můžeme přiřadit pravděpodobnost toho, že bude proveden (to je $2^{-t}$, kde $t$ je
    počet přečtených náhodných bitů). Sečtením všech přijímajících výpočtů pak můžeme
    stanovit pravděpodobnost přijetí slova.
    
    \subsection{Stroje s~orákulem}
    
    Schopnosti stroje můžeme rozšířit o~vyhodnocování libovolné funkce. Té se obvykle říká
    \em{orákulum.} S~orákulem se komunikuje tak, že vstup funkce zapíšeme na speciální \em{orákulovou pásku,}
    přejdeme do speciálního stavu a na začátku dalšího kroku výpočtu bude obsah orákulové pásky
    nahrazen odpovědí orákula. Do času výpočtu se dotaz na orákulum počítá jako jeden krok.
    
    \subsection{Interaktivní stroje}
    
    Někdy se hodí vybavit algoritmy schopností interagovat s~okolím, tedy v~průběhu výpočtu
    vypisovat výstup a získávat další vstup. I~to se dá do Turingova stroje dodělat, a~to podobně
    jako orákulum.
    
    Výstup uložíme na výstupní pásku a pak přejdeme do speciálního stavu, čímž je vypsán.
    Když chceme přečíst vstup, přejdeme do jiného speciálního stavu a na vstupní pásce se
    objeví další slovo ze vstupu.
    
    \exercises
    
    \ex{Pro všechna cvičení z~oddílu \secref{tm} uvažte, zda pomocí vícepáskového
    stroje není možné úlohu vyřešit s~lepší časovou a/nebo prostorovou složitostí.}
    
    \exx{Rozhodněte jazyk závorkování (cvičení \exref{zavorky}) v~čase $\O(n)$
    a prostoru $\O(\log n)$.}
    
    \ex{Uvažujme TM, který umí měnit pásku jenom uděláním \uv{kaňky}. A~jakmile je
    na políčku kaňka, už ho nelze přepsat na jiný symbol. Dokažte, že tyto stroje
    přijímají/rozhodují tytéž jazyky jako standardní TM.}
    
    \ex[onesidedtm]{Dokažte, že TM s~jednostranně nekonečnou páskou dokáže přijímat/rozhodovat
    tytéž jazyky jako standardní TM. Pokud stroj chce udělat pohyb doleva na začátku
    pásky, stroj automaticky přejde do stavu~$q_-$ a zastaví se.}
    
    \exx{Dokažte, že každý TM je možné upravit na ekvivalentní (rozhodující tentýž
    jazyk, vydávající tentýž výstup), který má pouze 2~stavy kromě $q_+$ a~$q_-$.
    }
    
    \exx{Dokažte, že každý TM se vstupní abecedou $\Sigma=\{\0,\1\}$ lze upravit
    na ekvivalentní, jehož pracovní abeceda je $\Gamma=\{\0,\1,\sp\}$.
    }
    
    \exxx[stackauto]{\em{Zásobníkový automat} je TM s~jednou vstupní páskou (na níž nelze
    zapisovat ani se pohybovat doleva) a jednou pracovní páskou používanou jako
    zásobník (při pohybu doleva musíme aktuální znak přepsat na mezeru). Dokažte,
    že jazyk přijímaný každým zásobníkovým automatem je bezkontextový. Aby platila
    i~druhá implikace, musíme nicméně uvažovat nedeterministické zásobníkové automaty.}
    
    \ex{\em{Dvojzásobníkový automat} je definován podobně jako v~minulém cvičení,
    ale místo jednoho zásobníku má dva. Dokažte, že tyto automaty přijímají/rozhodují
    stejné jazyky jako standardní TM.}
    
    \ex{Jak se při převodu vícepáskového stroje na jednopáskový změní časová a prostorová
    složitost?}
    
    \exxx{Navrhněte převod vícepáskového stroje na dvojpáskový tak, aby zpomaloval pouze
    $\O(\log n)$-krát.}
    
    \exx{Navrhněte převod nedeterministického vícepáskového stroje na dvojpáskový tak,
    aby zpomaloval pouze konstanta-krát.}
    
    \endexercises
    
    \section{Vztahy s ostatními modely}
    
    Ukážeme, že Turingův stroj je ekvivalentní s~některými dalšími modely výpočtu.
    Takzvaná \em{Churchova-Turingova teze} dokonce říká, že všechny realistické
    výpočetní modely jsou navzájem ekvivalentní. Jinými slovy že
    je jedno, jaký model použijeme k~definici algoritmu, protože pokaždé vyjde
    (až na vhodný isomorfismus) totéž. Churchovu tezi nicméně není možné dokázat,
    protože neumíme definovat, co znamená realistický výpočetní model.
    
    \subsection{Gramatiky}
    
    \theorem{Třída $\Ell_0$ jazyků generovaných gramatikami je rovná
    třídě \cc{RE} rekurzivně spočetných jazyků.}
    
    Důkaz rozdělíme do dvou lemmat.
    
    \lemma{Každý částečně rozhodnutelný jazyk je generovaný nějakou gramatikou.}
    
    \proof
    Musíme se vypořádat s~tím, že \uv{výpočet} gramatiky probíhá v~opačném směru
    než výpočet Turingova stroje. Gramatika vyjde z~počáteční proměnné a postupně
    přepisuje, až vygeneruje slovo jazyka. Stroj naopak začne nějakým slovem,\foot{Inu,
    i~zde platí, že na počátku bylo slovo.}
    to postupně upravuje a nakonec odpoví, zda slovo patří do jazyka.
    
    Tento rozpor vyřešíme tak, že nejprve gramatikou vygenerujeme dvě kopie slova.
    Jedna (té budeme říkat \em{originál}) bude složena z~terminálů, druhá (řečená \em{pracovní})
    bude obsahovat aspoň jednu proměnnou. Na pracovní kopii budeme simulovat výpočet stroje. Pokud výpočet
    skončí v~přijímacím stavu, smažeme celou pracovní kopii, čímž zbude jen originál slova z~terminálů
    a~přepisování se zastaví.
    
    Jelikož gramatikou se snáz než $\alpha\alpha$ generuje $\alpha\alpha\rev$,
    dovolíme si drobný trik: stroj před převáděním na gramatiku upravíme, aby
    rozhodoval slova zapsaná pozpátku. Na to stačí přesunout hlavu na konec slova
    a pak spustit původní výpočet s~prohozenými směry doleva a doprava.\foot{Tím jsme mimochodem dokázali, že třída rozhodnutelných
    i částečně rozhodnutelných jazyků jsou obě uzavřené na otočení.}
    
    Nyní konkrétněji. Terminály gramatiky budou znaky pracovní abecedy stroje~$\Gamma$.
    Proměnné gramatiky budou tvořeny:
    
    \list{o}
    \:počáteční proměnnou~$I$,
    \:kopií $Q'$ množiny stavů stroje~$Q$ (pro každý stav $t\in Q$ vytvoříme proměnnou $T\in Q'$
    různou od ostatních proměnných a terminálů),
    \:zarážkami \LL{} a \RR{},
    \:pomocnou proměnnou~$J$.
    \endlist
    
    V~průběhu přepisování bude mít slovo tvar $\alpha\LL\beta\RR$, kde $\alpha\in\Sigma^*$ je
    originál slova a $\beta$ aktuální obsah pásky stroje tvořený terminály z~$\Gamma$,
    do nějž je před pozici hlavy vložen stav stroje v~podobě proměnné z~$Q'$.
    
    Pravidla gramatiky rozdělíme do několika skupin:
    
    \def\Qplus{Q_{\!+}}
    
    \list{o}
    \:Inicializace: má za úkol vytvořit z~$I$ řetězec $\alpha\LL Q_0 \beta\RR$, kde
    $\beta$ je $\alpha\rev$ přepsané do pracovních proměnných.
    	\list{o}
    	\:$I \grule J\RR$
    	\:$J \grule xJx$ (pro všechna $x\in\Sigma$)
    	\:$J \grule \LL Q_0$
    	\endlist
    \:Výpočet stroje: kdykoliv $\delta(x,s) = (x',s',\<pohyb>)$, přidáme pravidlo:
    	\list{o}
    	\:$Sx \grule S'x'$, pokud $\<pohyb>=\bullet$,
    	\:$Sx \grule x'S'$, pokud $\<pohyb>={\rightarrow}$,
    	\:$ySx \grule S'yx'$ pro každé $y\in\Gamma$, pokud $\<pohyb>={\leftarrow}$.
    	\endlist
    \:Expanze pásky o~další mezeru na levém a pravém okraji:
    	\list{o}
    	\:$\LL \grule \LL\sp$
    	\:$\RR \grule \sp\RR$
    	\endlist
    \:Smazání pracovní části, pokud se stroj dostane do stavu~$q_+$
    (v~tomto stavu už výpočet nepokračuje, neboť přechodová funkce tam není definovaná):
    	\list{o}
    	\:$x\Qplus \grule \Qplus$ pro každé $x\in\Gamma$
    	\:$\Qplus x \grule \Qplus$ pro každé $x\in\Gamma$
    	\:$\LL \Qplus \RR \grule \varepsilon$
    	\endlist
    \endlist
    
    Snadno ověříme, že vygenerovat jdou právě ta slova, která stroj přijímá.
    \qed
    
    \lemma{Jazyk generovaný jakoukoliv gramatikou je částečně rozhodnutelný.}
    
    \proof
    Mějme libovolnou gramatiku. Vytvoříme stroj, který bude vyjmenovávat všechna
    slova (z~proměnných i terminálů) získatelná postupným přepisováním počáteční
    proměnné gramatiky: nejprve počáteční proměnnou, pak slova získatelná jedním
    přepsáním, pak dvěma, a~tak dále. Pokud slovo na vstupu stroje leží v~jazyce
    generovaném gramatikou, stroj ho najde mezi vyjmenovanými slovy a přijme.
    Neleží-li v~jazyce, stroj bude buď vyjmenovávat další a další slova, nebo
    (je-li generovaný jazyk konečný), slova mu dojdou a~vstup zamítne.
    
    Stroj sestrojíme jako vícepáskový. Vstupní pásku nebude měnit. Na první
    pracovní pásce bude vyjmenovávat slova a oddělovat je znakem~{\tt\#}.
    Na začátku tam bude jen slovo~$S$. Pokaždé vezmeme další slovo a porovnáme
    ho se vstupem; v~případě shody se zastavíme v~přijímacím stavu. Jinak ve
    slovu zkusíme najít všechny výskyty levých stran pravidel gramatiky (tvar pravidel
    si budeme pamatovat v~přechodové funkci stroje). Kdykoliv nějaký najdeme,
    zapíšeme na druhou pracovní pásku kopii aktuálního slova s~levou stranou
    pravidla vyměněnou za pravou. Nakonec všechna slova z~druhé pracovní
    pásky přepíšeme na konec první pásky a pokračujeme dalším slovem.
    \qed
    
    \subsection{Nedeterministické stroje}
    
    Myšlenku postupného vyjmenovávání možných výpočtů bychom mohli použít
    i k~důkazu, že nedeterministické Turingovy stroje přijímají tytéž jazyky
    jako deterministické stroje. Vlastně bychom prohledávali do šířky strom
    možných výpočtů. Stejný výsledek ale můžeme získat jednodušeji.
    
    \theorem{Nedeterministické Turingovy stroje přijímají částečně rozhodnutelné jazyky.}
    
    \proof
    Všimneme si, že převod Turingova stroje na gramatiku funguje i pro nedeterministické
    stroje: stačí vytvořit pravidla gramatiky pro všechny instrukce $(s',x',\<směr>) \in \delta(s,x)$.
    Proto označíme-li \cc{NRE} třídu jazyků přijímaných nedeterministickými stroji, platí
    $\cc{RE} \subseteq \cc{NRE} \subseteq \Ell_0 = \cc{RE}$.
    \qed
    
    \subsection{Random Access Machine}
    
    I~výpočetní model RAM (Random Access Machine), ve kterém obvykle studujeme
    algoritmy, je ekvivalentní s~TM (Turingovým strojem). Budeme používat definici RAMu
    z~Průvodce labyrintem algoritmů (kapitola o~časové a prostorové složitosti).
    Musíme se nicméně vyrovnat s~tím, že TM zpracovávají řetězce,
    zatímco RAM čísla a jejich posloupnosti.
    Budeme tedy ekvivalenci dokazovat jen pro vstupy, které mají tvar řetězce bitů.
    Takový vstup můžeme TM zadat přímo na pásce a RAMu ho uložit do po sobě jdoucích
    buněk paměti a ukončit číslem~2.\foot{Na reprezentaci vstupu zde nezáleží -- jak
    TM, tak RAM jsou dost silné na to, aby převáděly mezi libovolnými
    \uv{rozumnými} reprezentacemi. Nějakou jsme nicméně museli zvolit.}
    
    RAM můžeme použít k~přijímání jazyka (výpočet pro daný vstup se zastaví),
    k~rozhodování jazyka (výpočet se vždy zastaví a ve smluvené buňce paměti vydá
    nulu nebo jedničku) i k~vyčíslování funkcí (ze smluveného místa v~paměti přečteme
    výsledek funkce). Dostaneme stejné třídy jazyků a funkcí jako pro TM:
    dokážeme, že výpočet TM lze simulovat na RAMu a~opačně.
    
    Simulace TM na RAMu je přímočará: do paměťových buněk RAMu uložíme jednotlivá políčka pásky
    (znaky pracovní abecedy očíslujeme přirozenými čísly). Podle cvičení \exref{onesidedtm} můžeme
    předpokládat jednostranně nekonečnou pásku, tak nám stačí buňky s~nezápornými adresami.
    V~buňkách se zápornou adresou si budeme pamatovat index prvního a posledního
    použitého políčka a pozici hlavy. Stav stroje budeme reprezentovat pozicí v~programu RAMu.
    
    Zajímavější je simulace v~opačném směru. Budeme vytvářet vícepáskový TM.
    
    \list{o}
    \:\em{Reprezentace čísel:} RAM počítá s~celými čísly, na TM je budeme kódovat ve dvojkové
    soustavě se samostatným znakem pro znaménko.
    \:\em{Aritmetické operace:} pro každou aritmetickou a bitovou operaci RAMu sestrojíme
    část TM, která ji bude počítat. Pro vstupy a výstup operace použijeme samostatné pracovní pásky.
    \:\em{Reprezentace paměti:} na další pracovní pásce si budeme pamatovat použitou část paměti RAMu
    v~podobě posloupnosti dvojkových čísel oddělených symbolem~{\tt\#}. Dalším znakem vyznačíme
    nultou buňku a ve stavu stroje si budeme pamatovat, zda jsme zrovna před ní nebo za ní, takže se
    budeme umět kdykoliv k~nulté buňce vrátit.
    \:\em{Čtení z~paměti:} adresu požadované buňky dostaneme na speciální pásce.
    Nejprve tuto buňku najdeme: pokud je adresa kladná, vydáme se po paměťové pásce doprava a za každý~{\tt\#} odečteme
    od adresy jedničku. Až se adresa vynuluje, zkopírujeme obsah buňky na další pracovní pásku.
    Je-li adresa záporná, postupujeme doleva a jedničky přičítáme.
    Pokud během hledání buňky opustíme inicializovanou část paměti, budeme podle potřeby přidávat
    prázdné buňky.
    \:\em{Zápis do paměti} dostane adresu a hodnotu na dvou pracovních páskách. Buňku najdeme podobně
    jako při čtení a pak do ní začneme kopírovat hodnotu. Pokud se hodnota do buňky nevejde, rozšíříme
    buňku o~další znaky, což vyžaduje posunout všechny následující znaky.
    \:\em{Aritmetické instrukce:} nejprve přečteme operandy (to jsou konstanty, přímo adresované
    buňky nebo nepřímo adresované buňky), pak zavoláme podprogram pro výpočet aritmetické operace,
    a nakonec výsledek zapíšeme do paměti (přímo nebo nepřímo adresované).
    \:\em{Chod programu a řídicí instrukce:} posloupnost instrukcí programu bude zakódovaná do přechodové
    funkce stroje, pozici v~programu si budeme pamatovat ve stavu stroje. Nepodmíněný skok pouze změní
    pozici v~programu. Podmíněný skok předtím vyhodnotí podmínku podobně jako aritmetickou operaci. Instrukce
    zastavení programu způsobí vydání výsledku a zastavení stroje.
    \endlist
    
    RAM je tedy stejně silný jako TM.
    
    \exercises
    
    \exx{Nedeterministický stroj rozhoduje jazyk~$L$, pokud se pro každé vstupní slovo~$\alpha$
    všechny výpočty stroje zastaví a $\alpha\in L$ právě tehdy, když aspoň jeden výpočet skončí
    ve stavu~$q_+$. Dokažte, že každý takový jazyk je rozhodovaný i nějakým deterministickým
    strojem.}
    
    \ex{Doplňte detaily do simulace gramatiky Turingovým strojem.}
    
    \exx{Doplňte detaily do simulace RAMu Turingovým strojem.}
    
    \ex{Ukažte, jak simulovat generování slova gramatikou nedeterministickým Turingovým
    strojem. Nedeterminismus použijte na výběr pravidla, které se má v~daném kroku přepisování
    použít, a~výběr místa v~řetězci, kde se má pravidlo aplikovat.}
    
    \endexercises
    
    \section{Nerozhodnutelné problémy}
    
    V~tomto oddílu ukážeme, že existují jazyky, které nejsou rozhodnutelné, a~to ani částečně.
    
    Nejdříve se ale vypořádáme s~tím, že na rozdíl od běžných počítačů je na Turingově
    stroji program pevnou součástí stroje. Ukážeme, že každý stroj jde popsat nějakým
    řetězcem (kódem stroje), a sestrojíme univerzální stroj, jenž je schopen simulovat
    libovolný stroj zadaný kódem.
    
    \defn{Zavedeme \em{kódování} Turingových strojů, které každému stroji s~jednou páskou
    a vstupní abecedou $\{\0,\1\}$ přiřadí nějaké slovo z~$\{\0,\1\}^*$:
    
    \list{o}
    \:Očíslujeme stavy stroje: $Q=\{s_1,s_2,\ldots,s_{\vert Q\vert}\}$, přičemž
    $s_1=q_0$, $s_2=q_+$, $s_3=q_-$.
    \:Očíslujeme pracovní abecedu: $\Gamma=\{x_1,\ldots,x_{\vert\Gamma\vert}\}$, přičemž
    $x_1=\0$, $x_2=\1$, $x_3=\sp$.
    \:Očíslujeme směry: $d_1={\leftarrow}$, $d_2={\rightarrow}$, $d_3=\bullet$.
    \:Zakódujeme přechody: $\delta(s_i,x_j) = (s_k,x_\ell,d_m)$ zapíšeme
    řetězcem $\0^i\1\0^j\1\0^k\1\0^\ell\1\0^m\1\1$. Všimneme si, že uvnitř řetězce
    nejsou dvě jedničky za sebou, takže podle $\1\1$ bezpečně poznáme konec.
    \:Kód stroje získáme jako zřetězení všech přechodů v~libovolném pořadí.
    \endlist
    }
    
    \obs{Různé stroje mohou dostat stejný kód, pokud se liší pouze pojmenováním
    stavů a znaků pracovní abecedy. Takové stroje nicméně počítají totéž (přijímají
    i rozhodují tytéž jazyky), takže je není třeba rozlišovat. Podobně můžeme jeden
    stroj zakódovat různými způsoby v~závislosti na pořadí stavů a znaků abecedy,
    ani tyto kódy není potřeba rozlišovat.
    }
    
    \defn{Pro slovo $\alpha\in\{\0,\1\}^*$ definujeme $M_\alpha$ jako stroj s~kódem~$\alpha$.
    Pokud slovo~$\alpha$ není korektním kódem stroje, bude $M_\alpha$ stroj, který se
    hned zastaví ve stavu~$q_-$, a~tedy přijímá i rozhoduje prázdný jazyk.}
    
    \note{Stejným způsobem můžeme zakódovat i všechny částečně rozhodnutelné jazyky nad binární abecedou:
    $L_\alpha$~bude jazyk přijímaný strojem~$M_\alpha$, tedy $L_\alpha=L(M_\alpha)$.
    Jen pozor na to, že každý jazyk $L\in\cc{RE}$ nalezneme v~tomto kódování
    nekonečně-krát ($L=L_\alpha$ pro nekonečně mnoho různých kódů~$\alpha$),
    protože je přijímán nekonečně mnoha stroji -- například můžeme do stroje
    libovolně přidávat nedosažitelné stavy.
    }
    
    Nyní nadefinujeme univerzální jazyk, který v~jistém smyslu obsahuje všechny částečně
    rozhodnutelné jazyky.
    
    \defn{\em{Kódování dvojic} přiřadí každé uspořádané dvojici $(\alpha,\beta)$
    řetězců $\alpha,\beta\in\{\0,\1\}^*$ nějaký řetězec $\pair\alpha\beta \in \{\0,\1\}^*$,
    z~nějž lze dvojici jednoznačně rekonstruovat. Navíc jak zakódování, tak dekódování jsou
    vyčíslitelné funkce.
    }
    
    \example{Kódování dvojic můžeme sestrojit třeba takto:
    $$\pair{a_1\ldots a_n}{b_1\ldots b_m} = \0a_1\0a_2\ldots\0a_n\1\0b_1\0b_2\ldots \0b_m.$$
    Snadno ověříme, že je jednoznačně dekódovatelné.
    }
    
    \defn{\em{Univerzální jazyk} $L_u\subseteq\{\0,\1\}^*$
    obsahuje všechny dvojice $\pair\alpha\beta$, kde $\alpha,\beta\in\{\0,\1\}^*$
    a $\beta\in L(M_\alpha)$.}
    
    \lemma{Univerzální jazyk je částečně rozhodnutelný.}
    
    \proofsketch
    Sestrojíme \em{Univerzální Turingův stroj (UTM),} který dovede simulovat libovolný jiný
    Turingův stroj. Na vstupu dostane dvojici $\pair\alpha\beta$ a bude krok po kroku
    simulovat výpočet stroje~$M_\alpha$ na vstupu~$\beta$. Pokud se stroj~$M_\alpha$ zastaví,
    UTM se také zastaví a vydá stejný verdikt. Pokud se~$M_\alpha$ nezastaví, simulace bude
    pokračovat do nekonečna.
    
    Zhruba popíšeme konstrukci UTM. Bude to vícepáskový stroj, který pak redukujeme
    na jednopáskový.
    
    \list{o}
    \:Na pásce~$K$ bude uložen kód~$\alpha$ simulovaného stroje.
    
    \:Na pásce~$P$ budeme udržovat obsah pásky simulovaného stroje. Jelikož UTM musí mít pevnou
    pracovní abecedu, a~přitom umět simulovat stroj s~libovolně velkou abecedou, je potřeba
    symboly pásky kódovat. UTM si z~kódu~$\alpha$ zjistí počet znaků~$k$ v~pracovní abecedě a
    hodnotu~$k$ si zapíše na pomocnou pásku. Na pásce~$P$ pak bude mít uložené $k$-znakové \em{krabičky}
    oddělené znakem~{\tt\#}. Krabička tvaru $\1^i\0^{k-i}$ kóduje $i$-tý znak abecedy simulovaného stroje.
    
    \:Polohu hlavy simulovaného stroje si budeme pamatovat v~poloze hlavy UTM na pásce~$P$.
    Hlava UTM se bude nacházet někde uvnitř příslušné krabičky, podle symbolu~{\tt\#} umíme
    kdykoliv najít začátek krabičky.
    
    \:Na pásce~$S$ bude uložen aktuální stav simulovaného stroje v~jedničkové soustavě.
    (Opět nelze ukládat tento stav do stavu UTM, protože simulovaný stroj může mít libovolně
    mnoho stavů.)
    
    \:Na začátku výpočtu UTM dekóduje dvojici $\pair\alpha\beta$. Zkontroluje, zda $\alpha$
    je platný kód stroje, a~jinak vstup odmítne. Přepíše slovo~$\beta$ do krabiček na pásce~$P$.
    Na pásku~$S$ zapíše počáteční stav~1.
    
    \:Jeden krok stroje bude UTM simulovat takto: projde kód~$\alpha$ zleva doprava
    a najde přechod, který odpovídá aktuálnímu stavu a znaku na pásce. Jelikož máme
    vše kódované v~jedničkové soustavě, porovnání je triviální. Až přechod najde,
    přepíše krabičku na pásce~$P$ (to jde na místě) i stav na pásce~$S$
    a přesune hlavu na pásce~$P$ do sousední krabičky. Pokud sousední krabička
    ještě neexistuje, založí ji a vyplní znakem číslo~3 (mezerou).
    
    \:UTM kroky opakuje, dokud simulovaný stroj nepřejde do stavu~2 (přijímací)
    nebo~3 (odmítací). Podle toho sám buď přijme, nebo odmítne.
    \qeditem
    \endlist
    
    Univerzální jazyk tedy je částečně rozhodnutelný. Za chvíli se ovšem ukáže, že
    jeho doplněk není částečně rozhodnutelný. Nejprve to ale dokážeme o~jiném
    jazyku.
    
    \defn{\em{Diagonální jazyk} $L_d$ je jazyk nad abecedou $\{\0,\1\}$, který
    obsahuje všechna slova~$\alpha$ taková, že $\alpha\not\in L(M_\alpha)$.
    }
    
    \lemma{Diagonální jazyk není částečně rozhodnutelný.}
    
    \proof
    Pro spor předpokládejme, že $L_d$ je částečně rozhodnutelný. Tedy je přijímán nějakým Turingovým
    strojem. Nechť tento stroj má kód~$\alpha$. Platí tedy $L_d = L(M_\alpha)$.
    
    Položme si otázku, zda slovo $\alpha$ leží v~$L_d$: podle definice~$L_d$ je to právě tehdy,
    když $\alpha\not\in L(M_\alpha)$. Jenže $L(M_\alpha)=L_d$, takže je to právě tehdy, když
    $\alpha\not\in L_d$. Čili $\alpha$ leží v~$L_d$ právě tehdy, když tam neleží, což je spor.
    \qed
    
    \cor{Doplněk univerzálního jazyka není částečně rozhodnutelný.}
    
    \proof
    Ukážeme, že kdyby existoval stroj přijímající~$\overline{L_u}$, mohli bychom ho upravit,
    aby přijímal diagonální jazyk~$L_d$.
    Nový stroj dostane na vstupu slovo~$\alpha$. Vytvoří z~něj dvojici $\pair\alpha\alpha$
    a na ni spustí stroj pro~$\overline{L_u}$.
    To funguje, jelikož $\pair\alpha\alpha \in \overline{L_u} \Leftrightarrow \alpha\not\in L(M_\alpha)
    \Leftrightarrow \alpha\in L_d$.
    Dostali jsme spor s~tím, že $L_d$~není částečně rozhodnutelný.
    \qed
    
    \note{Tady je vidět, proč se jazyku~$L_d$ říká diagonální: Představíme si
    nekonečnou tabulku, která bude mít na jedné ose všechny kódy strojů~$\alpha$,
    na druhé ose budou všechny vstupy~$\beta$ a okénka tabulky budou vyplněna
    \0 a~\1 podle toho, zda $\pair\alpha\beta\in L_u$. Pokud na diagonále tabulky
    prohodíme nuly a jedničky, dostaneme jazyk~$L_d$. Tím pádem se $L_d$ nemůže
    vyskytovat v~žádném řádku tabulky: došli bychom ke sporu v~místě, kde řádek
    protíná diagonálu. Neexistuje tedy žádný stroj přijímající~$L_d$.
    }
    
    \cor{Univerzální jazyk není rozhodnutelný.}
    
    \proof
    Kdyby $L_u$ byl rozhodnutelný, byl by i $\overline{L_u}$ rozhodnutelný -- stačilo by ve stroji prohodit stavy $q_+$ a~$q_-$.
    Tím pádem by byl~$\overline{L_u}$ i částečně rozhodnutelný, což je ve sporu s~předchozím důsledkem.
    \qed
    
    \note{Zjistili jsme tedy, že jazyk~$L_u$ je částečně rozhodnutelný, ale není rozhodnutelný.
    Jazyk~$\overline{L_u}$ a jazyk~$L_d$ nejsou ani částečně rozhodnutelné.
    Inkluze tříd $\cc{R} \subset \cc{RE} \subset \Ell$ jsou tedy všechny ostré.
    }
    
    \note{Jiný pohled na totéž je tzv. \em{problém zastavení (halting problem):} máme najít
    algoritmus, který dostane kód programu a jeho vstup a ma rozhodnout, zda se program pro
    daný vstup zastaví. Takový algoritmus ovšem nemůže existovat, protože by rozhodoval jazyk~$L_u$.
    }
    
    \theoremn{Postova}{Jazyk $L$ je rozhodnutelný právě tehdy, když $L$ i $\overline{L}$
    jsou částečně rozhodnutelné.
    }
    
    \proof
    Jednu implikaci jsme už použili v~důkazu nerozhodnutelnosti jazyka~$L_u$:
    pokud $L$ je rozhodnutelný, pak i $\overline{L}$ je rozhodnutelný (prohodíme
    stavy $q_+$ a~$q_-$). Tím pádem jsou oba částečně rozhodnutelné.
    
    Obrácená implikace je zajímavější: mějme stroj~$A$ rozhodující~$L$ a stroj~$B$
    rozhodující~$\overline{L}$. Představíme si, že oba stroje spustíme současně
    na tomtéž vstupu (podobně jako u~součinu konečných automatů).
    Vytvoříme nový stroj~$M$ se dvěma páskami, z~nichž jedna
    odpovídá stroji~$A$ a druhá stroji~$B$. Stav stroje~$M$ bude určovat stavy obou
    původních strojů $A$ a~$B$. Stroj~$M$ v~jednom kroku provede jak krok stroje~$A$,
    tak krok stroje~$B$. Pokud stroj~$A$ přejde do stavu~$q_+$, stroj~$M$ také.
    Pokud stroj~$B$ přejde do~$q_+$, stroj~$M$ do~$q_-$.
    A~jelikož každý vstup leží buď v~$L$, nebo v~$\overline{L}$, určitě se časem
    buď~$A$ nebo~$B$ zastaví. Stroj~$M$ tedy rozhoduje jazyk~$L$.
    \qed
    
    \exercises
    
    \ex{Dokažte, že třídy $\cc{R}$ a $\cc{RE}$ jsou uzavřené na sjednocení, průnik,
    zřetězení a iteraci. Třída~$\cc{R}$ je uzavřená na doplňky, třída~$\cc{RE}$ nikoliv.
    }
    
    \exx{Zvolme pevnou abecedu~$\Sigma$ o~aspoň dvou znacích. Dokažte, že množina všech
    jazyků nad~$\Sigma$ je nespočetná, zatímco množina všech částečně rozhodnutelných jazyků nad~$\Sigma$
    spočetná. Z~toho plyne nejen to, že některé jazyky nejsou ani částečně rozhodnutelné,
    ale že takové jsou skoro všechny jazyky.}
    
    \exx{Doplňte detaily univerzálního Turingova stroje.}
    
    \ex{Kolik času a prostoru spotřebuje univerzální Turingův stroj? Porovnejte s~časovou a prostorovou
    složitostí simulovaného stroje.}
    
    \ex{\em{Převody jazyků.} Důkaz $L_u\not\in\cc{RE}$ pomocí $L_d\not\in\cc{RE}$ připomíná převody NP-úplných problémů,
    jen roli převodu hraje obecná vyčíslitelná funkce (ne nutně počítaná v~polynomiálním čase).
    Jazyk~$A$ nad abecedou~$\Sigma$ lze převést na jazyk~$B$ nad abecedou~$\Delta$ (značíme $A\rightarrow B$), pokud existuje
    vyčíslitelná funkce $f: \Sigma^* \rightarrow \Delta^*$ taková, že pro všechna $\alpha\in\Sigma^*$
    platí $\alpha\in A \Leftrightarrow f(\alpha)\in B$. Dokažte, že pokud $A\rightarrow B$ a $B$ je (částečně)
    rozhodnutelný, pak $A$ je také (částečně) rozhodnutelný. Takže není-li $A$ (částečně) rozhodnutelný,
    nemůže být ani $B$ (částečně) rozhodnutelný.
    }
    
    \exx{Uvažme jazyk všech $\alpha\in\{\0,\1\}^*$ takových, že $M_\alpha$ s~prázdným vstupem
    se zastaví. Dokažte, že tento jazyk je částečně rozhodnutelný, ale není rozhodnutelný.}
    
    \exx{Uvažme jazyk všech dvojic $\pair\alpha\beta$ takových, že stroje $M_\alpha$ a~$M_\beta$
    přijímají tentýž jazyk. Dokažte, že tento jazyk není částečně rozhodnutelný.}
    
    \exx{Definujme funkci $f: \N\rightarrow\N$. Číslo $f(n)$ bude udávat maximální počet kroků,
    za který se zastaví Turingův stroj s~kódem délky nejvýše~$n$ na vstupu délky nejvýše~$n$
    (stroje, které se nezastaví, nezapočítáváme). Dokažte, že funkce~$f$ není vyčíslitelná.
    Dokažte, že funkce~$f$ roste rychleji než každá vyčíslitelná funkci z~$\N$ do~$\N$.
    (Čísla kódujeme ve dvojkové soustavě.)}
    
    \exx[recenum]{Dokažte, že jazyk je částečně vyčíslitelný právě tehdy, když lze všechna jeho slova
    algoritmicky vyjmenovat. Tedy existuje interaktivní Turingův stroj, který pro spuštění postupně
    vypisuje všechna slova jazyka tak, že každé slovo jazyka je v~konečném čase vypsáno.}
    
    \exx{Dokažte, že jazyk je vyčíslitelný právě tehdy, když lze všechna jeho slova vypsat
    v~délkově-lexikografickém pořadí (slova porovnáváme podle délky, v~rámci téže délky pak
    lexikograficky).}
    
    \endexercises
    
    \section{Inventura jazyků}
    
    V~předchozích kapitolách jsme zavedli několik tříd jazyků:
    
    \list{o}
    \:$\Ell_3$ je třída regulárních jazyků. Ty jsou rozpoznávané konečnými automaty
    (deterministickými i nedeterministickými), generované regulárními výrazy a levými i pravými
    lineárními gramatikami.
    \:$\Ell_2$ je třída bezkontextových jazyků, generovaných bezkontextovými gramatikami.
    \:$\cc{R}$ je třída rozhodnutelných (rekurzivních) jazyků. Ty jsou rozhodovány Turingovým
    strojem, který se vždy zastaví.
    \:$\cc{RE}$ je třída částečně rozhodnutelných (rekurzivně spočetných) jazyků, které Turingův
    stroj přijímá zastavením.
    \:$\Ell_0$ je třída jazyků generovaných obecnými gramatikami.
    \:$\Ell$ je třída všech jazyků.
    \endlist
    
    Pojďme shrnout, co jsme o~nich zjistili:
    $$
    \Ell_3 \subset \Ell_2 \subset \cc{R} \subset \cc{RE} = \Ell_0 \subset \Ell.
    $$
    Vztahy zleva doprava:
    
    \list{o}
    \:Lineární gramatiky jsou speciálním případem bezkontextových. Jazyk $\0^n\1^n$ je bezkontextový, ale není regulární.
    \:Bezkontextové jazyky jsou rozpoznatelné algoritmem CYK. Jazyk $\|a|^n\|b|^n\|c|^n$ je rozhodnutelný, ale není bezkontextový.
    \:Jazyky generované gramatikami jsou právě ty částečně rozhodnutelné.
    \:Rozhodnutelný jazyk je i částečně rozhodnutelný. Jazyk $L_u$ leží v~$\cc{RE} \setminus \cc{R}$.
    \:Jazyky $\overline{L_u}$ a $L_d$ nejsou částečně rozhodnutelné.
    \endlist
    
    \subsection{Složitostní třídy}
    
    Další zajímavé třídy jazyků získáme omezením časové nebo prostorové složitosti
    Turingova stroje, který je rozhoduje:
    
    \defn{Nechť $f$ je funkce z~$\N$ do~$\N$. Potom:
    \list{o}
    \:$L\in\cc{TIME}(f)$ právě tehdy, když je rozhodován Turingovým strojem, který se pro
    vstup délky~$n$ zastaví za $\O(f(n))$ kroků.
    \:$L\in\cc{SPACE}(f)$ právě tehdy, když je rozhodován Turingovým strojem, který pro
    vstup délky~$n$ spotřebuje prostor $\O(f(n))$.
    \:$\cc{NTIME}(f)$ a $\cc{NSPACE}(f)$ jsou definovány analogicky přes nedeterministické stroje.
    \:$\cc{P}$ je sjednocení tříd $\cc{TIME}(n^k)$ přes všechna $k\ge 0$.
    \:$\cc{NP}$ je sjednocení tříd $\cc{NTIME}(n^k)$ přes všechna $k\ge 0$.
    \endlist
    }
    
    Všechny jazyky v~těchto třídách jsou rozhodnutelné.
    
    \exercises
    
    \exx{Třídy $\cc{P}$ a $\cc{NP}$ jsme už jednou zavedli v~kapitole Průvodce o~těžkých problémech
    (ale pouze pro binární abecedu, zatímco zde připouštíme obecnou). Třídu $\cc{NP}$ jsme v~Průvodci definovali pomocí
    certifikátů. Dokažte, že je to ekvivalentní se zdejší definicí pomocí nedeterministického stroje.}
    
    \exx[ellone]{Původní Chomského hierarchie obsahovala ještě třídu~$\Ell_1$. Ta se dá zavést například
    jako jazyky generované \em{nezkracujícími gramatikami.} Všechna pravidla těchto gramatik mají pravou stranu
    aspoň tak dlouhou jako levou. Výjimka se připouští pouze pro pravidlo $S\grule\varepsilon$, pokud se $S$ nevyskytuje
    na pravé straně žádného pravidla. Bezkontextové gramatiky v~ChNF jsou nezkracující. Dokažte, že jazyk všech
    $\|a|^n\|b|^n\|c|^n$ leží v~$\Ell_1$, takže inkluze $\Ell_2\subset\Ell_1$ je ostrá. Dále dokažte, že
    $\Ell_1=\cc{NSPACE}(n)$. Z~toho speciálně plyne, že $\Ell_1\subseteq\cc{R}$. Uměli byste dokázat, že
    tato inkluze je ostrá?}
    
    \endexercises
    
    \sectionstar[tfa]{Obousměrné konečné automaty}
    
    Když jsme v~oddílu \secref{tmvariants} zkoumali varianty Turingových strojů,
    narazili jsme na \em{obousměrný konečný automat} neboli TFA \em{(two-way finite-state automaton).}
    Nebyl by to výstižnější model výpočtů v~konstantním prostoru než konečný automat?
    Nyní dokážeme, že to vyjde nastejno -- každý jazyk přijímaný obousměrným automatem je regulární.
    
    \theorem{Obousměrné konečné automaty přijímají právě regulární jazyky.}
    
    \proof
    Připomeňme definici TFA: je to Turingův stroj, který dostane vstup $\|<|\alpha\|>|$
    a nemá ho povoleno měnit. Navíc na levé zarážce~$\|<|$ nesmí vykonat pohyb doleva
    a na pravé zarážce~$\|>|$ nesmí jít doprava. Aby byl TFA podobnější konečným automatům,
    výpočet začíná s~hlavou na prvním znaku slova~$\alpha$. To je ale detail: TFA můžeme snadno upravit,
    aby výpočet začínal na~$\|<|$ -- stačí přidat nový počáteční stav, v~němž provedeme jeden pohyb
    hlavou doprava a přejdeme do původního počátečního stavu.
    
    Každý regulární jazyk je určitě přijímán nějakým TFA, který vznikne přímočarým
    překladem příslušného DFA. Opačná implikace je méně triviální.
    Uvažme TFA rozpoznávající nějaký jazyk~$L$ a jeho výpočet nad nějakým vstupem~$\alpha$
    délky~$n$. Do vstupu ještě doplníme zarážky $\alpha[-1] = \|<|$ a $\alpha[n] = \|>|$.
    
    Potřebujeme se nějak vyrovnat s~tím, že automat se může během výpočtu na jedno
    políčko vracet opakovaně. Představme si, že se díváme dovnitř výpočtu, hlava zrovna stojí
    na $i$-tém políčku slova~$\alpha$, stroj se právě přepíná ze stavu~$s$ do~$s'$ a chystá se
    odejít doprava do nějakého suffixu $\alpha[i+1:{}]$.
    Jak bude výpočet pokračovat? Jedna možnost je, že se stroj po čase vrátí zprava na $i$-té políčko v~nějakém novém stavu,
    přičemž nic kromě stavu stroje se nezměnilo (na pásku nemůžeme zapisovat).
    Nebo se předtím stroj stihl zastavit a přijmout/odmítnout.
    Případně se stroj zacyklil v~nekonečné smyčce, což rovněž odpovídá odmítnutí vstupu.
    
    Z~této úvahy plyne, že kdybychom znali chování stroje na suffixu $\alpha[i+1:{}]$
    (jakému vstupnímu stavu odpovídá jaký výstupní), mohli bychom pomocí něj určit,
    co bude stroj dělat na políčku~$\alpha[i]$, aniž bychom se dívali na následující
    znaky. Z~toho bychom mohli určit chování na suffixu $\alpha[i:{}]$ a tak dále.
    Zkusme to provést.
    
    Chování stroje na suffixu vstupu $\alpha[i:{}]$ popíšeme nějakou funkcí~$f_i(s)$.
    Ta dostane počáteční stav~$s\in Q\setminus\{q_+, q_-\}$, v~němž stroj vstoupí
    na $\alpha[i]$. Výsledkem funkce je koncový stav~$s'\in Q$, v~němž stroj odchází
    ze suffixu doleva. Pokud je $s'=q_+$, stroj se místo odejití doleva zastavil a přijal.
    Pokud $s'=q_-$, stroj odmítl zastavením nebo zacyklením se.
    
    Ukážeme, jak sestrojit funkci~$f_i$, pokud už známe~$f_{i+1}$.
    Chceme-li stanovit $f(s)$, budeme konstruovat posloupnost stavů $s_0$, $s_1$, $s_2$, \dots{}
    při jednotlivých návštěvách políčka $\alpha[i]$.
    Na počátku položíme $s_0=s$.
    
    Nyní budeme z~libovolného~$s_j$ počítat $s_{j+1}$.
    Podíváme se, co stroj provede, přečte-li ve stavu~$s_j$ znak~$\alpha[i]$.
    Vyhodnotíme tedy přechodovou funkci $\delta(s_j, \alpha[i])$, čímž získáme instrukci, která
    přechází do nějakého stavu~$s'_j$, zapisuje nezměněný znak~$\alpha[i]$ a možná pohybuje hlavou:
    
    \list{o}
    \:Pokud hlava odchází doleva, položíme $f_i(s) = s'_j$ a jsme hotovi.
    \:Pokud hlava zůstává na místě, položíme $s_{j+1} = s'_j$ a pokračujeme ve vytváření posloupnosti
    s~několika výjimkami: Je-li $s'_j$ rovno $q_+$ nebo~$q_-$, položíme $f_i(s) = s'_j$ a skončíme.
    Je-li $s'_j$ rovno některému z~předešlých~$s_k$ pro $k\le j$, stroj se zacyklil, takže položíme
    $f_i(s) = q_-$ a skončíme.
    \:Pokud hlava odchází doprava, využijeme známou funkci $f_{i+1}$ popisující chování na suffixu
    $\alpha[i+1:{}]$, takže položíme $s_{j+1} = f_{i+1}(s'_j)$. Opět ošetříme případy, kdy je tento
    stav roven $q_+$, $q_-$, případně některému z~předchozích stavů v~posloupnosti.
    \endlist
    
    Všimněte si, že funkce~$f_i$ je jednoznačně určena funkcí~$f_{i+1}$ a znakem $\alpha[i]$.
    To nám dává návod na sestrojení konečného automatu, který bude procházet vstupem zprava doleva
    a postupně přepočítávat funkci~$f_i$. Stavy automatu odpovídají všem funkcím z~$Q\setminus\{q_+,q_-\}$ do~$Q$,
    takže jich je konečně mnoho.
    
    Zbývá dořešit, jak automat začne a jak skončí.
    
    Použijeme-li naši konstrukci pro funkci~$f_n$, tedy chování výpočtu na pravé zarážce~\|>|,
    nikdy se nezeptá na neexistující~$f_{n+1}$. To proto, že stroj se na pravé zarážce nemůže
    pohybovat doprava. Funkce~$f_n$ je tedy nezávislá na vstupu, takže může posloužit jako
    počáteční stav automatu.
    
    Až automat přečte levou zarážku~$\|<|$, bude jeho stav roven funkci~$f_{-1}$.
    Ta popisuje chování na celém vstupu. Takže do ní chceme dosadit počáteční stav~$q_0$
    původního TFA.
    Je-li $f_{-1}(q_0)$ rovno~$q_+$, vstup přijmeme.
    Pokud je rovno~$q_-$, tak odmítneme.
    Nic jiného nemůže funkce vrátit, protože by to znamenalo, že automat z~\|<| odešel doleva, a~to nesmí.
    Přijímací stavy tedy odpovídají těm funkcím~$f$, pro něž je $f(q_0)=q_+$.
    
    Tím jsme sestrojili automat dosvědčující regularitu. Ovšem ne původního jazyka~$L$,
    nýbrž jazyka $L' = L\rev\cdot\{\|<|\}$, v~němž jsou slova pozpátku a ukončená zarážkou.
    
    Teď si stačí uvědomit, že z~regularity~$L'$ plyne regularita~$L\rev$ a z~ní zase regularita~$L$.
    Regularitu $L\rev$ můžeme zdůvodnit cvičením \exref{quotex}, protože $L\rev$ je kvocient $L' / \{\|<|\}$.
    Nebo to lze provést přímo úpravou koncových stavů: za koncové prohlásíme ty stavy, z~nichž vede přechod
    před znak~$\|<|$ do některého z~původních koncových stavů.
    Regularitu~$L$ dostaneme z~uzavřenosti regulárních jazyků na otočení (cvičení \exref{regrev}).
    
    \qed
    
    \exercises
    
    \ex{Dokažte, že třída $\cc{SPACE}(c)$ pro libovolnou konstantu~$c$ odpovídá
    jazykům rozpoznatelným TFA, tedy regulárním. Nezapomeňte na pracovní pásky.}
    
    \ex{Rozšiřte definici TFA o~nedeterminismus. Dokažte, že nedeterministické TFA také rozpoznávají
    pouze regulární jazyky. Z~toho plyne, že $\cc{NSPACE}(c) = \cc{SPACE}(c) = \Ell_3$.}
    
    \endexercises
    
    \endchapter