18 Redukce
Definice. Problém nazveme:
• rozhodnutelný, jestliže jeho jazyková reprezentace je rekurzivní jazyk.
• částečně rozhodnutelný, jestliže jeho jazyková reprezentace je rekurzivně spočetný jazyk.
• nerozhodnutelný, jestliže není rozhodnutelný.
Cíl. Naším cílem je zavést formalizmus, pomocí něhož bychom mohli porovnávat obtížnost problémů. To znamená, že hledáme relaci na třídě všech problémů, která je alespoň reflexivní a tranzitivní.
Motivace. Mějme problém Pi určit, zda délka slova nad abecedou £ = {a, b} je dělitelná 13, a předpokládejme, že máme algoritmický postup (v tomto případě stačí dokonce konečný automat) na problém P2 určit, zda délka slova nad £ je dělitelná 26. K vyřešení Pi chceme využít P2, čímž se vyhneme vymyšlení nového algoritmu. Cíl je tedy převést instanci w\ problému P\ na instanci w2 problému P2. To lze udělat např. tak, že položíme w2 = w\w\. Zřejmě w2 je dělitelné 26 právě tehdy, když w\ bylo dělitelné 13. Po aplikaci algoritmu pro P2 na w2 získáme rozhodnutí o instanci w\ pro P\.
Definice. Mějme funkci /: S* —>• T*, kde £ a T jsou nějaké abecedy. Řekneme, že / je totálně vyčíslitelná, jestliže existuje úplný Turingův stroj, který po ukončení výpočtu na vstupu w má na pásce řetězec f(w). Mějme nyní nějaké jazyky yl C E* a B C r*. Řekneme, že A se redukuje na B, píšeme A < B (zkracuji zde běžné značení <m), jestliže existuje totálně vyčíslitelná funkce /: S* —>• T* splňující:
w e A<^ f(w) e B Píšeme A = B, pokud A < B & zároveň B < A.
Úmluva. Připomeňme, že symbolem (M) označujeme nějaké zakódování Turin-gova stroje M jako řetězce nad zvolenou abecedou (toto umíme jednoznačně provést už pro libovolnou dvouprvkovou abecedu). Tento proces potřebujeme pro to, abychom mohli jazykově reprezentovat problémy a vlastnosti Turingo-vých strojů.
Příklad 1. Mějme problém zastavení definovaný jako problém příslušnosti do jazyka:
HALT = {(M) #w | stroj M zastaví na vstupu w} Ukážeme, že problém zastavení a problém akceptování jsou ekvivalentní:
ACCEPT = HALT
K tomu musíme provést dvě redukce:
ACCEPT < HALT: Nejprve si přeložme, co vlastně znamená provést tuto redukci: Naším úkolem je nalézt postup, jak z řetězce M#w udělat řetězec M'#w' takovým způsobem, že M akceptuje w právě tehdy, když M! zastaví na vstupu w'. To můžeme provést třeba následujícím způsobem: Stroj M! vznikne ze stroje
1
M tak, že z něj odstraníme všechny přechody do zamítajícího stavu. Přitom ponecháme w = w'. Potom zřejmě M! zastaví na vstupu w tehdy a jen tehdy, pokud jej akceptuje, tj. pokud jej akceptoval již automat M. Tento postup přitom zřejmě můžeme provést algoritmicky, čili tato redukce je totálně vyčíslitelná, jak se v definici požaduje.
HALT < ACCEPT: V opačném směru chceme z řetězce A4#w udělat řetězec M'#w' takový, že stroj M zastaví na vstupu w právě tehdy, když stroj M! akceptuje vstup w'. Opět nebude potřeba měnit vstup, čili položíme w' = w. Stroj M! získáme ze stroje M tak, že v něm všechny přechody vedoucí do zamítajícího stavu zavedeme do akceptujícího. Tímto způsobem bude stroj M! akceptovat právě všechny vstupy, které stroj M akceptovat nebo zamítal, tedy na nichž svůj výpočet zastavil v konečném čase.
Věta 18.1. Důležité vlastnosti redukce:
1. Relace < je reflexivní a transitivní.
2. Je-li B rekurzivní a A < B, pak A je rekurzivní.
3. Je-li B rekurzivně spočetný a A < B, pak A je rekurzivně spočetný.
4. Pokud A není rekurzivní a A < B, pak B není rekurzivní.
5. Pokud A není rekurzivně spočetný a A < B, pak B není rekurzivně spočetný.
Příklad 2. Problém zastavení je pouze částečně rozhodnutelný, ale není rozhodnutelný. Snadno se ukáže, že tento problém je částečně rozhodnutelný tak, že pro něj sestrojíme Turingův stroj. Tento stroj bude fungovat podobně jako univerzální Turingův stroj tím, že bude simulovat činnost stroje na vstupu pouze s tím rozdílem, že akceptujeme, jestliže simulovaný stroj akceptuje nebo zamítá. V ostatních případech simulovaný i simulující stroj cyklí. Částečná rozhodnutel-nost problému zastavení také plyne z výše dokázané redukce HALT < ACCEPT. Z opačné redukce ACCEPT < HALT zase plyne, že problém zastavení je neroz-hodnutelný.
Poznámka. Předchozí příklad ilustruje dva postupy, které budeme používat k důkazu, že je nějaký jazyk A pouze rekurzivně spočetný:
1. Buď nalezneme ekvivalenci A = R, kde R je jiný pouze rekurzivně spočetný jazyk,
2. nebo sestrojíme Turingův stroj rozpoznávající A a nalezneme redukci N < A, kde N je nějaký nerekurzivní jazyk.
Příklad 3. Problém neprázdno<sti definovaný jako problém příslušnosti do jazyka:
NONEMPTY = {(M) | C{M) + 0}
je částečně rozhodnutelný, ale není rozhodnutelný. Turingův stroj pro tento jazyk bude pracovat následovně: Dostaneme na vstup stroj M. Nedeterministicky na pomocnou pásku zapíšeme slovo a simulujeme činnost M na pomocné pásce,
2
akceptujeme právě tehdy, když akceptuje stroj AA. Takto zřejmě budeme akceptovat právě ty stroje, které akceptují alespoň jedno slovo. Nyní sestrojíme redukci:
ACCEPT < NONEMPTY
Mějme řetězec A4#w. Sestrojme Af, který na začátku provede kontrolu, zda má na vstupu w. Pokud ne, pak automaticky zamítá. V opačném případě pokračuje ve výpočtu jako stroj Ad. Je zřejmé, že stroj Ad akceptuje vstup w právě tehdy, když Af rozpoznává neprázdný jazyk. Tím je naše redukce hotová. Protože problém akceptování není rozhodnutelný, není rozhodnutelný ani problém neprázdnosti.
Příklad 4. Problém určit, zda Turingův stroj akceptuje alespoň 2000 slov (označme příslušný jazyk TS2000), je částečně rozhodnutelný, ale není rozhodnutelný. Turingův stroj pro tento jazyk by pracoval následovně: Dostane na vstup stroj Ad. Paralelně by procházel všechny možné vstupy a simuloval na nich činnost stroje Ad. To může dělat třeba tak, že provede jeden krok výpočtu na prázdném slově, potom jeden krok výpočtu na všech slovech délky jedna, posléze se vrátí a provede další krok výpočtu na prázdném slově, poté na slovech délky jedna a poté na slovech délky dva a znovu od prázdného slova atd. Takto zaručíme, že simulaci stroje Ad na každém možném vstupu, aniž bychom mu dovolili se na některém z nich zacyklit. Zvlášť si pak budeme na druhé pásce počítat, kolik slov akceptuje. Jakmile toto číslo dosáhne 2000, akceptujeme. Na druhou stranu nikdy nezamítáme, protože nemůžeme v konečném čase zjistit, zda stroj bude v budoucnu akceptovat nebo cyklit. Nyní provedeme redukci:
NONEMPTY < TS2000
Mějme stroj Ad s páskovou abecedou S. Sestrojíme stroj Af s páskovou abecedou SU{i}, kde x je nový symbol nevyskytující se v S. Stroj Af na začátku prochází pásku, a pokud se na ní vyskytuje kterýkoli z řetězců xn pro n e {1,..., 1999}, pak akceptuje. V opačném případě pokračuje v činnosti jako stroj A4. Zřejmě stroj Af akceptuje alespoň 2000 slov právě tehdy, když původní stroj akceptoval alespoň jedno slovo.
Příklad 5. Problém ekvivalence definovaný jako problém příslušnosti do jazyka:
EKVIV = {(Ad) # (Af) | C{M) = £(Af)}
není ani částečně rozhodnutelný. Z dříve dokázaných uzáverových vlastností víme, že doplněk jazyka NONEMPTY není ani rekurzivně spočetný (Postova věta), potom ani následující jazyk není r.e.:
EMPTY = {(M) | C(M) = 0}
neboť se od doplňku jazyka NONEMPTY liší pouze ve všech řetězcích, které nejsou kódem žádného Turingova stroje a které dokážeme snadno algoritmicky „odfiltrovat". Fakt, že EKVIV není ani rekurzivně spočetný dokážeme právě redukcí EMPTY < EKVIV. Snadno můžeme sestrojit stroj V, o kterém víme, že rozpoznává prázdný jazyk, např. stroj s prázdnou přechodovou funkcí. Redukce vezme Turingův stroj A4 a vrátí AdjfV. Potom stroje A4 a V rozpoznávají tentýž jazyk právě tehdy, když A4 rozpoznává prázdný jazyk. Tím je redukce hotova.
3
Cvičení 1. Dokážte, že následující jazyk není ani rekurzivně spočetný:
FINITE = {(M) \C (M) je konečný} Cvičení 2. Dokažte, že následující jazyk není ani rekurzivně spočetný:
INFINITE = {(M) \C (M) je nekonečný} Cvičení 3. Dokažte, že následující jazyk není ani rekurzivně spočetný:
REG = {(M) \C(M) = R} kde R je nějaký pevně zvolený regulární jazyk. Definice. Mějme C třídu jazyků. Řekneme, že jazyk A je:
• C-těžký, jestliže pro libovolné X e C platí X < A.
• C-úplný, jestliže je C-těžký a zároveň A e C.
Poznámka. Bez důkazu uveďme, že jazyk ACCEPT je úplný pro třídu rekurzivně spočetných jazyků. To souvisí s univerzalitou příslušného Turingova stroje - interpreta. Rovněž libovolný jazyk X, který je ekvivalentní ACCEPT, je úplný pro třídu rekurzivně spočetných jazyků. Ukázali jsme, že to jsou například jazyky HALT nebo NONEMPTY.
Cvičení 4. Rozhodněte, zda platí následující implikace. Své rozhodnutí zdůvodněte:
a) A < B    Ac < Bc
b) A < B a B je regulární =>■ A je regulární
c) A je rekurzivně spočetný a Ac < A =>• A je rekurzivní
d) A je rekurzivně spočetný a, A < Ac =>• A je rekurzivní
e) A < B a A je rekurzivní =>• B je rekurzivní
f) A je rekurzivně spočetný =>• A < HALT
Definice. Postův systém nad S je konečná množina dvojic:
P = {(ai,A)|ai,AeE*,l<i<n}
Řešení Postova systému je neprázdná konečná posloupnost přirozených čísel ii, ■ ■ ■, ík <= {1, ■ ■ ■, n} taková, že:
OLiY • •' C^ik • • • f3ik
Definujeme:
• Postův korespondenční problém jako problém pro zadaný Postův systém P určit, zda má nějaké řešení.
PCP = {(P) | P je Postův systém, který má řešení}
4
• iniciální Postův korespondenční problém jako problém pro daný Postův systém určit, zda má nějaké řešení začínající číslem 1.
inPCP = {(P) | P je Postův systém, který má řešení začínající číslem 1}
Příklad 6. Mějme Postův systém:
{(c, abc), (ca, b), (o, ca), (ab, a)}
Tento systém má řešení 42341:
ab ■ ca ■ a ■ ab ■ c = a ■ b ■ ca ■ a ■ abc
Tento systém na druhou stranu nemá řešení začínající číslem 1, neboť se nemůžou rovnat dvě slova, kde první začíná znakem c a druhé řetězcem abc.
Cvičení 5. Nalezněte řešení následujícího Postova systému:
{(aa, a), (ab, abab), (b, a), (aba, b)}
Věta 18.2. Oba problémy PCP i inPCP jsou nerozhodnutelné. Lze provést následující redukce:
ACCEPT < inPCP < PCP
Cvičení 6. Ukažte, že Postův korespondenční problém je nerozhodnutelný, i když se omezíme na abecedu {0,1}.
5