Teorema di Matijasevič

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Teorema di Matiyasevich)

Il teorema di Matiyasevich, dimostrato nel 1970 da Yuri Matiyasevich, implica che il decimo problema di Hilbert è irrisolvibile. Il problema richiede la costruzione di un algoritmo generale che sia in grado di stabilire se un dato sistema di equazioni diofantee (polinomi a coefficienti interi) ha soluzioni intere. David Hilbert ha posto il problema durante il suo discorso del 1900 al Congresso Internazionale dei Matematici.

Un sistema tipico di equazioni diofantee assomiglia a questo:

3x2y − 7y2z3 = 18
− 7y2 + 8z2 = 0

Il problema è stabilire se esistono degli interi x, y e z che soddisfano entrambe le equazioni simultaneamente. Si vede che questo problema è equivalente a quello di stabilire se una singola equazione diofantea in più variabili ha soluzioni nell'insieme dei numeri interi. Ad esempio, il sistema precedente è risolvibile negli interi se e solo se la seguente equazione è risolvibile nell'insieme dei numeri naturali:

(3(x1x2)2(y1y2) − 7(y1y2)2(z1z2)3 − 18)2 + (−7(y1y2)2 + 8(z1z2)2)2 = 0.

Matiyasevich ha usato un trucco ingegnoso che coinvolge i numeri di Fibonacci per mostrare che le soluzioni delle equazioni diofantee possono crescere esponenzialmente. I lavori precedenti di Julia Robinson, Martin Davis e Hilary Putnam hanno mostrato che questo è sufficiente a mostrare che non può esistere nessun algoritmo capace di decidere la risolubilità delle equazioni diofantee.

Lavori successivi hanno mostrato che il problema della risolubilità è indecidibile anche se l'equazione ha solo 9 variabili naturali (Matiyasevich, 1977) o 11 variabili intere (Zhi Wei Sun, 1992).

Il teorema di Matiyasevich stesso è molto più forte della insolubilità del Decimo Problema. Infatti dice:

Ogni insieme ricorsivamente enumerabile è diofanteo.

Un insieme S di interi è ricorsivamente enumerabile se esiste un algoritmo che si comporta nel seguente modo: dato come input un intero n, se n è un elemento di S, allora l'algoritmo alla fine termina; altrimenti non termina mai. questo è equivalente a dire che esiste un algoritmo che non termina mai e che elenca gli elementi di S. Un insieme S è diofanteo se esiste un certo polinomio a coefficienti interi f(n, x1, ..., xk) tale che un intero n è in S se e solo se esistono degli interi x1, ..., xk tali che f(n, x1, ..., xk) = 0.

Non è difficile vedere che ogni insieme diofanteo è ricorsivamente enumerabile: si consideri una equazione diofantea f(n, x1, ..., xk) = 0. Ora costruiamo un algoritmo che semplicemente prova tutti i possibili valori per n, x1, ..., xk e scrive n ogni volta che f(n, x1, ..., xk) = 0. Questo algoritmo ovviamente non termina mai ed elenca esattamente gli n per i quali f(n, x1, ..., xk) = 0 ha una soluzione in x1, ..., xk.

Il teorema di Matiyasevich, insieme a un risultato scoperto negli anni 1930 implica che la soluzione al decimo problema di Hilbert è impossibile. Il risultato scoperto negli anni 1930 da molti logici si può formulare nel seguente modo: "esistono insiemi ricorsivamente enumerabili non ricorsivi". In questo contesto, un insieme S di interi è detto "ricorsivo" se esiste un algoritmo che, dato come input un intero n, ritorna come output una risposta si/no corretta alla domanda: "n è un elemento di S?" Da questo segue che esistono equazioni diofantee che non possono essere risolte da nessun algoritmo, a meno che non si possa costruire un ipercomputer (Kieu, 2003); comunque questa possibilità è ritenuta generalmente non implausibile fisicamente.

Il teorema di Matiyasevich è stato usato successivamente per provare l'insolubilità di molti problemi riguardanti l'analisi e le equazioni differenziali.

Si può anche derivare la seguente forma (più forte) del teorema di incompletezza di Gödel dal risultato di Matiyasevich:

Per ogni assiomatizzazione data della teoria dei numeri è possibile costruire esplicitamente una equazione diofantea priva di soluzioni, ma tale che questo fatto non si può provare all'interno dell'assiomatizzazione data.

Bibliografia[modifica | modifica sorgente]

  • (EN) Y. Matiyasevich. "Enumerable sets are Diophantine." Doklady Akademii Nauk SSSR, 191, pp. 279-282, 1970. Traduzione inglese in Soviet Mathematics. Doklady, vol. 11, no. 2, 1970.
  • (EN) M. Davis. "Hilbert's Tenth Problem is Unsolvable." American Mathematical Monthly 80, pp. 233-269, 1973.
  • (EN) T. Kieu. "Quantum Algorithm for the Hilbert's Tenth Problem", Int. J. Theor. Phys. 42, pp. 1461-1478, 2003. e-print archive quant-ph/0110136 (PDF)


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