Kapitola 1
Státnice - Algoritmicky nerozhodnutelné problémy

1.1 Turingovy stroje

Definice (Turingův stroj)

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

- konečná množina stavů řídící jednotky

- konečná pásková abeceda

- je přechodová funkce (částečná)

- počáteční stav

- množina přijímajících stavů

Definice (Konfigurace TS/Postovo slovo)

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:

kde jsou části pásky nalevo a napravo od hlavy, je stav a čtené políčko.

Poznámka (Kombinování TS)

- Spojení dvou TS: napřed počítá , na výsledek pustím , tj.

- Větvení (if-then-else): ve stroji ze stavu přechod do (poč. stavu) , z do

- 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ě))

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

1.2 Univerzální Turingův stroj

Věta (Univ. Turingův stroj)

Máme dánu abecedu . Existuje univerzální TS nad , který pro každý TS nad simuluje výpočet.

Důkaz

- Vezmeme , což stačí. BÚNO má každý TS jediný koncový stav , počáteční stav buď . Počet stavů – – může být velký. Kód stavu budiž blok znaků délky ( + -krát + -krát + ).

- Pro máme vždy dvě instrukce (jedna pro , druhá pro ). Ty se dají zakódovat do bloku , kde je pomocný symbol (v abecedě být může) a jsou kódy obou instrukcí pro stav – kód zapisovaného písmene, pohybu a cílového stavu.

- Páska pak vypadá následovně:

- “blok1” je konfigurace pův. stroje, jen obsah právě čteného pole je nahrazen pomocným symbolem .

- “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 – stav 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

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

Věta (Halting problém)

Halting problém není algoritmicky rozhodnutelný.

Důkaz

Sporem nechť máme TS rozhodující, zda se TS zastaví nad daty (a se zastaví vždy a vydá buď 0 nebo 1). Potom lze vyrobit takový, že se zastaví, právě když se nezastaví (pomocí ). Pak má nějaký kód, nazveme jej . Pak ale

a to je spor.

Poznámka (Silně a slabě omezené mazání)

Omezíme mazání v TS:

- slabě – máme spec. symbol “kaňka” () a pravidla:

- silně – máme abecedu jen a povolený jen přepis .

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 s konfigurací někdy přepíše na něco jiného (existuje horní odhad počtu kroků v popsané části pásky). Nelze ale rozhodnout, zda TS s konfigurací někdy přepíše ne- na – to je ekvivalentní Halting problému ( simulujme silně omezeným a přidejme , který smaže 1 kaňku. Pokud se zastaví, musel se zastavit i a tím bychom rozhodli zastavení ).