Státnice - Algoritmicky nerozhodnutelné problémy

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Tohle je poněkud obšírnější výcuc ke státnicovým okruhům z vyčíslitelnosti pro obory Matematická lingvistika a Softwarové systémy, pocházející ze Strojilových skript, papírových zápisků A. Kazdy a zápisků z předmětu Vyčíslitelnost I ze Studnice -- Tuetschek 14:01, 17 Aug 2010 (CEST)

Turingovy stroje[editovat | editovat zdroj]

Definice (Turingův stroj)[editovat | editovat zdroj]

Deterministický Turingův stroj (DTS) $ M\,\! $ s $ k\,\! $-páskami, kde $ k\,\! $ je konstanta, je pětice

$ M=(Q,\Sigma,\delta,q_0,F) \,\! $
  • $ Q = \,\! $ konečná množina stavů řídící jednotky
  • $ \Sigma = \,\! $ konečná pásková abeceda
  • $ \delta: (Q\backslash F) \times \Sigma^k \mapsto Q \times \Sigma^{k} \times \{L,N,R\}^k \,\! $ je přechodová funkce (částečná)
  • $ q_0 \in Q = \,\! $ počáteční stav
  • $ F \subseteq Q = \,\! $ množina přijímajících stavů

Definice (Konfigurace TS/Postovo slovo)[editovat | editovat zdroj]

Konfigurace (jednopáskového) TS, neboli Postovo slovo, je obsah nejmenší souvislé části pásky, která obsahuje všechna neprázdná a čtené políčko; poloha hlavy a stav. Zapisujeme:

$ UqsV\,\! $

kde $ U, V\,\! $ jsou části pásky nalevo a napravo od hlavy, $ q\,\! $ je stav a $ s\,\! $ čtené políčko.

Poznámka (Kombinování TS)[editovat | editovat zdroj]

  • Spojení dvou TS: napřed počítá $ M1\,\! $, na výsledek pustím $ M2\,\! $, tj. $ M1 \wedge M2\,\! $
  • Větvení (if-then-else): ve stroji $ M1\,\! $ ze stavu $ q_0\,\! $ přechod do (poč. stavu) $ M2\,\! $, z $ q_1\,\! $ do $ M3\,\! $
  • While-cyklus: složené spojení a větvení

Nutná opatrnost -- stejná vnější abeceda, disjunktní vnitřní stavy atd.

Poznámka (Modifikace a omezení (stručně))[editovat | editovat zdroj]

  • Omezení pohybu na jeden směr -- síla stroje klesne na úroveň konečných automatů
  • Omezení na povinný pohyb (L/P) -- OK
  • Jen jedna činnost v taktu (buď zápis, nebo posuv) -- OK
  • Jednostranně omezená páska, více pásek, více hlav -- stále stejná síla
  • Okraje pásky z obou stran -- páska není nekonečná, mám jen konfiguraci stroje -- můžu mít potřebu pásku zvětšovat a zmenšovat (je možné)
  • Omezení na 2 aktivní stavy -- OK (jeden ale nestačí)
  • Omezení na 2 symboly abecedy -- OK (z toho jedno je "blank")
  • K simulaci TS stačí 2 zásobníkové automaty -- z jednoho zásobníku uděláme obsah pásky nalevo, z druhého napravo (vč. čteného znaku) a přehazujeme znaky.

Univerzální Turingův stroj[editovat | editovat zdroj]

Věta (Univ. Turingův stroj)[editovat | editovat zdroj]

Máme dánu abecedu $ A\,\! $. Existuje univerzální TS $ \mathcal{U}\,\! $ nad $ A\,\! $, který pro každý TS nad $ A\,\! $ simuluje výpočet.

$ \mathcal{U}(\mathrm{k\acute{o}d}(T) + \mathrm{k\acute{o}d}(S))\simeq T(S)\,\! $

