Teorema Matijasevič
Teorema lui Matijasevic, demonstrată în 1970 de Yuri Matiyasevich , implică faptul că a zecea problemă a lui Hilbert este de nerezolvat. Problema necesită construirea unui algoritm general care să poată determina 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 de a determina dacă există numere întregi x, y și z care satisfac ambele ecuații simultan. Se vede că această problemă este echivalentă cu determinarea dacă o singură ecuație diofantină din 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ă determine 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 Diofantin .
Un set de numere întregi S este recursiv enumerabil dacă există un algoritm care se comportă în modul următor: dat ca intrare un număr întreg n, dacă n este un element al lui S, atunci algoritmul se termină la sfârșit; 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 diofantin 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 greu de văzut că fiecare mulțime diofantină este recursiv enumerabilă: ia în considerare o ecuație diofantină f (n, x 1, ..., x k) = 0. Acum construim un algoritm care încearcă pur și simplu toate valorile posibile pentru n, x 1 , ..., x k și scrie n de fiecare dată când 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 Matijasevic, î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 se numește „recursiv” dacă există un algoritm care, dat ca intrare un număr întreg , returnează ca ieșire un răspuns corect da / nu la întrebarea: „n este un element al lui S?” Din aceasta rezultă că există ecuații diofantine care nu pot fi rezolvate de niciun algoritm, cu excepția faptului că nu puteți construi un ipercomputer (Kieu, 2003); cu toate acestea, această posibilitate este în general considerată neplauzibilă din punct de vedere fizic.
Teorema Matijasevic a fost folosită ulterior pentru a demonstra insolubilitatea multor probleme referitoare la „ analiza și ecuațiile diferențiale .
De asemenea, poate rezulta în următoarea formă (mai puternică) a teoremei incompletei Godel din rezultatul lui Matijasevic:
- 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 engleză în matematică 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 )
