Entscheidungsproblem
Definizione rapida
L'Entscheidungsproblem è il problema della decisione formulato dal matematico tedesco David Hilbert.
Spiegazione
La questione chiede di definire una procedura rigorosa, espressa in un linguaggio formale deduttivo, capace di eseguire automaticamente una dimostrazione. L'idea è quindi vicina a quella di algoritmo.
Esempio pratico
Si cerca un procedimento meccanico che, ricevuta una formulazione logica, stabilisca attraverso passaggi formali l'esito della dimostrazione.
Spiegazione tecnica
Il requisito di automaticità impone regole precise e applicabili senza intuizioni esterne. Per questo il problema collega logica formale e nozione di procedura algoritmica.
Da non confondere con
Una dimostrazione è il risultato logico; l'Entscheidungsproblem domanda l'esistenza di una procedura generale per produrla automaticamente.