Turingovy stroje

Úloha 6: Turingovy stroje

Zadání

Turingův stroj

Turingův stroj je teoretický model počítače zavedený ve 30. letech 20. století Alanem Turingem. Skládá se z

nekonečné pásky (jednodimenzionálního pole) na které(m) Turingův stroj obdrží vstup a následně na ni provádí výpočet a zapisuje výstup,
hlavy umožňující číst a přepisovat obsah právě zvoleného políčka pásky (ukazatel do pole) a
řídící jednotky, což je orientovaný graf, kde vrcholy reprezentují stavy řídící jednotky a hrany reprezentují instrukce, tedy možné přechody mezi stavy, hrany mají přiřazeny popisy: <čtený symbol> → <zapisovaný symbol>, <posun na pásce>.

Význam popisu hran je: Pokud přečteme <čtený symbol>, tak jej přepíšeme na <zapisovaný symbol> a posuneme se na pásce o políčko doleva, nebo doprava (<posun na pásce> je L nebo R, kde L značí left a R značí right).

Formálně je Turingův stroj sedmice $(Q, \Sigma, \Gamma, \delta, q_0, B, F)$ , kde

$Q$ je konečná množina stavů,
$\Sigma$ je konečná množina vstupních symbolů,
$\Gamma$ je konečná množina páskových symbolů, přitom $\Sigma \subset \Gamma$
$B$ je prázdný symbol (též nazýván blank), jedná se o páskový symbol, který není vstupním symbolem (tj. $B \in \Gamma \setminus \Sigma$ ),
$\delta$ je přechodová funkce, tj. parciální zobrazení z množiny $(Q \setminus F) \times \Gamma$ do množiny $Q \times \Gamma \times \{L, R\}$ , (zde $L$ znamená pohyb hlavy o jedno pole doleva, $R$ znamená pohyb hlavy o jedno pole doprava),
$q_0 \in Q$ je počáteční stav a
$F \subseteq Q$ je množina koncových stavů.

Abychom s Turingovým strojem mohli pracovat, tak musíme ještě zavést pojem situace Turingova stroje (též konfigurace Turingova stroje, v angličtině instantaneous description). Situace Turingova stroje je úplný popis obsahu pásky, pozice hlavy na pásce a stavu, ve kterém se nachází řídící jednotka. Jedná se o

X_1 X_2 ... X_{i-1} q X_i X_{i+1} ... X_k ,

kde symboly $X_1, X_2, ..., X_k$ jsou páskové symboly a kromě nich jsou na pásce (tedy před $X_1$ a po $X_k$ ) pouze blank symboly B; řídící jednotka je ve stavu q a hlava čte symbol $X_i$ .

Turingův stroj se na začátku práce nachází v počáteční situaci (konfiguraci). V počáteční situaci páska obsahuje vstupní slovo, řídící jednotka se nachází ve stavu $q_0$ a hlava čte první neblankový symbol zleva. Tedy v případě vstupního slova $a_1 a_2 ... a_n$ je počáteční situace

q_0 a_1 a_2 ... a_n .

Pokud se Turignův stroj ocitne v koncovém stavu, tak říkáme, že se zastavil úspěšně. Pokud již nemůže provést další přechod a není v koncovém stavu, pak říkáme, že se zastavil neúspěšně.

S automaty a Turingovy stroji se více seznámíte v předmětech JAG, PAL a TAL

Příklad: Jednoduchý Turingův stroj

V následujích obrázcích šipka z prázdna značí počáteční stav, zdvojený kroužek značí koncový stav a zelené obarvení značí současný stav.

Počáteční situace

Situace po prvním kroku

Situace po druhém kroku

Situace po třetím kroku

Situace po čtvrtém kroku

Deterministický Turingův stroj

Pokud má Turingův stroj nejvýše jednu možnost, co provést v daném stavu při přečtení symbolu, pak mu říkáme deterministický Turingův stroj. Výše zmíněná definice Turingova stroje je definicí deterministického Turingova stroje.

Nedeterministický Turingův stroj

Pokud má Turingův stroj více možností, co provést v daném stavu při přečtení symbolu (má více hran se stejným čteným symbolem vedoucích z téhož vrcholu), pak mu říkáme nedeterministický Turingův stroj.

Halting problem

Turingův stroj se nad některými vstupy nemusí zastavit. Určit, zda se libovolný Turingův stroj pracující nad libovolným vstupem zastaví (úspěšně, nebo neúspěšně), je nerozhodnutelná úloha známá jako Halting problem.

Úloha

Na vstupu dostaneme kód Turingova stroje a počáteční stav pásky. Naším úkolem je rozhodnout zda se jedná o deterministický, nebo nedeterministický Turingův stroj, odsimulovat jeho běh a v případě úspěšného zastavení vypsat konečný stav pásky.

Vstupy

První řádek vstupu obsahuje tři čísla oddělena mezerou $N$ , $M$ a $K$ , kde $N$ je počet stavů, $M$ je počet páskových symbolů rozdílných od prázdného symbolu a $K$ je délka vstupního slova.
Druhý řádek vstupu obsahuje $M$ symbolů oddělených mezerou.
Třetí řádek obsahuje prázdný symbol (většinou bude B).
Čtvrtý řádek obsahuje kód Turingova stroje, což je zakódování Turingova stroje předpokládající, že počáteční stav (vrchol) má číslo 1, koncový stav (vrchol) má číslo 2, páskové symboly jsou očíslovány od $1$ do $M+1$ , prázdný symbol má číslo $M+1$ , posuny jsou značeny $D_1 = R$ a $D_2 = L$ .
Za těchto předpokladů je hrana (přechod mezi stavy) $X_j$ → $X_l, D_r$ z vrcholu $q_i$ do vrcholu $q_k$ zakódována slovem $w = 0^i 1 0^j 1 0^k 1 0^l 1 0^r$ . Mocnina v tomto případě znamená počet opakování znaku. 0^3 tedy odpovídá 000. Kód Turingova stroje je $111 w_1 11 w_2 11 ... 11 w_p 111$ , kde slova $w_1, w_2, ..., w_p$ jsou kódy hran.
Pátý řádek obsahuje $K$ symbolů oddělených mezerou reprezentujících počáteční stav pásky. Můžeme předpokládat, že Turingův stroj na vstupu se vždy nad vstupním slovem zastaví.

