Select Git revision
-
Jiří Kalvoda authoredJiří Kalvoda 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.