====== N-AP15 ======

====== Zadání ======
Rekurzivní a rekurzivně spočetné jazyky. Turingovy stroje. Pojem nerozhodnutelnosti a částečné rozhodnutelnosti.

====== Rekurzivní a rekurzivně spočetné jazyky ======



<box round 95% blue|Definice>Jazyk <math>L \subseteq \Sigma^*</math> nazýváme
  * **rekurzivně spočetný** <=> //L = L(M)// pro nějaký Turnigův stroj //M//
  * **rekurzivní** <=> //L = L(M)// pro nějaký úplný Turnigův stroj //M//
</box>
Ke každému rekurzivnímu jazyku **L** existuje Turingův stroj, který ho **rozhoduje**, tj. výpočet na každém vstupním slovu je konečný. Rekurzivně spočetný jazyk musí splňovat slabší podmínku: musí pro něj existovat Turingův stroj, který ho **akceptuje**, tj. akceptuje každé slovo z **L**, ale výpočet na slovu nepatřícím do **L** může být bud’ zamítající, nebo nekonečný.
Mezi rekurzivní jazyky patří regulární, bezkontextové, kontextové jazyky a další jazyky, které splňují podmínku rekurzivního jazyka. Každý rekurzivní jazyk je i rekurzivně spočetný (opačně to neplatí). Rekurzivně spočetné jazyky se dají generovat gramatikami typu 0. Metodou diagonalizace se dá dokázat, že existuje jazyk, který není rekurzivně spočetný.

S rekurzivními a rekurzivně spočetnými množinami úzce souvisí rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy:
<box round 95% blue|Problémy> **Problém**, kde se má určit, zda řetězec //w// má vlastnost //P// nazýváme:
  * **rozhodnutelný** -- právě když množina všech řetězců, která má vlasnost //P//, je rekurzivní 
  * **nerozhodnutelný** -- právě když není rozhodnutelný
  * **částečně rozhodnutelný** -- právě když množina všech řetězců, která má vlastnost //P//, je rekurzivně spočetná
</box>

===== Uzávěrové vlastnosti rekurzivních a rekurzivně spočetných jazyků =====


<box round 95% blue|Věta> Třídy **rekurzivních a rekurzivně spočetných** jazyků jsou uzavřeny vzhledem k operacím <math>\cup,\ \cap,\ \cdot,\ \ast</math>
</box><box round 95% white|Důkaz pro sjednocení>Necht’ **L1**, **L2** jsou jazyky akceptovány Turingovými stroji **M1**,**M2** a mají disjunktní množiny stavů. Nedeterministický stroj **M∪**, akceptující **L1∪L2**, dostaneme sjednocením strojů **M1** a **M2**. Stroj **M∪** bude mít navíc nový počáteční stav a v prvním kroku výpočtu stroj **M∪** nedeterministicky přejde bud’ do požátežního stavu stroje **M1**, nebo do počátečního stavu stroje **M2**. V druhém kroku simuluje výpočet zvoleného stroje.
{{:mgr-szz:ap-ap:turing_sjednoceni.png|}}
</box>


<box round 95% white|Důkaz pro průnik>Stroj **M∩**, akceptující **L1∩L2**, bude mít pásku se třemi stopami. Na první stopě je zapsán vstupní řetěz a její obsah se v průběhu výpočtu nemění. Stroj **M∩** okopíruje svůj vstup w na druhou stopu a na ní simuluje výpočet **M1** na w. V případě, že **M1** akceptoval, okopíruje vstup w na třetí stopu a na ní pak simuluje výpočet **M2** na w. Jestliže **M2** akceptoval, pak **M∩** též akceptuje. Jinak zamítá.
{{:mgr-szz:ap-ap:turing_prunik.png|}}
</box>

<box round 95% white|Důkaz pro zřetězení>Nedeterministický stroj **M·**, akceptující **L1·L2**, bude mít pásku se třemi stopami. Na první stopě je zapsáno vstupní slovo. Stroj překopíruje nějaký (může být i prázdný) prefix vstupního slova na druhou stopu — délku prefixu určí nedeterministicky. Symboly, které byly okopírovány se na první stopě označkují. Na druhé stopě pak **M·** simuluje výpočet **M1**. V případě, že simulovaný výpočet skončí v akceptující konfiguraci, tak **M·** překopíruje na třetí stopu zbylou (neoznačkovanou) část vstupu a simuluje výpočet **M2** na řetězu zapsaném na třetí stopě. **M·** akceptuje právě když **M2** akceptuje.
</box>


