Skip to content

Latest commit

 

History

History
147 lines (96 loc) · 8.27 KB

10_turinguv_stroj.md

File metadata and controls

147 lines (96 loc) · 8.27 KB
Raw

10. - Turingův stroj

Turingův stroj, problém zastavení, totální a parciální rozhodnutelnost tříd problémů, rekurzivní a rekurzivně spočetné množiny, jejich vztah.

Turingův stroj

  • Teoretický model počítače popsaný matematikem Alanem Turingem
  • Lze pomocí něj implementovat libovolný algoritmus (algoritmus a TS stroj často chápáno jako synonymum)
  • V porovnání s KA je to silnější nástroj
  • Rozpoznává jazyky typu 0
  • Stejně složité úlohy jsou schopny řešit i Postovy stroje nebo Konečné stroje se dvěma a více zásobníky

Základní části:

  1. Páska - Slouží jako paměť - Nekonečná (doprava)
  2. Čtecí hlava - Určuje pozici na pásce - Umožňuje čtení/zápis libovolného znaku na pásku - Pohybuje se vždy o jeden krok doleva (L) nebo doprava (R)
  3. Program - Zapisovali jsme jako konečný, ohodnocený a orientovaný graf (lze zapsat i pomocí insturkcí) - Definuje počáteční stav - Definuje množinu koncových stavů - Graf znázorňuje přechody mezi jednotlivými stavy a činnost čtecí hlavy (čtení, zápis, posun) - Jednotlivé hrany grafu jsou ohodnoceny (čtený symbol, přepisuje na, pohyb hlavy vlevo/vpravo) - Na začátku pásky je zapsáno vstupní slovo, čtecí hlava je na začátku

Ukázka Turingova stroje

Ukázka Turingova stroje

Graf Turingova stroje

Graf Turingova stroje

Výsledek činnosti Turingova stroje:

  • Akceptování (AKC) - (přijetím) slova w (ANO)
  • dosáhne-li stroj stavu STOP (koncového) a výpočet pak končí
  • Zamítnutí (ZAM) - slova w (NE)
  • hlava je nad nejlevějším polem a je dán příkaz pohybu vlevo-
  • dosáhne-li výpočet jistého stavu odkud nevede cesta pro právě přečtený symbol
  • Cyklování (CYK) - znamená, že se stroj dostal do cyklu, kdy se periodicky opakuje jeho činnost bez možnosti zastavení.

Turingovy stroje lze považovat za ekvivaletní, pokud akceptují stejná slova.

Turingův stroj lze považovat za:

  1. AKCEPTOR - akceptuje rekurzívní nebo rekurzivně spočetné množiny.
  2. GENERÁTOR - vyčísluje totálně rekurzívní nebo částečně rekurzívní funkce.
  3. ALGORITMUS - rozhoduje nebo částečně rozhoduje třídu problémů typu ano/ne.

Formální definice:

TS T se definuje nad vstupní abecedou \Sigma.

T = (Q, \pi, \delta, q_0, F), kde

  • Q je množina stavů stroje (neprázdná)
  • \pi je abeceda stroje (neprázdná), \pi = \Sigma \cup V \cup {\Delta} (abeceda stroje se skládá ze vstupní abecedy, pomocných znaků a prázdného symbolu)
  • \delta je parciální zobrazení, které přiřazuje nekoncovému stavu stroje a vstupnímu symbolu následný stav stroje, symbol z abecedy stroje (pro zápis) a směr posunu čtecí hlavy \delta : (Q - F) \times \pi \rightarrow Q \times \pi \times {L, R}
  • q_0 je počáteční stav
  • F je množina koncových stavů

Totální a parciální rozhodnutelnost problémů

Máme třídu problémů na které lze odpovědět ANO/NE a k nim odpovídající algoritmus (TS), který všechny tyto problémy řeší.

Totálně rozhodnutelné problémy

