Skip to content
Snippets Groups Projects
Select Git revision
  • 4421785429124d042d5bd97fce4c6b50ec26940e
  • devel default
  • master
  • fo
  • jirka/typing
  • fo-base
  • mj/submit-images
  • jk/issue-96
  • jk/issue-196
  • honza/add-contestant
  • honza/mr7
  • honza/mrf
  • honza/mrd
  • honza/mra
  • honza/mr6
  • honza/submit-images
  • honza/kolo-vs-soutez
  • jh-stress-test-wip
  • shorten-schools
19 results

util.py

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.