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^[1] e da Alan Turing, indipendentemente, pochi mesi dopo^[2], in due lavori che, insieme, costituiscono le basi per la fondazione della teoria della computabilità.

Note

^ (EN) Alonzo Church, An Unsolvable Problem of Elementary Number Theory, in American Journal of Mathematics, vol. 58, n. 2, The Johns Hopkins University Press, aprile 1936, pp. 345–363. URL consultato il 26 gennaio 2015.
^ (EN) Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (PDF), in Proceedings of the London Mathematical Society, ser. 2, vol. 42, 12 novembre 1936, pp. 230-265. URL consultato il 26 gennaio 2015 (archiviato dall'url originale il 22 dicembre 2014).

Voci correlate

Controllo di autorità	GND (DE) 4253928-6

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] (EN) Alonzo Church, An Unsolvable Problem of Elementary Number Theory, in American Journal of Mathematics, vol. 58, n. 2, The Johns Hopkins University Press, aprile 1936, pp. 345–363. URL consultato il 26 gennaio 2015.

[2] (EN) Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (PDF), in Proceedings of the London Mathematical Society, ser. 2, vol. 42, 12 novembre 1936, pp. 230-265. URL consultato il 26 gennaio 2015 (archiviato dall'url originale il 22 dicembre 2014).

[1]

[2]