Nerozhodnutelné problémy a redukce
Martin Jonáš
IB005 - Formální jazyky a automaty I
Rekurzivní a rekurzivně spočetné jazyky
Rekurzivní jazyk
Rekurzivní a rekurzivně spočetné jazyky
Rekurzivní jazyk
■ existuje TS, který akceptuje každé slovo z jazyka L a každé slovo, které není v L, zamítá
■ odpovídají rozhodnutelným problémům
Rekurzivní a rekurzivně spočetné jazyky
Rekurzivní jazyk
■ existuje TS, který akceptuje každé slovo z jazyka L a každé slovo, které není v L, zamítá
■ odpovídají rozhodnutelným problémům
Rekurzivně spočetný jazyk (RE)
Rekurzivní a rekurzivně spočetné jazyky
Rekurzivní jazyk
■ existuje TS, který akceptuje každé slovo z jazyka L a každé slovo, které není v L, zamítá
■ odpovídají rozhodnutelným problémům
Rekurzivně spočetný jazyk (RE)
■ existuje TS, který akceptuje každé slovo z jazyka L a každé slovo, které není v L, zamítá nebo nad ním cyklí
■ odpovídají částečně rozhodnutelným problémům
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
■ zadaný TS akceptuje alespoň jedno slovo.
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
■ zadaný TS akceptuje alespoň jedno slovo.
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
■ zadaný TS akceptuje alespoň jedno slovo.
Odpovídající nerekurzivní jazyky jsou
■ HALT = {(M,w) | výpočet TS M na slově w je konečný},
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
■ zadaný TS akceptuje alespoň jedno slovo.
Odpovídající nerekurzivní jazyky jsou
■ HALT = {(M,w) | výpočet TS M na slově w je konečný},
■ ACC = {(JVL,w) | TS M akceptuje slovo w},
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
■ zadaný TS akceptuje alespoň jedno slovo.
Odpovídající nerekurzivní jazyky jsou
■ HALT = {(M,w) | výpočet TS M na slově w je konečný},
■ ACC = {(JVL,w) | TS M akceptuje slovo w},
■ NONEMPTY = {(M) | M je TS takový, že L(M) / 0}.
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
■ zadaný TS akceptuje alespoň jedno slovo.
Odpovídající nerekurzivní jazyky jsou
■ HALT = {(M,w) | výpočet TS M na slově w je konečný},
■ ACC = {(JVL,w) | TS M akceptuje slovo w},
■ NONEMPTY = {(M) | M je TS takový, že L(M) / 0}.
Nerozhodnutelné problémy
Existují problémy, které nejsou rozhodnutelné. Například rozhodnout, jestli
■ výpočet zadaného TS na zadaném slově skončí,
■ zadaný TS akceptuje zadané slovo,
■ zadaný TS akceptuje alespoň jedno slovo.
Odpovídající nerekurzivní jazyky jsou
■ HALT = {(M,w) | výpočet TS M na slově w je konečný},
■ ACC = {(JVL,w) | TS M akceptuje slovo w},
■ NONEMPTY = {(M) | M je TS takový, že L(M) / 0}.
Všechny uvedené jazyky jsou rekurzivně spočetné.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/at/'
w g A f (w) g B
pro každé w g I*.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/at/'
w g A => f (w) g B w g A ^= f (w) g B
pro každé w g I*.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/at/'
w g A => f (w) g B w^A ^> f (w) 0 B
pro každé w g I*.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/at/'
w g A w 0 A
» f (w) g B
» f (w) 0 B
pro každé wgZ
*
o
*
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/at/'
w g A => f (w) g B w^A ^> f (w) 0 B
pro každé w g I*.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/at/'
w g A => f (w) g B w^A ^> f (w) 0 B
pro každé w g I*.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/at/'
w g A => f (w) g B w^A ^> f (w) 0 B
pro každé w g I*.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/ař/'
w g A => f (w) g B w^A ^> f (w) 0 B
pro každé w g I*.
Redukce
Definice (m-redukce)
Necht A C I* a B C O*. Říkáme, že jazyk A se m-redukuje na jazyk B (značíme A ^m B), pokud existuje taková totálně
vyčíslitelná funkce f: I* —>► O*, že p/ař/'
w g A => f (w) g B w^A ^> f (w) 0 B
Redukce - příklad
Příklad
Uvažte jazyky
A = {w £ {a,b}* | |w| je dělitelná 2}, B = {w g {a,b}* | |w| je dělitelná 4}.
Ukažte, že platí A ^m B
Redukce, rozhodnutelnost a nerozhodnutelnost
Věta
Pokud A ^m B a B je rekurzivní jazyk, pak také A je rekurzivní
Redukce, rozhodnutelnost a nerozhodnutelnost
Věta
Pokud A ^m B a B je rekurzivní jazyk, pak také A je rekurzivní
Věta
Pokud A ^m B a B je RE, pak také A je RE.
Redukce, rozhodnutelnost a nerozhodnutelnost
Věta
Pokud A ^m B a B je rekurzivní jazyk, pak také A je rekurzivní
Věta
Pokud A ^m B a B je RE, pak také A je RE.
Důsledek
Pokud A ^ m B a A není rekurzivní jazyk, pak B není rekurzivní
Redukce, rozhodnutelnost a nerozhodnutelnost
Věta
Pokud A ^m B a B je rekurzivní jazyk, pak také A je rekurzivní.
Věta
Pokud A ^m B a B je RE, pak také A je RE.
Důsledek
Pokud A ^ m B a A není rekurzivní jazyk, pak B není rekurzivní.
Důsledek
Pokud A ^ m B a A není RE, pak B není RE.
Redukce a nerozhodnutelnost - příklad
Příklad
Dokažte, že problém rozhodnout, jestli dva zadané TS akceptují různé jazyky, není rozhodnutelný. Jinými slovy dokažte, že jazyk
1MOTEQ = {(Mi, M2) | Mi,M2 jsou TS a L(Mi) / L(M2)}
není rekurzivní.
Redukce a nerozhodnutelnost - příklad
Příklad
Dokažte, že problém rozhodnout, jestli výpočet zadaného TS na prázdném slově je konečný, není rozhodnutelný. Jinými slovy dokažte, že jazyk
L = {(M) I výpočet TS M na slově £ je konečný }
není rekurzivní.
Redukce a nerozhodnutelnost - příklad
Příklad
Dokažte, že problém rozhodnout, jestli výpočet zadaného TS na prázdném slově je konečný, není rozhodnutelný. Jinými slovy dokažte, že jazyk
L = {(M) | výpočet TS M na slově £ je konečný }
není rekurzivní.
Je L rekurzivně spočetný?
Redukce a nerozhodnutelnost - příklad
Příklad
Dokažte, že problém rozhodnout, jestli výpočet zadaného TS na prázdném slově je konečný, není rozhodnutelný. Jinými slovy dokažte, že jazyk
L = {(M) | výpočet TS M na slově £ je konečný }
není rekurzivní.
Je L rekurzivně spočetný? Je co—L rekurzivně spočetný?
Redukce a nerozhodnutelnost - příklad
Příklad
Dokažte, že problém rozhodnout, jestli výpočet zadaného TS na prázdném slově je konečný, není rozhodnutelný. Jinými slovy dokažte, že jazyk
L = {(M) | výpočet TS M na slově £ je konečný }
není rekurzivní.
Je L rekurzivně spočetný? Je co—L rekurzivně spočetný?
Věta (Post)
Jazyk L je rekurzivní právě tehdy když jazyky L a co—L jsou rekurzivně spočetné.
Redukce a nerozhodnutelnost - příklad
Příklad
Dokažte, že problém rozhodnout, jestli zadaný TS akceptuje regulární jazyk, není rozhodnutelný. Jinými slovy dokažte, že jazyk
REG = {(M) | M je TS a L(M) je regulární}
není rekurzivní.