Entscheidungsproblem

Da Wikipedia, l'enciclopedia libera.

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, nel 1937[2], in due lavori che, inoltre, costituiscono le basi per la fondazione della teoria della computazione.

Note[modifica | modifica sorgente]

  1. ^ Alonzo Church, An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, 58 (1936), pp 345–363
  2. ^ Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1937), pp 230–265.

Voci correlate[modifica | modifica sorgente]

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