Nedeterministický stroj **M∗**, akceptující L<sub>1</sub><sup>∗</sup>, je zobecněním stroje **M·**.

<box round 95% blue|Věta>Třída **rekurzivních** jazyků je uzavřena vzhledem k operaci komplementu.</box><box round 95% white|Důkaz pro komplement>Necht’ **L** je jazyk akceptovaný úplným deterministickým Turingovym strojem **TM**. Stroj **co–M**, akceptující jazyk **co–L**, získáme tak, že všude v definici přechodové funkce δ zaměníme navzájem akceptující stav q<sub>accept</sub> a zamítající stav q<sub>reject</sub> . Protože **M** je úplný, bude i **co–M** úplný.
{{:mgr-szz:ap-ap:turing_komplement.png|}}
</box>





<box round 95% blue|Postova věta>Necht’ jazyk L i jeho komplement **co–L** jsou rekurzivně spočetné. Pak jazyky **L** a **co–L** jsou rekurzivní. Postova věta je známa i jako tvrzení: **L** je rekurzivní <=> **L** a **co–L** jsou rekurzivně spočetné ((ne rekurzivní, ve skriptech na s. 123 je nejspíš chyba)).
</box><box round 95% white|Důkaz>Předpokládejme, že M1 a M2 jsou Turingovy stroje **akceptující** po řadě jazyky L a co–L. Sestrojíme Turingův stroj M, který bude na vstupu w současně simulovat výpočet M1 na w i výpočet M2 na w. Formálně, stroj M bude mít dvě stopy, jednu pro každý simulovaný výpočet. M střídavě simuluje jeden krok výpočtu stroje M1 (na první stopě) a jeden krok výpočtu stroje M2 (na druhé stopě). M akceptuje vstup, právě když ho akceptuje M1 a M zamítá vstup, právě když ho akceptuje M2. Protože každý řetěz w patří bud’ do jazyka L anebo do jazyka co–L, výpočet M se pro každý vstup zastaví. Proto L je rekurzivní.

</box>
Důsledkem Postovy věty je, že //třída rekurzivně spočetných jazyků není uzavřená na komplement//. Pokud by platil opak, třídy rekurzivních a rekurzivně spočetných jazyků by se rovnaly.

====== Turingovy stroje ======
<box round 95% blue|Definice>Turingův stroj (TM) je 9-tice <math>M = (Q,\ \Sigma,\ \Gamma,\ \triangleright,\ \sqcup,\ \delta,\ q_0,\ q_{accept},\ q_{reject})</math> kde:

  * <math>Q</math> je konečná množina //stavů//

  * <math>\Sigma</math> je konečná množina //vstupních symbolů//

  * <math>\Gamma</math> je konečná množina //páskových (pracovních) symbolů//, obsahující jako svou podmnožinu abecedu <math>\Sigma</math>

  * <math>\triangleright \in \Gamma \setminus \Sigma</math> je //levá koncová značka//

  * <math>\sqcup \in \Gamma \setminus \Sigma</math> je symbol označující //prázdne políčko//

  * <math>\delta:\ (Q \setminus \{q_{accept},q_{reject}\}) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}</math> je //totální přechodová funkce//

  * <math>q_0 \in Q</math> je //počáteční stav//

  * <math>q_{accept} \in Q</math> je //akceptující stav//

  * <math>q_{reject} \in Q</math> je //zamietající stav//
</box>
Turingův stroj má konečnou množinu stavů Q, pásku, která je rozdělena na jednotlivá políčka, a hlavu, která se může po pásce pohybovat doleva a doprava, číst a zapisovat symboly. Na každém políčku pásky je zapsán právě jeden z konečně mnoha páskových (pracovních) symbolů. Páska je jednosměrně nekonečná. Na nejlevějším (nultém) políčku je zapsán speciální symbol <math>\triangleright\</math>, označující levý konec pásky. Na začátku výpočtu je na prvním až n-tém, n ≥ 0, políčku pásky zapsán vstupní řetěz (vstupem tedy může být i prázdný řetěz). Ostatních nekonečně mnoho políček napravo od vstupu je prázdných — tuto skutečnost vyjádříme pomocí speciálního znaku <math>\sqcup\</math>. Výpočet začíná v počátečním stavu q0, přičemž hlava snímá nulté políčko obsahující levou koncovou značku <math>\triangleright\</math>. Krok výpočtu spočívá v tom, že stroj v závislosti na momentálním stavu a symbolu snímaném hlavou
  - změní svůj stav (či přesněji může změnit),
  - zapíše symbol na políčko snímané hlavou (čímž přepíše symbol, který tam byl zapsán předtím) a
  - posune hlavu o jedno políčko doprava, nebo doleva.

