Máme-li problém formalizován ptejme se, jestli existuje pro každý problém formalizovaný uvedeným způsobem algoritmus. Pro odpověď na tuto otázku je uvedená abstrakce problému obecnější než je nutné. Stačí, omezíme-li se na třídu rozhodovacích problémů. Rozhodovací problémy jsou takové, kterých množina řešení je dvouhodnotová ano /ne. Pro rozhodovací problémy je zobrazení množiny instancí na množinu řešení funkcí. Rozhodovací problémy můžeme formulovat ve vztahu k obecnějším problémům. Pro problém řazení je odpovídající rozhodovací problém vyjádřen funkcí na obr.. Známe-li řešení uvedeného rozhodovacího problému, umíme řešit i odpovídající problém, například systematickým generováním všech permutací prvků zadané posloupnosti a rozhodováním zda jsou seřazeny. Zdůrazněme, že směrujeme k tomu, je-li problém řešitelný a uvedený postup dává odpověď, i když je extrémně neefektivní. Na druhé straně si uvědomme, že právě to dělají algoritmy řazení, tedy pro danou posloupnost prvků z nich vytvoří takovou permutaci, ve které jsou prvky seřazeny.
Zapíšeme-li řešení problému ve tvaru programu pro počítač, instance problému je vstup programu a bude použitím odpovídajícího kódování vyjádřena jako řetězec 0 a 1, který můžeme jednoznačně interpretovat jako přirozené číslo (možná velice veliké). Řešení, výstup programu, můžeme kódovat 1 = ano, 0 = ne. Nyní je rozhodovací problém formalizován jako funkce f: N → { 0, 1}, kde N je množina přirozených čísel, kam zahrnujeme i 0.
Problém "Je zadané přirozené číslo liché?" je formalizován následující funkcí
I / nÎ N 0 1 2 3 4 5 ...
S / f(n) 0 1 0 1 0 1 ...
Uvedený problém řeší například algoritmy na obr., zapsané v Javě. Tak jako v případě problému řazení, existuje víc než jeden algoritmus řešení problému.
Předpokládejme, že najdeme problém, pro který neumíme napsat v Javě algoritmus, jinými slovy je neřešitelný pomocí JVM. Otázka je neexistuje-li jiný formalizmus pro zápis algoritmu, který by takový problém řešil.
Ve třicátých letech minulého století, Alan Turing zavedl pro opis algoritmů formální prostředek, nazývaný Turingovy stroje a Alonzo Church lambda - kalkulus. Ukázali, že opisují stejnou množinu funkcí.
Tyto výsledky vedly k Churchově - Turingově tezi, která tvrdí, že každý algoritmus může být vykonán Turingovým strojem. Navíc, každý program v konvenčních programovacích jazycích může být transformován na Turingův stroj a naopak. Konvenční programovací jazyky a také Java jsou dostatečné pro vyjádření jakéhokoliv algoritmu. Také další formalizace pojmu algoritmu vedly ke stejnému výsledku a obecně se předpokládá platnost Churchove - Turingove teze. Churchova - Turingova teze však není větou a nemůže být dokázána. Může být vyvrácena, bude-li objevena metoda akceptována jako algoritmus, který nebude možno vykonat Turingovým strojem.
Existuje-li tedy rozhodovací problém, pro jehož řešení neexistuje program, například v Javě, potom je tento problém algoritmicky neřešitelný a naopak.
Uvažujme všechny rozhodovací programy v Javě. Jejich binární tvar můžeme interpretovat jako přirozená čísla a vyjmenovat je v jejich pořadí, tedy P0, P1, ..., Pn, ... . Každý z nich může mít vstup interpretovaný jako přirozené číslo 0, 1, 2, ..., k, ... a jeho výstupem je Pn(k)Î{ 0, 1}.
Vytvořme matici uvedenou na obr., jejíž prvek v řádku n a sloupci k je Pn(k). Má-li každý rozhodovací problém specifikovaný nějakou funkcí f: N → { 0, 1} aspoň jeden program v Javě, jenž jej vypočítá, musí v uvedené matici existovat řádek takový, že
Px(k) = f(k), k = 0, 1, 2, ...
Musí tam být například řádky pro programy s metodami jeLiche1( ) a jeLiche2( ) (obr.).
Metodou diagonalizace ukážeme, že existuje problém, tj. funkce f: N → { 0, 1}, pro kterou v uvedené matici neexistuje žádný program.
Problém nazveme D a je definován následovně:
D(k) = 1 je-li Pk(k) = 0
0 je-li Pk(k) = 1 k = 0, 1, 2, …
Takto definovaný problém existuje, ale nemůže být vypočten programem P0, protože D(0) ≠ P0(0), ani programem P1, protože D(1) ≠ P1(1), ... , ani programem Pn, protože D(n) ≠ Pn(n), ... . Pro rozhodovací problém D, tedy neexistuje v Javě žádný program a tedy ani žádný algoritmus.
Pro libovolné pořadí řádků v matici můžeme definovat odpovídající problém D. Existují tedy rozhodovací problémy, pro které neexistují v Javě programy a tedy vzhledem k Churchově-Turingově tezi, pro ně neexistují žádné algoritmy. Takové problémy se nazývají algoritmicky nerozhodnutelné.
První algoritmicky nerozhodnutelný problém ukázal v roce 1936 Alan Turing. Jde o problém zastavení (halting problem), který pomocí programů, například v Javě, můžeme formulovat následovně:
Vstup: Program P v Javě reprezentován jako přirozené číslo a jeho vstup k reprezentován také jako přirozené číslo.
Výstup: 1 když se program P zastaví , 0 když se program P nezastaví.
Ptáme se zda existuje v Javě program, který vypočítá (řeší) problém zastavení. Zdůrazněme, že úkolem není najít algoritmus (program), který rozhodne, zda-li konkrétní program se pro zadaný vstup zastaví, ale program, který rozhodne pro jakýkoliv program a jakýkoliv jeho vstup zda se zastaví nebo ne.
Uvažujme všechny programy v Javě, J0, J1, ..., Jn, ... a vytvořme matici, jejíž prvky jsou výstupy těchto programů pro jejich vstupy anebo ?, pokud pro daný vstup program nezastaví. Příklad takové matice je na obr. .
Nechť existuje metoda pro rozhodnutí zda se program Jn pro vstup k zastaví nebo ne. Potom metodou diagonalizace vytvořme program D, kterého výstup D(k) je 0 když Jk(k) nezastaví a Jk(k) + 1, když zastaví. Tento program však musí být jedním z programů J0, J1, ..., Jn, ..., což nemůže, protože jeho výstup D(k) je různý od výstupu Jk(k) pro každé k.
Jediným předpokladem uvedeného postupu byla existence metody, která má výstup 0, když se program pro zadaný vstup nezastaví a 1 v opačném případě. Sporem jsme tedy ukázali, že pro problém zastavení neexistuje v Javě program, tedy pro něj neexistuje ani žádný algoritmus a problém zastavení je algoritmicky nerozhodnutelný.
Uvedený výsledek lze také dosáhnout následujícím postupem.
Nechť existuje metoda zastavi( ) s parametry program v Javě J a jeho vstup w, oba reprezentované přirozenými čísly, která vrátí true, jestliže se program J pro vstup w zastaví a false, jestliže se nezastaví. Metoda zastavi( ) tedy je
boolean zastavi(int J, int w) {
return boolean z = program J pro vstup w se zastavi;
}
Můžeme pak napsat metodu cyklujKdyzZastavi( ) opět s parametry program J a jeho vstup w, která bude cyklovat, když metoda zastavi( ) vrátí true, jinak skončí. Její diagram je na obr. .
void cyklujKdyzZastavi(int J, int w) {
if (zastavi(J, w))
for ( ; ; );
}
Nyní zvažme program, který volá metodu cyklujKdyzZastavi( ), tak aby rozhodla sama o sobě, tedy parametr J i parametr w budou její celočíselné reprezentace, což znázorníme přetypováním
public static void main(String args[ ]) {
cyklujKdyzZastavi( (int) cyklujKdyzZastavi, (int) cyklujKdyzZastavi );
}
V tomto případě, když metoda zastavi( ), volaná v metodě cyklujKdyzZastavi( ) vrátí false, zjistí, že cyklujKdyzZastavi( ) nezastaví. Z její konstrukce však plyne, že skončí. Opačně, vráti-li metoda zastavi( ) hodnotu true, zjistí, že cyklujKdyzZastavi( ) skončí, avšak z její konstrukce plyne, že zůstane v cyklu for. Dostali jsme tedy spor s předpokladem, kterým byla existence metody zastavi( ) a tedy algoritmus pro problém zastavení nemůže existovat.