Entscheidungsproblem

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Problema Entscheidungs (în italiană: „problema deciziei”) este o problemă pusă de David Hilbert în 1928 , în cadrul dezbaterii fierbinți de atunci asupra bazelor matematicii . Problema constă în a solicita expunerea unei proceduri, complet executabilă mecanic, capabilă să stabilească, pentru fiecare formulă exprimată în limbajul formal al logicii de ordinul întâi , dacă această formulă este sau nu o teoremă a logicii de ordinul întâi: cu alte cuvinte, dacă sau nu nu această afirmație este deductibilă în cadrul sistemului formal.

Un răspuns negativ la problemă a fost dat de Biserica Alonzo în 1936 [1] și de Alan Turing , independent, câteva luni mai târziu [2] , în două lucrări care, împreună, formează baza fundamentării teoriei calculabilității .

Notă

  1. ^ (EN) Biserica Alonzo , O problemă insolvabilă a teoriei numerelor elementare , în Jurnalul American de Matematică, vol. 58, nr. 2, The Johns Hopkins University Press, aprilie 1936, pp. 345–363. Adus la 26 ianuarie 2015 .
  2. ^ (EN) Alan M. Turing , On Computable Numbers, with a Application to the Entscheidungsproblem (PDF), în Proceedings of the London Mathematical Society, ser. 2 , vol. 42, 12 noiembrie 1936, pp. 230-265. Adus la 26 ianuarie 2015 (arhivat din original la 22 decembrie 2014) .

Elemente conexe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică