Entscheidungsproblem

Da Wikipedia, l'enciclopedia libera.

L'Entscheidungsproblem (in italiano: "problema della decisione") è il secondo dei Problemi di Hilbert, la lista di problemi matematici aperti stilata dal matematico tedesco nel 1900.

Nell'agosto del 1900, il matematico tedesco David Hilbert partecipò al Congresso Internazionale di matematica di Parigi e, nel suo intervento, presentò una lista di problemi che la matematica era chiamata a risolvere. La lista contava ventitré problemi che apparivano, allo stato della matematica di allora, irrisolti. Il secondo di questi problemi era appunto l'Entscheidungsproblem: dimostrare cioè che esiste un algoritmo generale o procedura meccanica in grado di stabilire, per ogni formula di un linguaggio formale, se si tratta oppure no di un teorema, ovvero se è deducibile dagli assiomi. Questa questione coinvolgeva direttamente i fondamenti stessi della matematica.

Una risposta negativa al problema venne data da Alonzo Church nel 1936[1], e da Alan Turing, indipendentemente, nel 1937[2]. Entrambi fecero ricorso a tecniche utilizzate per la prima volta da Kurt Gödel nel suo teorema di incompletezza dell'aritmetica.

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