Důkaz[editovat | editovat zdroj]

  • Vezmeme $ A=\{\lambda, |\}\,\! $, což stačí. BÚNO má každý TS jediný koncový stav $ q_f\,\! $, počáteční stav buď $ q_s\,\! $. Počet stavů -- $ m\,\! $ -- může být velký. Kód stavu $ q_i\,\! $ budiž blok znaků délky $ m+2\,\! $ ($ |\,\! $ + $ i\,\! $-krát $ |\,\! $ + $ m-i\,\! $-krát $ \lambda\,\! $ + $ \lambda\,\! $).
  • Pro $ i\geq 1\,\! $ máme vždy dvě instrukce (jedna pro $ \lambda\,\! $, druhá pro $ |\,\! $). Ty se dají zakódovat do bloku $ \times O_1\times O_2\times O_3\dots \times O_m\times \,\! $, kde $ \times \,\! $ je pomocný symbol (v abecedě $ \mathcal{U}\,\! $ být může) a $ O_i\,\! $ jsou kódy obou instrukcí pro stav $ r_i\,\! $ -- kód zapisovaného písmene, pohybu a cílového stavu.
  • Páska $ \mathcal{U}\,\! $ pak vypadá následovně:
    $ Y[\mbox{blok1}]Y[\mbox{blok2}]\Delta[\mbox{blok3}] \times O_1\times O_2\dots \times O_m\times\,\! $
    • "blok1" je konfigurace pův. stroje, jen obsah právě čteného pole je nahrazen pomocným symbolem $ M\,\! $.
    • "blok2" kóduje aktuální stav pův. stroje.
    • "blok3" je jedna buňka, v níž je uložen obsah právě čteného pole.
  • Univerzální stroj potom sestává z testu bloku2, zda obsahuje koncový stav, procedury vyčištění pásky a vydání výsledku a odsimulování jednoho kroku práce původního stroje
  • Simulace:
  1. najít relevantní blok $ O_i\,\! $ -- stav $ i\,\! $ si nelze pamatovat přímo, proto musím z bloku 2 postupně umazávat $ |\,\! $ a posouvat nějaký spec. symbol "zarážku" doprava
  2. posunout zarážku na konkrétní instrukci podle bloku3 (čteného znaku)
  3. provést instrukci (po kouskách přenést nový stav do bloku 2, pak 6 možností zapisování písmene a pohybu, při pohybu a mazání pozor na okraje pásky)

Důsledek[editovat | editovat zdroj]

Díky tomu lze všechny TS očíslovat.

Věta (Halting problém)[editovat | editovat zdroj]

Halting problém není algoritmicky rozhodnutelný.

Důkaz[editovat | editovat zdroj]

Sporem nechť máme TS $ H(T,K)\,\! $ rozhodující, zda se TS $ T\,\! $ zastaví nad daty $ K\,\! $ (a $ H\,\! $ se zastaví vždy a vydá buď 0 nebo 1). Potom lze vyrobit $ Alg(K)\,\! $ takový, že $ Alg(K)\,\! $ se zastaví, právě když $ \mathcal{U}(K + K)\,\! $ se nezastaví (pomocí $ H\,\! $). Pak $ Alg(K)\,\! $ má nějaký kód, nazveme jej $ Q\,\! $. Pak ale

$ Alg(Q)\mbox{ zastavi}\Leftrightarrow \mathcal{U}(Q + Q)\mbox{ nezastavi} \Leftrightarrow Alg(Q)\mbox{ nezastavi}\,\! $

a to je spor.

Poznámka (Silně a slabě omezené mazání)[editovat | editovat zdroj]

Omezíme mazání v TS:

  • slabě -- máme spec. symbol "kaňka" ($ *\,\! $) a pravidla:
    • $ \lambda \to \mbox{cokoliv} $
    • $ \mbox{cokoliv}\neq \lambda \to *\,\! $
  • silně -- máme abecedu jen $ \{\lambda,*\}\,\! $ a povolený jen přepis $ \lambda\to *\,\! $.

Oba dva případy mají stejnou sílu jako běžný TS (silné se slabým dá simulovat: kaňku kódovat jako blok samých kaněk, převést abecedu; normální TS se dá simulovat slabým postupným překreslováním konfigurací vedle sebe na pásku se současným měněním stavu).

Lze algoritmicky rozhodnout, zda TS $ T\,\! $ s konfigurací $ K\,\! $ někdy přepíše $ \lambda\,\! $ na něco jiného (existuje horní odhad počtu kroků v popsané části pásky). Nelze ale rozhodnout, zda TS $ T\,\! $ s konfigurací $ K\,\! $ někdy přepíše ne-$ \lambda\,\! $ na $ \lambda\,\! $ -- to je ekvivalentní Halting problému ($ T\,\! $ simulujme silně omezeným $ T_1\,\! $ a přidejme $ T_2\,\! $, který smaže 1 kaňku. Pokud se $ T_1T_2\,\! $ zastaví, musel se zastavit i $ T_1\,\! $ a tím bychom rozhodli zastavení $ T\,\! $).