Select Git revision
recursive.tex
-
Martin Mareš authoredMartin Mareš authored
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