Vyčíslitelnost a složitost výpočtů Turingův stroj •Jde o snadno pochopitelný model skutečného počítače s páskovou pamětí •Lehce programovatelný •Jednoduše lze studovat jeho vlastnosti a omezení • Turingův stroj •Základní principy Turingova stroje: •Páska: Nekonečně dlouhá páska rozdělená na jednotlivé buňky, kde každá buňka může obsahovat symbol (např. 0 nebo 1) nebo může být prázdná. Páska slouží jako paměť stroje. •Hlava: Pohyblivá čtecí a zapisovací hlava, která se může pohybovat doleva nebo doprava po pásce. Hlava může číst symboly z pásky, přepisovat je a provádět určité akce na základě stavu stroje. •Stavy: Turingův stroj má konečný počet stavů, ve kterých se může nacházet. Každý stav představuje aktuální konfiguraci stroje. •Přechodová funkce: Určuje, jak se Turingův stroj chová v závislosti na aktuálním stavu a symbolu, který právě čte. Na základě této funkce může stroj provést několik akcí: změnit symbol na pásce, posunout hlavu doleva nebo doprava a přejít do jiného stavu. Turingův stroj •Jak Turingův stroj pracuje: •Stroj začíná v počátečním stavu a na pásce je zapsán vstup. •Hlava čte symbol z pásky a podle aktuálního stavu a symbolu se provede akce (např. přepis symbolu, pohyb hlavy, přechod do nového stavu). •Tento proces pokračuje, dokud stroj nedosáhne koncového stavu nebo nekonečně neprovádí výpočty. • Rozhodnutelné a nerozhodnutelné problémy Rozhodovací problém •problém, kde na každou instanci odpovídáme ANO / NE. •Instance = konkrétní vstup (číslo, graf, slovo, program...). •Odpověď je vždy jednoznačná. •Každý rozhodovací problém je reprezentován nějakým jazykem L. •Formálně: •L = { ⟨x⟩ | x je instance problému a odpověď na ni je ANO } •Zbytek (Σ* \ L) jsou instance s odpovědí NE. • • • • Rozhodovací problém •Řešit rozhodovací problém znamená: umět rozhodnout, zda slovo patří do jazyka LL. •Úloha pro Turingův stroj / algoritmus. •Pokud existuje stroj, který pro každý vstup vždy správně zastaví a odpoví ANO/NE, pak je problém rozhodnutelný. • Rozhodovací problém •Je dané přirozené číslo sudé? Rozhodovací problém •Instance: každé přirozené číslo n∈N. •Odpověď: •ANO, pokud n je sudé, •NE, pokud n je liché. Rozhodovací problém •Existuje algoritmus, který vždy skončí: •Vstup: číslo n. •Vypočti zbytek po dělení 2 . •Pokud zbytek = 0 → odpověď ANO. •Jinak → odpověď NE. Rozhodovací problém •TS= (Q, Σ, Γ, δ, q0, F) •Q = {q0, q1, qaccept, qreject} •Σ = {1} •Γ = {1, X, _} •Počáteční stav: q0 •Konečný stav: qaccept, qreject •Přechodové stavy: •δ(q0, 1) = (X, R, q1) •δ(q0, _) = (_, S, qaccept) •δ(q1, 1) = (X, R, q0) •δ(q1, _) = (_, S, qreject) Rozhodovací problém •L = { w0 ∣ w ∈ {0,1}* } = množina všech binárních slov, která končí na 0 •L = { w ∈ {0,1}* | w končí na 0 } • Rozhodovací problém •Je dané slovo nad abecedou {a,b} palindrom? Rozhodovací problém •Vstup: slovo w nad {a,b}. •Nastav i ← 1, j ← |w|. •Dokud i < j: • Pokud w[i] ≠ w[j] → odpověď NE. • Jinak nastav i ← i + 1 a j ← j − 1. •Po skončení cyklu → odpověď ANO. • Rozhodovací problém •TS= (Q, Σ, Γ, δ, q0, F) •Q = {q0, q1, q2, q3, q4, q5, qaccept, qreject} •Σ = {a,b} •Γ = {a,b, X, _} •Počáteční stav: q0 •Konečný stav: qaccept, qreject •q0 → výběr levého nespárovaného znaku •q1 → hledání páru pro a (doprava a zpět vlevo) •q2 → hledání páru pro b (doprava a zpět vlevo) •q3 → návrat vlevo po spárování a •q4 → návrat vlevo po spárování b •qaccept, qreject → koncové stavy Rozhodovací problém •δ(q0, X) = (X, R, q0) •δ(q0, a) = (X, R, q1) •δ(q0, b) = (X, R, q2) •δ(q0, _) = (_, S, qaccept) • •δ(q1, a) = (a, R, q1) •δ(q1, b) = (b, R, q1) •δ(q1, X) = (X, R, q1) •δ(q1, _) = (_, L, q3) • •δ(q2, a) = (a, R, q2) •δ(q2, b) = (b, R, q2) •δ(q2, X) = (X, R, q2) •δ(q2, _) = (_, L, q4) • •δ(q3, X) = (X, L, q3) •δ(q3, a) = (X, L, q5) •δ(q3, b) = (b, S, qreject) •δ(q3, _) = (_, R, q0) • •δ(q4, X) = (X, L, q4) •δ(q4, b) = (X, L, q5) •δ(q4, a) = (a, S, qreject) •δ(q4, _) = (_, R, q0) • •δ(q5, X) = (X, L, q5) •δ(q5, a) = (a, L, q5) •δ(q5, b) = (b, L, q5) •δ(q5, _) = (_, R, q0) Rozhodovací problém •q0 : _ a b b a _ – čtu a → přepíšu na X, jdu do q1 •q1 : _ X b b a _ – jedu doprava, na konci _ → přechod do q3 •q3 : _ X b b a _ (hlava na a) – čtu a, přepíšu na X, jdu do q0 •q0 : _ X b b X _ – přeskočím X, čtu b → přepíšu na X, jdu do q2 •q2 : _ X X b X _ – jedu doprava, na konci _ → přechod do q4 •q4 : _ X X b X _ (hlava na b) – čtu b, přepíšu na X, jdu do q0 •q0 : _ X X X X _ – všude jen X, pak _ → qaccept • Rozhodovací problém •L= { w ∈ {a,b}* ∣ w = wR } Nerozhodnutelné problémy •Nerozhodnutelný problém je takový rozhodovací problém, pro který neexistuje algoritmus, jenž by pro všechny vstupy během konečného času určil správnou odpověď ANO / NE. Nerozhodnutelné problémy •Halting problem (problém zastavení) „Zastaví se daný Turingův stroj M na vstupu w?“ – Dokázáno jako nerozhodnutelné pomocí redukce. •Problém příslušnosti „Přijímá daný Turingův stroj M slovo w?“ •Problém prázdnosti „Je jazyk přijímaný Turingovým strojem M prázdný?“ • Metoda redukce •Redukce je způsob, jak přenést obtížnost jednoho problému (A) na jiný problém (B). •Pokud by se dal snadno vyřešit problém B, pak by šlo vyřešit i problém A. •Proto – jestliže A je nerozhodnutelný, pak i B musí být nerozhodnutelný. Metoda redukce •Cíl: chceme ukázat, že problém B je nerozhodnutelný. •Známý problém A: vybereme problém, u kterého už víme, že je nerozhodnutelný (např. problém příslušnosti nebo halting problem). •Redukce f: navrhneme algoritmus (tzv. redukční funkci), který: •vezme libovolný vstup x problému A, •převede ho na vstup f(x) problému B, •tak, že odpovědi odpovídají: •x∈A  ⟺  f(x)∈B • Metoda redukce •Spor: •Předpokládejme, že existuje algoritmus pro problém B. •Pak bychom mohli vzít každý vstup x problému A, přepočítat na f(x), spustit algoritmus pro B a dostat tím i odpověď pro A. •Tím bychom rozhodli A. Ale A je nerozhodnutelný → vzniká spor. •Závěr: problém B je také nerozhodnutelný. • Metoda redukce •A = problém příslušnosti („Přijímá Turingův stroj M slovo w?”) – víme, že je nerozhodnutelný. •B = halting problem („Zastaví se Mna vstupu w?”). •Ukážeme, že kdybychom měli algoritmus pro halting problem, mohli bychom s ním řešit i příslušnost. •Proto je halting problem také nerozhodnutelný. •