Teorema di Matiyasevich

Da Wikipedia, l'enciclopedia libera.

Il teorema di Matiyasevich, provato 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 suo discorso del 1900 al Congresso Internazionale dei Matematici.

Un sistema tipico di equazioni diofantee assomiglia a questo:

3x²y − 7y²z³ = 18

− 7y² + 8z² = 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(x₁ − x₂)²(y₁ − y₂) − 7(y₁ − y₂)²(z₁ − z₂)³ − 18 )² + ( −7(y₁ − y₂)² + 8(z₁ − z₂)²)² = 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, x₁, ..., x_k) tale che un intero n è in S se e solo se esistono degli interi x₁, ..., x_k tali che f(n, x₁, ..., x_k) = 0.

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

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à è in genere fisicamente implausibile.

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.

[modifica] Bibiliografia

• (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)