====== IN12 Turingovy stroje a jazyky typu 0 ======
(definice, vztah ke gramatikám Chomského hierarchie, rekurzivní a rekurzivně spočetné jazyky, uzávěrové vlastnosti)
===== Vypracovanie =====

==== Definícia ====
<box round 95% blue|Turingov stroj>Turingov stroj (TM) je 9-tica <math>M = (Q,\ \Sigma,\ \Gamma,\ \triangleright,\ \sqcup,\ \delta,\ q_0,\ q_{accept},\ q_{reject})</math> kde:

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

  * <math>\Sigma</math> je konečná množina //vstupných symbolov//

  * <math>\Gamma</math> je konečná množina //páskových (pracovných) symbolov//, obsahujúca ako svoju podmnožinu abecedu <math>\Sigma</math>

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

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

  * <math>\delta:\ (Q \setminus \{q_{accept},q_{reject}\}) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}</math> je //totálna prechodová funkcia//

  * <math>q_0 \in Q</math> je //počiatočný stav//

  * <math>q_{accept} \in Q</math> je //akceptujúci stav//

  * <math>q_{reject} \in Q</math> je //zamietajúci stav//
</box>
Naviac požadujeme, aby Turingov stroj nikdy neprepísal svoju ľavú koncovú značku iným symbolom a aby nikdy neposunul svoju hlavu vľavo od políčka obsahujúceho ľavú koncovú značku. Formálne, požadujeme aby pre každé <math>q \in Q</math> existoval stav <math>p \in Q</math>, taký že:
 <math>\delta(q,\triangleright) = (p,\triangleright,R)</math>
Množina stavov spolu s prechodovou funkciou sa niekedy súhrnne označuje ako //riadiacia jednotka// Turingovho stroja.

=== Neformálny popis ===
Turingov stroj má konečnú množinu stavov //Q//, pásku, ktorá je rozdelená na jednotlivé políčka, a hlavu, ktorá sa môže po páske pohybovať doľava a doprava, čítať a zapisovať symboly. Na každom políčku pásky je zapísaný práve jeden z konečne mnoho páskových (pracovných) symbolov.
Páska je jednosmerne nekonečná. Na najľavejšom políčku je zapísaný symbol ľavého konca pásky <math>\triangleright</math>. Na začiatku výpočtu je na prvom až //n//-tom (<math>n \geq 0</math>) políčku pásky zapísaný vstupný reťazec. Ostatných nekonečne mnoho políčok napravo od vstupu je prázdnych (znak <math>\sqcup</math>).
Výpočet začína v počiatočnom stave <math>q_0</math>, pričom hlava sníma nulté políčko obsahujúce značku <math>\triangleright</math>. Krok výpočtu spočína v tom, že stroj v závislosti na momentálnom stave a symbolu snímaného hlavou:
  - zmení svoj stav (resp. ho môže zmeniť)
  - zapíše symbol na políčko snímané hlavou (čím prepíše symbol, ktorý tam bol predtým)
  - posunie hlavu o jedno políčko doprava alebo doľava
Spôsob, akým sa má zmeniť stav, prepísať symbol a posunúť hlava, predpisuje prechodová funkcia <math>\delta</math>. <math>\delta (q,a) = (p,X,R)</math> teda znamená, že ak stroj v stave //q// sníma symbol //a//, tak prejde do stavu //p//, symbol //a// prepíše symbolom //X// a hlavu posunie o jedno políčko doprava (R - right, L - left). Stroj akceptuje vstupný reťazec, ak prejde do stavu <math>q_{accept}</math>, zamieta, ak prejde do stavu <math>q_{reject}</math>.
Na niektorých vstupoch môže stroj bežať nekonečne dlho bez toho, aby vstupné slovo akceptoval alebo zamietol - v tom prípade stroj //cyklí//. Turingov stroj sa nazýva **//úplný//** práve vtedy, keď pre každý vstup zastaví.

<box round 95% blue|Jazyk akceptovaný TM>

Jazyk akceptovaný Turingovým strojom //M// definujeme ako množinu reťazcov, ktoré //M// akceptuje:

<math>L(M) = \{w \in \Sigma^{*} \ |\ M\ akceptuje\ w\}</math>

Ak je //M// úpný, hovoríme, že jazyk //L(M)// je //rozhodovaný// strojom //M// alebo že stroj //M rozhoduje jazyk L(M)//.
</box>