Způsob, jakým se má změnit stav, přepsat symbol a posunout hlava, předepisuje přechodová funkce δ. Stroj //akceptuje// vstupní řetěz, právě když přejde do speciálního akceptujícího stavu //q<sub>accept</sub>//. Stroj //zamítá// právě když přejde do speciálního zamítajícího stavu //q<sub>reject</sub>//. Na některých vstupech může výpočet běžet nekonečně dlouho, aniž by stroj vstupní slovo akceptoval, nebo zamítnul. V takovém případě říkáme, že stroj pro daný vstup //cyklí//.
{{:mgr-szz:ap-ap:tm.png|}}
Navíc požadujeme, aby Turingův stroj nikdy nepřepsal levou koncovou značku jiným symbolem a aby nikdy neposunul svou hlavu vlevo od políčka obsahujícího levou koncovou značku. Formálně, požadujeme aby pro každé <math>q \in Q</math> existoval stav <math>p \in Q</math> takový, že: <math>\delta(q,\triangleright) = (p,\triangleright,R)</math>

====== Pojem nerozhodnutelnosti a částečné rozhodnutelnosti ======
**Problém**, kdy se má určit, zda řetěz //w// má vlastnost //P//, nazýváme:
  * **rozhodnutelný** právě když množina všech řetězů majících vlastnost //P// je rekursivní, tj. existuje úplný Turingův stroj //M//, který akceptuje každý řetěz mající vlastnost //P// a zamítne každý řetěz, který tuto vlastnost nemá (//M// rozhoduje jazyk obsahující právě všechna ta slova, která mají vlastnost //P//);

  * **nerozhodnutelný** právˇe když není rozhodnutelný;

  * **částečně rozhodnutelný** (semirozhodnutelný) právě když množina všech řetězů majících vlastnost //P// je rekursivně spoěetná, tj. existuje Turingův stroj, který akceptuje každý řetěz mající vlastnost //P// (a zamítá anebo cyklí pro řetěz nemající vlastnost //P//).


Namísto ”problém určit, zda řetěz //w// má vlastnost //P// je rozhodnutelný (částečně rozhodnutelný)“ zkráceně říkáme, že vlastnost //P// je rozhodnutelná resp. že problém P je rozhodnutelný (částečně rozhodnutelný). Ačkoli vlastnost rekursivní resp. rekursivně spočetný vypovídá o množinách, zatímco rozhodnutelnost resp. semirozhodnutelnost je vlastnost problémů, jsou oba pojmy úzce spjaty.

Platí mezi nimi tato ekvivalence:
//P// je rozhodnutelný <=> jazyk {//w// | //w// má vlastnost //P//} je rekursivní
//L// je rekursivní <=> problém ”//w?∈L//“ je rozhodnutelný
//P// je semirozhodnutelný <=> jazyk {//w// | //w// má vlastnost //P//} je rekursivně spočetný
//L// je rekursivně spočetný <=> problém ”//w?∈L//“ je semirozhodnutelný

====== Předměty ======
IB102 Automaty a gramatiky
IB005 Formální jazyky a automaty
====== Vypracoval ======
Marek Menšík UČO 255679
Nevím přesně, kdo otázky zpracoval přede mnou, pouze jsem je sem umístil, doplnil chybějící věci a opravil nepřesnosti. Připomínám, že věci zde uvedené nemusí být korektní a zatím neprošly kontrolou žádného z profesorů. Z mé strany je tato otázka dokončena a případné chybějící věci a chyby mě můžete napsat na UČO mail nebo se registrujte a upravte je sami.

Z mě strany prozatím hotovo
Možná by se u nerozhodnutelných problémů dalo doplnit více věcí jako Postův korespondenční problém, diagonalizace a jiné.

~~DISCUSSION~~