Teorema Matijasevič
Teorema lui Matijasevič , demonstrată în 1970 de Jurij Vladimirovič Matijasevič , implică faptul că a zecea problemă a lui Hilbert este de nerezolvat. Problema necesită construirea unui algoritm general care să poată stabili dacă un sistem dat de ecuații diofantine ( polinoame cu coeficienți întregi ) are soluții întregi . David Hilbert a pus problema în timpul discursului său din 1900 la Congresul internațional al matematicienilor.
Descriere
Un sistem tipic de ecuații diofantine arată astfel:
Problema este dacă există numere întregi x , y și z care satisfac ambele ecuații simultan. Vedem că această problemă este echivalentă cu cea a stabilirii dacă o singură ecuație diofantină în mai multe variabile are soluții în setul de numere întregi . De exemplu, sistemul anterior este rezolvabil în numere întregi dacă și numai dacă următoarea ecuație este rezolvabilă în setul numerelor naturale:
- (3 ( x 1 - x 2 ) 2 - 7 ( y 1 - y 2 ) 2 ( z 1 - z 2 ) 3 - 18) 2 + (−7 ( y 1 - y 2 ) 2 + 8 ( z 1 - z 2 ) 2 ) 2 = 0.
Matiyasevich a folosit un truc ingenios care implică cifre Fibonacci pentru a arăta că soluțiile ecuațiilor diofantine pot crește exponențial . Lucrările anterioare ale Julia Robinson , Martin Davis și Hilary Putnam au arătat că acest lucru este suficient pentru a arăta că nu poate exista un algoritm capabil să decidă solvabilitatea ecuațiilor diofantine.
Lucrările ulterioare au arătat că problema solvabilității este indecidabilă chiar dacă ecuația are doar 9 variabile naturale (Matiyasevich, 1977) sau 11 variabile întregi ( Zhi Wei Sun , 1992).
Teorema lui Matijasevich în sine este mult mai puternică decât insolubilitatea celei de-a zecea probleme. De fapt, el spune:
- Fiecare set recursiv enumerabil este diofant .
Un set S de numere întregi este recursiv enumerabil dacă există un algoritm care se comportă după cum urmează: dat un număr întreg n ca intrare, dacă n este un element al lui S , atunci algoritmul se termină în cele din urmă; altfel nu se termină niciodată. acest lucru este echivalent cu a spune că există un algoritm care nu se termină niciodată și care listează elementele lui S. Un set S este diofant dacă există un anumit polinom cu coeficienți întregi f ( n , x 1 , ..., x k ) astfel încât un număr întreg n este în S dacă și numai dacă există numere întregi x 1 , ..., x k astfel încât f ( n , x 1 , ..., x k ) = 0.
Nu este dificil să vedem că fiecare mulțime diofantină este recursiv enumerabilă: ia în considerare o ecuație diofantină f ( n , x 1 , ..., x k ) = 0. Acum să construim un algoritm care testează pur și simplu toate valorile posibile pentru n , x 1 , ..., x k și scrie n ori de câte ori f ( n , x 1 , ..., x k ) = 0. Acest algoritm evident nu se termină niciodată și listează exact n pentru care f ( n , x 1 , ..., x k ) = 0 are o soluție în x 1 , ..., x k .
Teorema lui Matijasevič, împreună cu un rezultat descoperit în anii 1930 implică faptul că soluția la a zecea problemă a lui Hilbert este imposibilă. Rezultatul descoperit în anii 1930 de mulți logicieni poate fi formulat după cum urmează: „există recursiv enumerabile seturi nerecursive”. În acest context, un set S de numere întregi este declarat a fi „recursiv“ în cazul în care există un algoritm care, având în vedere un număr întreg n ca intrare, se întoarce ca ieșire corectei da / nici un răspuns la întrebarea: „este n un element de S ? " Din aceasta rezultă că există ecuații diofantine care nu pot fi rezolvate de niciun algoritm, decât dacă se poate construi un hipercomputer (Kieu, 2003); cu toate acestea, această posibilitate este în general considerată neplauzibilă din punct de vedere fizic.
Teorema lui Matijasevič a fost folosită mai târziu pentru a dovedi insolubilitatea multor probleme legate de analiză și ecuații diferențiale .
De asemenea, putem obține următoarea formă (mai puternică) a teoremei incompletitudinii lui Gödel din rezultatul lui Matijasevič:
- Pentru orice axiomatizare dată a teoriei numerelor este posibil să se construiască în mod explicit o ecuație diofantină fără soluții, dar astfel încât acest fapt să nu poată fi dovedit în cadrul axiomatizării date.
Bibliografie
- ( EN ) Y. Matiyasevich. „Seturile nenumărate sunt diofantine”. Doklady Akademii Nauk SSSR, 191, pp. 279-282, 1970. Traducere în limba engleză în matematica sovietică. Doklady, vol. 11, nr. 2, 1970.
- ( EN ) M. Davis. „A zecea problemă a lui Hilbert este de nerezolvat”. American Mathematical Monthly 80, pp. 233-269, 1973.
- ( EN ) T. Kieu. „Algoritmul cuantic pentru a zecea problemă a lui Hilbert”, Int. J. Theor. Fizic. 42, pp. 1461-1478, 2003. e-print archive quant-ph / 0110136 ( PDF )