Třída problému je totálně rozhodnutelná právě tehdy, když existuje TS A, který pro všechny problémy z dané třídy zastaví svoji činnost a vydá odpověď (AKC/ZAM), tedy nikdy necykluje.

Příklad:

  • Problém ekvivalence automatů
  • Problém odvození v kontextových gramatikách

Pokud je třída problémů totálně rozhodnutelná, tak je i parciálně rozhodnutelná (neplatí naopak!)

Parciálně rozhodnutelné problémy

  • Třída problémů je parciálně rozhodnutelná právě tehdy, když existuje TS A, který:

    • je-li odpověď na daný problém ANO, tak zastaví akceptováním AKC(A),
    • je-li odpověď na daný problém NE, tak buď zastaví zamítnutím ZAM(A) nebo cykluje CYK(A)

Příklad:

  • problém zastavení TS je parciálně rozhodnutelný

Pokud jsou obě třídy problémů \mathcal{P}, \overline{{\mathcal{P}}} (chápeme jako doplňěk, tvořený z negací všech problémů původní třídy) parciálně rozhodnutelné, pak je třída problémů \mathcal{P} totálně rozhodnutelná (tím pádem je i \overline{\mathcal{P}} totáně rozhodnutelná).

Poznámka: Existují i problémy, které nejsou ani parciálně rozhodnutelné, např. problém nezastavení TS.

Problém zastavení

Existuje takový Turingův stroj, který do dokázal rozhodnout, zda pro libovolný TS M a vstupní slovo w stroj M zastaví?

Takový TS neexistuje, problém zastavení pro Turingovy stroje je nerozhodnutelný.

Důkaz sporem:

Uvažujeme, že existuje výše popsaný TS, který označíme A.

Halting problem A

Na vstupu je kód stroje M a slovo w. Tento TS ukončí činnost akceptováním, pokud TS M zastaví pro slovo w. Svoji činnost ukončí zamítnutím, pokud stroj M pro dané slovo cykluje.

TS A rozšíříme na TS B tak, že:

  • vstupem bude pouze kód stroje a ten bude zároveň i vstupním slovem,
  • stroj B bude cyklovat právě tehdy, když stroj A skončí akceptováním (když stroj M zastaví),
  • stroj B zastaví, pokud stroj A skončí zatítnutím (a tedy stroj M cykluje).

Halting problem B

Vytvořený stroj B je ovšem také TS. Pokud na vstup stroje B dáme jeho vlastní kód, dochází ke sporu, protože:

  • stroj B cykluje právě tehdy, pokud stroj B zastaví,
  • stroj B zastaví právě tehdy, pokud stroj B cykluje.

Halting problem B spor

Jedná se o paradox, což dokazuje, že nelze sestavit TS, který by o libovolném TS rozhodl, zda zastaví pro slovo w. Halting problém je tedy nerozhodnutelný (resp. parciálně rozhodnutelný).

Rekurzivní a rekurzivně spočetné množiny

Rekurzivní množina

Množina S \subset \Sigma^* se nazývá rekurzivní právě tehdy, když existuje TS, který

  1. akceptuje všechna slova w \in S,
  2. zamítne všechna ostatní slova w \in \Sigma^* - S (a tedy nikdy necykluje)

Rekurzivně spočetná množina

Množina S \subset \Sigma^* se nazývá rekurzivně spočetná právě tehdy, když existuje TS, který

  1. akceptuje každé slovo w \in S
  2. buď zamítne nebo cykluje pro slova w \in \Sigma^* - S

Množina S \subset \Sigma^* je rekurzivní právě tehdy, když obě množiny S, \Sigma^* - S jsou rekurzivně spočetné.

Vztah mezi RSM a RM

RM \subsetneqq RSM ... rekurzivní množiny jsou podmnožinami rekurzivně spočetných množin

Vztah RM a RSM

Vztah RM a RSM

Existuje i množina, která není ani RSM. Daný jazyk tím pádem není rozpoznatelný Turingovým strojem.