Entscheidungsproblem
# 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.

Una risposta negativa al problema venne data da Alonzo Church nel 1936 e da Alan Turing, indipendentemente, pochi mesi dopo, in due lavori che, insieme, costituiscono le basi per la fondazione della teoria della computabilità.

