Algoritmická řešitelnost problémů
Problém definujeme jako binární relaci mezi množinou instancí problému I (tj. množinou všech možností vstupu) a množinou řešení S. Dvě instance mohou mít stejné řešení, stejně tak jedna muže mít více řešení. Algoritmická řešitelnost zkoumá, zda pro všechny formulovatelné problémy lze nalézt algoritmus řešení.
Ve 30. letech 20. století objevil Alan Turing formální opis algoritmu - Turingův stroj, ve spojení s Alonzem Churchem vytvořili Churchovu-Turingovu tezi a sice, že každý algoritmus (ne problém!) lze vykonat Turingovým strojem. Tezi lze vyvrátit nalezením algoritmu nevykonatelného TS. Moderní programovací jazyky pak byly navrženy tak, aby libovolný program šlo převést na TS a naopak. Problém, který nelze vyřešit pomocí TS, tedy ani pomocí programu, je pak algoritmicky neřešitelný.
Vytvoříme-li takový rozhodovací problém (řešení je ano/ne), který pro každý rozhodovací algoritmus a alespoň jeden jeho vstup dává pro tento vstup opačnou odpověď, než daný algoritmus se stejným vstupem, takový problém není řešitelný žádným z těchto algoritmu a je tedy nerozhodnutelný.
První takový problém - problém zastavení - našel sám Turing: program má o všech vytvořitelných programech rozhodnout, zda pro každý ze vstupu daný program zastaví (tehdy vrací jeho výstup v podobě přirozeného čísla + 1) nebo nezastaví (pak vrací 0). Takový program to ale nedokáže rozhodnout sám o sobe (pokud by byl vytvořitelný, patřil by mezi zkoumané programy také a musel by ve svém výstupu vrátit svůj výstup + 1, což nejde).
