Problém s povolením

Rozhodovací problém ( německy:  Entscheidungsproblem ) je problém v základech matematiky , formulovaný Davidem Hilbertem v roce 1928 : najít algoritmus , který by bral jako vstup popis jakéhokoli problému řešitelnosti (formální jazyk a matematický výrok " " v tento jazyk) - a po konečném počtu kroků by se zastavil a dal jednu ze dvou odpovědí: "Pravda!" nebo "False!", podle toho, zda je výrok " " pravdivý nebo nepravdivý. Odpověď nevyžaduje odůvodnění, ale musí být správná.

Takový algoritmus by mohl například potvrdit Goldbachovu hypotézu a Riemannovu hypotézu, přestože důkazy (a vyvrácení) zatím nejsou známy. Neřešitelnost problému rozlišení (neřešitelnost množiny skutečných aritmetických vzorců) pro aritmetický jazyk obsahující „rovnost“, „sčítání“ a „násobení“ je důsledkem nearitmetické povahy této množiny. Nonaritmeticita je důsledkem Tarskiho teorému „o nevyjádřitelnosti pojmu pravdy v jazyce pomocí stejného jazyka“ [1] .

V roce 1936 Alonzo Church a nezávisle Alan Turing publikovali články, ve kterých ukázali, že neexistuje žádný algoritmus pro určování pravdivosti výroků v aritmetice , a proto obecnější rozhodovací problém také nemá řešení. Tento výsledek je známý jako "Church-Turingova věta" .

Viz také

Poznámky

  1. ↑ V. A. Uspensky , A. L. Semenov Teorie algoritmů: hlavní objevy a aplikace, M., Nauka , 1987, 288 s., 2.3 Aplikace pro matematickou logiku: analýza formalizovaných jazyků logiky a aritmetiky

Literatura