Entscheidungsproblem

L'Entscheidungsproblem (in italiano: "problema della decisione") è un problema posto da David Hilbert nel 1928, all'interno dell'allora fervente dibattito sui fondamenti della matematica. Il problema consiste nel chiedere di esibire una procedura, eseguibile del tutto meccanicamente, in grado di stabilire, per ogni formula espressa nel linguaggio formale della logica del primo ordine, se tale formula è o meno un teorema della logica del primo ordine: in altri termini, se tale enunciato è o meno deducibile all'interno del sistema formale.