Teorema di Matijasevič
Il teorema di Matijasevič, dimostrato nel 1970 da Jurij Vladimirovič Matijasevič, 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.
Descrizione
[modifica | modifica wikitesto]Un sistema tipico di equazioni diofantee assomiglia a questo:
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(x1 − x2)2 − 7(y1 − y2)2(z1 − z2)3 − 18)2 + (−7(y1 − y2)2 + 8(z1 − z2)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 Matijasevič stesso è molto più forte della insolubilità del Decimo Problema. Infatti dice:
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 Matijasevič, 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 Matijasevič è 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 Matijasevič:
- 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 wikitesto]- (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)
