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

1. řádek

První řádek vstupu obsahuje tři čísla $N$ , $M$ a $K$ oddělená mezerou.

$N$ je počet stavů ve kterých se stroj může nacházet. Stavy jsou číslovány od $1$ do $N$ . To znamená, že pro $N = 4$ jsou platné stavy $1$ , $2$ , $3$ a $4$ . Stav $2$ je vždy považován za koncový stav. Když se do tohoto stavu stroj dostane jedná se o úspěšné zastavení a neměl by pokračovat.
$M$ je počet páskových symbolů rozdílných od prázdného symbolu.
$K$ je délka vstupního slova, tedy počet symbolů zadaných v počátečním stavu pásky na 5. řádku.

2. řádek

Druhý řádek vstupu obsahuje $M$ symbolů oddělených mezerou. Jsou to všechny symboly, které lze číst a zapisovat do pásky vyjma blank symbolu.

3. řádek

Třetí řádek obsahuje symbol, který bude používán jako blank symbol (většinou to bude znak "B").

4. řádek

Čtvrtý řádek obsahuje kód Turingova stroje, což je seznam pravidel (hran) kterými se má stroj při svém provozu řídit zákódovaný unárně tak, že znaky "1" slouží jako separátory/oddělovače hodnot a počet "0" značí číselnou hodnotu. Posloupnost 3 "1" značí počátek a konec kódu. Posloupnost 2 "1" odděluje jednotlivá pravidla (hrany). Samotné "1" oddělují jednotlivé hodnoty pravidla, kterých je dohromady 5.

Každé pravidlo říká:

Pokud se stroj vyskytuje ve stavu (vrcholu) $H_1$ a z pásky přečetl symbol číslo $H_2$ , tak by se měl přesunout do stavu (vrcholu) $H_3$ , na pásku by měl zapsat symbol číslo $H_4$ a pokud $H_5 = 1$ , tak by se měl na pásce posunout doprava a jinak doleva (doleva striktně vzato jen pokud $H_5 = 2$ ).

Kde $H_1$ až $H_5$ značí 5 hodnot daného pravidla, tak jak jsou za sebou v kódu.

Stroj vždy začíná ve stavu číslo 1 a čte 1. znak pásky.

5. řádek

Pátý řádek obsahuje $K$ symbolů oddělených mezerou reprezentujících počáteční stav pásky. Před 1. symbolem se implicitně nachází nekonečno blank symbolů a stejně tak za posledním symbolem. Páska teoreticky nemá konce.

Výstupy

Výstup obsahuje 1, nebo 2 řádky.

1. řádek

První řádek obsahuje znak "D", pokud Turingův stroj na vstupu byl deterministický, a "N", pokud Turingův stroj na vstupu byl nedeterministický.

2. řádek

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 u kterého lze dosáhnout uspěšného zastavení obsahuje druhý řádek konečný stav pásky po úspěšném zastavení stroje dosažitelný v nejkratším počtu kroků a pořadí zpracování hran takovém, jak se objevily na vstupu. Formát výpisu je stejný jako u deterministického stroje.

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 pravidlech

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 pravidlech

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 pravidlech

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é.