<box round 95% green|Príklad na TM>**Zadanie:** Navrhnete Turingov stroj rozhodujúci jazyk <math>L = \{a^n b^n c^n \ |\ n \geq 0\}</math>, ktorý nie je bezkontextový.
**Idea riešenia:**((kompletné riešenie, skriptá FJA, str. 108)) Stroj najskôr posúva svoju hlavu až na koniec vstupného reťazca a kontroluje, či je zapísaný na páske v tvare <math>a^* b^* c^*</math> . Pritom nemení obsah pásky (zapíše prečítaný symbol). Keď hlava prečíta prvé prázdne políčko, začne sa posúvať doľava až na ľavý koniec pásky. Nasleduje cyklus, v ktorom hlava "vymaže" (prepíše symbolom X) jeden symbol //a//, jeden //b// a jeden //c// a vráti sa na ľavý koniec pásky. Ak vstupný reťazec patrí do jazyka //L//, stroj nakoniec vymaže na vstupnej páske všetky symboly //a, b, c// a akceptuje. V opačnom prípade zamietne.
</box>

==== Rekurzivne a rekurzivne spočetné jazyky ====
<box round 95% blue|Definícia>Jazyk <math>L \subseteq \Sigma^*</math> nazývame
  * **rekurzívne spočetný** práve vtedy, keď //L = L(M)// pre nejaký Turnigov stroj //M//
  * **rekurzívny** práve vtedy, keď //L = L(M)// pre nejaký úplný Turnigov stroj //M//
</box>
Ku každému rekurzívnemu jazyku //L// existuje Turingov stroj, ktorý ho **//rozhoduje//**. Rekurzívne spočetný jazyk musí splňovať slabšiu podmienku: musí existovať Turingov stroj, ktorý ho **//akceptuje//**, t.j. akceptuje každé slovo z //L//, ale výpočet na slove nepatriaceho //L// môže byť buď zamietajúci alebo nekonečný.
Medzi rekurzívne jazyky patria regulárne, bezkontextové, kontextové jazyky a ďalšie jazyky, ktoré spĺňajú podmienku rekurzívneho jazyka. Každý rekurzívny jazyk je aj rekurzívne spočetný (opačne to neplatí). Rekurzívne spočetné jazyky sa dajú generovať gramatikami typu 0. Metódou diagonalizácie sa dá dokázať, že existuje jazyk, ktorý nie je rekurzívne spočetný.

S rekurzívnymi a rekurzívne spočetnými množinami úzko súvisia rozhodnuteľné, nerozhodnuteľné a čiastočne rozhodnuteľné problémy:
<box round 95% blue|Problémy> **Problém**, kde sa má určiť, či reťazec //w// má vlastnosť //P// nazývame:
  * **rozhodnuteľný** práve keď množina všetkých reťazcov, ktorá má vlastnosť //P//, je rekurzívna
  * **nerozhodnuteľný** práve keď nie je rozhodnuteľný
  * **čiastočne rozhodnuteľný** práve keď množina všetkých reťazcov, ktorá má vlastnosť //P//, je rekurzíve spočetná
</box>

==== Uzáverové vlastnosti ====
<box round 95% blue|Uzáverové vlastnosti> Triedy rekurzívnych a rekurzívne spočetných jazykov sú uzavrené vzhľadom na operácie <math>\cup,\ \cap,\ \cdot,\ \ast</math>
</box>
Nech <math>L_1, L_2</math> sú jazyky akceptované Turingovými strojmi <math>M_1, M_2</math> s disjunktými množinami stavov:

Nedeterminstický stroj <math>M_{\cup}</math> akceptujúci <math>L_1 \cup L_2</math> dostaneme zjednotením strojov <math>M_1, M_2</math>. Stroj <math>M_{\cup}</math> bude mať nový počiatočný stav a v prvom kroku výpočtu stroj nedeterministicky prejde buď do počiatočného stavu <math>M_1</math> alebo <math>M_2</math>. V druhom kroku simuluje výpočet zvoleného stroja.

Stroj <math>M_{\cap}</math> akceptujúci <math>L_1 \cap L_2</math> bude mať pásku s troma stopami. Na prvej je zapísaný vstupný reťazec a jej obsah sa v priebehu výpočtu nemení. Stroj <math>M_{\cap}</math> okopíruje svoj vstup //w// na druhú stopu a simuluje na nej výpočet <math>M_1</math>. Ak <math>M_1</math> akceptoval, okopíruje vstup na tretiu stopu a na nej simuluje výpočet <math>M_2</math>. Ak <math>M_2</math> akceptuje, akceptuje aj <math>M_{\cap}</math>, v iných prípadoch zamietne.

Nedeterministický stroj <math>M_{\circ}</math> akceptujúci <math>L_1 \cdot L_2</math> bude mať pásku s troma stopami. Na prvej stope je zapísané vstupné slovo. Stroj prekopíruje nejaký (môže byť aj prázdny) prefix vstupného slova na druhú stopu - dĺžku prefixu určí nedeterminsiticky. Okopírované symboly sa na prvej páske označia. Na druhej stope potom <math>M_{\circ}</math> simuluje výpočet <math>M_1</math>. Ak <math>M_1</math> akceptuje, <math>M_{\circ}</math> prekopíruje na tretiu stopu zvyšnú neoznačkovanú časť slova a simuluje na nej výpočet <math>M_2</math>. <math>M_{\circ}</math> akceptuje práve vtedy, keď <math>M_2</math> akceptuje.

