Problémy a jazyky: přehled terminologie
Problém	Jazyk
Má objekt 0 vlastnost P?	{(0) | Orná vlastnost P}
je rozhodnutelný	je rekursivní, tj. 3 úplný TM, který ho akceptuje, tj. 3 TM, který ho rozhoduje
je nerozhodnutelný	není rekursivní
je částečně rozhodnutelný neboli semirozhodnutelný	je rekursivně spočetný, tj. 3 TM, který ho akceptuje
IB102 Automaty, gramatiky a složitost, 24.11.2014
1/17
Redukce - Intuice
A = {w g {0,1 }* | | w\ je dělitelná 26} B = {w g {0,1 }* | |w| je dělitelná 13}
IB102 Automaty, gramatiky a složitost, 24.11.2014
2/17
Redukce - Intuice
IB102 Automaty, gramatiky a složitost, 24.11.2014
3/17
Turingovy stroje a funkce
Jednopáskový deterministický Turingův stroj lze vnímat jako funkci, jejíž hodnotou pro daný vstup je obsah pásky po skončení výpočtu. Přesněji, pokud stroj M na vstupu w zastaví s obsahem pásky >yuw (kde y nekončí na u), pak y označíme jako M(w).
IB102 Automaty, gramatiky a složitost, 24.11.2014
4/17
Vyčíslitelné funkce
Definice. Funkce f: Z*    <t>* je vyčíslitelná, pokud existuje TM .A/í, který na vstupu w zastaví, právě když f(w) je definovaná a navíc = .M(w).
Funkce je totálně vyčíslitelná, pokud je vyčíslitelná a totální.
IB102 Automaty, gramatiky a složitost, 24.11.2014
5/17
Příklady
í 1   pokud x = (M, w) a výpočet M na w je konečný
■ f(x) = {
[ 0 jinak
í 1   pokud x = (M,w) a výpočet M na w je konečný | _L jinak
í 1 pokud x = (M, w) a výpočet Mnaw není konečný | _L jinak
(1   pokud x = (M, w) a výpočet Mnaw skončí po nejvýše 100 krocích 0 jinak
IB102 Automaty, gramatiky a složitost, 24.11.2014
6/17
Redukce
Definice. Nechť A c Z* a B c <í>* jsou jazyky. Řekneme, že /A se m-redukuje na fí, píšeme A <m B, právě když existuje totálně vyčíslitelná funkce f: Z*    í>* taková, že
Funkci f nazveme redukcí A na B.
A a B jsou m-ekvivalentní, psáno /A =m fí, pokud /A <m B a fí <m /A.
IB102 Automaty, gramatiky a složitost, 24.11.2014 7/17
HALT =m ACC
HALT = {(M, w) I M je TM a výpočet M na w je konečný} /ACC = {(M,w) \ M \eJM a M akceptuje w}
HALT <m ACC:
IB102 Automaty, gramatiky a složitost, 24.11.2014
8/17
HALT =m ACC
HALT = {(M, w) | M je TM a výpočet M na w je konečný} /ACC = {(M,w) \ M \e TM a M akceptuje w}
ACC <m HALT:
IB102 Automaty, gramatiky a složitost, 24.11.2014
9/17
Redukce a rozhodnutelnost
Věta. Nechť A <m B.
m B je rekursivní =>- A je rekursivní.
■ B je rekursivně spočetný =>- A je rekursivně spočetný. Důkaz.
Nechť f je redukce A na B a Mb je TM akceptující B. Stroj      akceptující /A na vstupu w
□ spočítá f(w)
Q spustí M b na vstupu f(w) a vrátí stejný výsledek jako M b Je-li .Mb úplný, pak je i M a úplný.
IB102 Automaty, gramatiky a složitost, 24.11.2014
Redukce a rozhodnutelnost
Důsledek. Nechť A <m B.
■ A není rekursivní =>- B není rekursivní.
■ A není rekursivně spočetný =>- B není rekursivně spočetný.
Důsledek. Nechť A =m S.
■ /A je rekursivní <;=>- fí je rekursivní.
■ A je rekursivně spočetný <;=>- fí je rekursivně spočetný.
IB102 Automaty, gramatiky a složitost, 24.11.2014
11/17
Typické aplikace
■ důkaz (částečné) rozhodnutelnosti A
m důkaz nerozhodnutelnosti B
IB102 Automaty, gramatiky a složitost, 24.11.2014
12/17
Problém neprázdnosti
Problém neprázdnosti je problém rozhodnout, zda daný TM akceptuje neprázdný jazyk.
NONEMPTY = {{M) \ M je TM a L{M) ŕ 0}
Věta. Problém neprázdnosti není rozhodnutelný.
Důkaz. ACC <m NONEMPTY:
IB102 Automaty, gramatiky a složitost, 24.11.2014
□
13/17
Postův systém
Definice. Postův systém P nad ebecedou Z je konečná množina dvojic
P={
a j Ji
aj,(3j e E*,1 < / < n}.
Řešením systému Pje konečná neprázdná posloupnost přirozených čísel /■i ,i2,---Jk taková, že 1 < /) < n a
aha-,2 ...ajk = (3-h(3-,2 ...(3jk.
Příklad. P = {
c		ca		a		ab
abc		~~b		ca		a
IB102 Automaty, gramatiky a složitost, 24.11.2014
14/17
Postův korespondenční problém (PCP)
Postův korespondenční problém (PCP) je problém rozhodnout, zda má Postův systém P nějaké řešení.
PCP = {(P) | P je Postův systém, který má nějaké řešení}
Iniciální Postův korespondenční problém (inPCP) je problém rozhodnout, zda má Postův systém P 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} Věta. PCP není rozhodnutelný.
Důkaz. Postupně ukážeme ACC <m inPCP <m PCP. □
IB102 Automaty, gramatiky a složitost, 24.11.2014 15/17
inPCP <m PCP
Zkonstruujeme totálně vyčíslitelnou funkci f tak, že
f((P)) = (P'), kde P' má řešení <;=>- P má řešení začínající 1.
P={
ba		b		b		bab
b		bb		abb		a
IB102 Automaty, gramatiky a složitost, 24.11.2014
16/17
ACC <m inPCP
#qr0 > w# > qrV# ... # > ... qacc ... #
IB102 Automaty, gramatiky a složitost, 24.11.2014