Problemă cu permisiunea

Problema deciziei ( germană:  Entscheidungsproblem ) este o problemă din bazele matematicii , formulată de David Hilbert în 1928 : pentru a găsi un algoritm care să ia ca intrare o descriere a oricărei probleme de solubilitate (un limbaj formal și o afirmație matematică „ ” în acest limbaj) - și, după un număr finit de pași, s-ar opri și s-ar fi dat unul dintre cele două răspunsuri: „Adevărat!” sau „Fals!”, în funcție de faptul dacă afirmația „ ” este adevărată sau falsă. Răspunsul nu necesită justificare, dar trebuie să fie corect.

Un astfel de algoritm ar putea, de exemplu, să confirme ipoteza Goldbach și ipoteza Riemann, în ciuda faptului că dovezile (și infirmațiile) nu sunt încă cunoscute. Inrezolvabilitatea problemei de rezoluție (nerezolvabilitatea mulțimii de formule aritmetice adevărate) pentru un limbaj aritmetic care conține „egalitate”, „adunare” și „înmulțire” este o consecință a naturii non-aritmetice a acestei mulțimi. Nonaritmeticitatea este o consecință a teoremei lui Tarski „cu privire la inexprimabilitatea conceptului de adevăr într-o limbă prin intermediul aceluiași limbaj” [1] .

În 1936, Alonzo Church și, în mod independent, Alan Turing au publicat lucrări în care au arătat că nu există un algoritm pentru a determina adevărul enunțurilor în aritmetică și, prin urmare, problema de decizie mai generală nu are nicio soluție. Acest rezultat este cunoscut sub numele de „teorema Bisericii-Turing” .

Vezi și

Note

  1. ↑ V. A. Uspensky , A. L. Semenov Teoria algoritmilor: principalele descoperiri și aplicații, M., Nauka , 1987, 288 p., 2.3 Aplicații la logica matematică: analiza limbajelor formalizate ale logicii și aritmeticii

Literatură