Nedeterministický stroj <math>M^*</math> akceptujúci jazyk <math>L_1^*</math> je zobecnením stroja <math>M_{\circ}</math>.

<box round 95% blue|Komplement>Trieda rekurzívnych jazykov je uzavretá vzhľadom k operácii komplementu.</box>
Ak //L// je jazyk akceptovaný //úplným// TM, stroj akceptujúci //co-L// zosrojíme jednoducho tak, že v definícii prechodovej funkcie <math>\delta</math> zameníme navzájom akceptujúci stav <math>q_{accept}</math> a zamietajúci stav <math>q_{reject}</math>.

<box round 95% blue|Postova veta>Nech jazyk //L// i jeho komplement //co-L// sú rekurzívne spočetné. Potom jazyky //L// a //co-L// sú rekurzívne. Postova veta je známa aj ako tvrdenie:
//L je rekurzívny// <math>\Leftrightarrow</math> //L a co-L sú rekurzívne//
</box>
Dôsledkom Postovej vety je, že //trieda rekurzívne spočetných jazykov nie je uzavretá na komplement//. Ak by platil opak, triedy rekurzívnych a rekurzívne spočetných jazykov by sa rovnali.
==== Vzťah TS ku gramatikám Chomského hierarchie ====
<box round 95% blue|Veta 1.1>Triedy jazykov, ktoré sa dajú generovať gramatikami typu 0, resp. akceptovať Turingovými strojmi sú si rovné a tvoria práve triedu rekurzívne spočetných jazykov.
</box>
Dôkaz je možné nájsť v skriptách ((skriptá FJA, str. 123-125)).
Každý rekurzívný jazyk je možné rozhodovať nejakým úplným Turingovým strojom. Z toho bezprostredne vyplýva, že ku gramatikám typu 1-3 (kontextová, bezkontextová, regulárna) vždy existuje úplný Turingov stroj, ktorý //rozhoduje// jazyk generovaný danou gramatikou. Ku gramatike typu 0 existuje TS, ktorý //akceptuje// jazyk generovaný touto gramatikou.

=== Prevod gramatiky typu 0 na TS ===
Nech //L// je jazyk generovaný gramatikou G=(N, Σ, P, S) typu 0. Nedeterministický TS //M// akceptujúci jazyk //L// bude mať 2 stopy. Na prvej stope je zapísaný vstupný reťazec a behom výpočtu sa nemení. Na druhej stope simuluje //M// odvodenie v //G// a je na nej zapísaná (do daného okamihu vygenerovaná) vetná forma α gramatiky //G//. Na zaciatku je obsah druhej stopy //S// a //M// opakovane prevádza tieto kroky:
  - nedeterministicky vybere pozíciu //i// v  reťazci α na druhej stope.
  - nedeterminsticky zvolí pravidlo β → γ gramatiky //G// 
  - ak je β podreťazcom reťazcu α začínajúcim na pozícii //i//, nahradí β reťazcom γ (ak nie sú rovnako dlhé, tak zvyšok druhej pásky posunie doľava alebo doprava)
  - ak sa reťazec na 1.stope rovná reťazcu na 2.stope - akceptuje, inak pokračuje znova krokom 1.

=== Prevod TS na gramatiku typu 0 ===
Odvodenie v gramatike musí nejakým spôsobom simulovať výpočet stroja //M//. V gramatike //G// vygenerujeme dve kópie slova //w// nad abecedou //Σ// a nad druhou z nich v každom kroku odvodenia simulujeme jeden krok výpočtu stroja //M//. Ak stroj //M// neakceptuje, odvodenie nikdy nepovedie k terminálnemu reťazcu. Pravidlá na tvorenie pravidiel gramatiky sú pomerne zložité, nájsť ich môžete v skriptách ((skriptá FJA , str. 125))
===== Predmety =====
* [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3084;kod=IB005|FI:IB005]] Formální jazyky a automaty I (jaro 2006), prof. RNDr. Mojmír Křetínský, CSc.
===== Použitá literatúra =====
* [[http://www.fi.muni.cz/usr/kretinsky/fja1.html|Skriptá k IB005]]
===== Vypracoval =====
Dušan Katona, ICQ: 426 081 873
hotovo: <99%>
môžete kluďne niečo doplniť alebo opraviť

FIXME Je potřeba ještě zapracovat [[http://statnice.dqd.cz/tmp/turingovy_stroje.pdf|poznámky od Jitky Pospíšilové]].

~~DISCUSSION~~