Výstupy

Výstup obsahuje jeden až dva řádky. První řádek obsahuje znak D, pokud Turingův stroj na vstupu byl deterministický, a N, pokud Turingův stroj na vstupu byl nedeterministický. Pokud se Turingův stroj zastavil úspěšně, pak druhý řádek obsahuje konečný stav pásky (od prvního do posledního neblankového symbolu), tedy posloupnost symbolů oddělenou mezerami. V případě nedeterministického Turingova stroje vypiště konečný stav pásky dosažitelný v nejkratším počtu kroků a pořadí zpracování hran takovém, jak se objevily na vstupu.

Příklady

Příklad 1

Vstup

2 2 8
0 1
B
111010101001011010010101011010001001000100111
1 1 0 0 0 1 0 0

Kód Turingova stroje rozdělený po slovech

111 0101010010 11 0100101010 11 010001001000100 111

Výstup

D
0 0 1 1 1 0 1 1

Obr. 6. Počáteční situace Turingova stroje provádějícího bitovou negaci slova 11000100

Příklad 2

Vstup

3 3 100
X Y Z
B
111010101010110100101001011010001010001011010001000100010110001010001000010110001001000100001011000100001001000010111
Z Z Y Y Y Z Z X X X Y Z Y X X Y Y Y Y Z Z Z X X Z Y Y Z Y X Y X Y Y X Z Y Z X Y Z Y X Z Y X Y Z X Y X X Y X X Y X X Y X Z Z Z X Y Z X Y X X Y X X Y X X Y X X Y X X Y X X Y X X Y X X Y X X Y X X X Y X

Kód Turingova stroje rozdělený po slovech

111 010101010 11 01001010010 11 0100010100010 11 010001000100010 11 0001010001000010 11 00010010001000010 11 000100001001000010 111

Výstup

N
Z Z Y Y Y Z Z X X X Y Z Y X X Y Y Y Y Z Z Z X X Z Y Y Z Y X Y X Y Y X Z Y Z X Y Z Y X Z Y X Y Z X Y X X Y X X Y X X Y X Z Z Z X Y Z

Příklad 3

Vstup

2 2 10
0 1
B
1110101001010111
1 0 0 0 1 1 0 0 1 0

Kód Turingova stroje rozdělený po slovech

111 0101001010 111

Výstup

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data

Teoretické okénko

Turingovy stroje jsou významné i v dnešní době a to nejen jako jednoduchý model počítače, ale především jako základní kámen teorie složitosti.

Pokud máme úlohu, třeba nalezení minimální kostry, pak ji řadíme do třídy složitosti dle toho, kolik času (kroků) či prostoru (počet použitých políček pásky) provede/použije Turingův stroj řešící tuto úlohu pro libovolný vstup a to v závislosti na velikosti vstupu (pro úlohu minimální kostry by byla velikost vstupu počet vrcholů).

Formálně je to trochu složitější, zájemci se mohou podívat na kapitoly 3 a 4 v materiálech profesorky Demlové.

Třída složitosti P

Úlohu řadíme do třídy P, pokud existuje deterministický Turingův stroj, který ji řeší v polynomiálním čase.

Do třídy P patří například úloha minimální kostry.

Třída složitosti NP

Úlohu řadíme do třídy NP, pokud existuje nedeterministický Turingův stroj, který ji řeší v polynomiálním čase.

Není dokázáno, že jsou třídy P a NP různé. Proto často naleznete v různých textech věty na následující způsob. "Za předpokladu $P \neq NP$ …" Různosti tříd P a NP nasvědčuje, že nedetermistické Turingovy stroje používají trik vyzkoušení všech možných řešení a následném ověření jejich správnosti v polynomiálním čase, jenže vyzkoušení všech možných řešení bez nedeterminismu (tedy na běžném počítači) vyžaduje exponenciální čas.

NP těžké úlohy (NP hard)

Úloha je NP těžká, pokud dokážeme všechny NP úlohy převést na tuto úlohu v polynomiálním čase.

NP úplné úlohy

Úlohu považujeme za NP úplnou (řadíme ji do třídy NPC = NP Complete), pokud je NP těžká a zároveň ve třídě NP.

Mezi NP úplné úlohy patří například problém batohu (knapsack), problém obchodního cestujícího (TSP) nebo splňování formulí v konjunktivním normálním tvaru (SAT).

Obr. 6. Třídy složitosti (tak, jak si myslíme, že jsou)

Třída složitosti PSPACE

Úlohu řadíme do třídy PSPACE, pokud existuje deterministický Turingův stroj, který ji řeší a používá polynomiální prostor.

Třída složitosti NPSPACE

Úlohu řadíme do třídy NPSPACE, pokud existuje nedeterministický Turingův stroj, který ji řeší a používá polynomiální prostor.

Třídy složitosti PSPACE a NPSPACE jsou totožné, důkaz je k nalezení v materiálech profesorky Demlové.