INSOLUBILITA’ DEL X
PROBLEMA DI
HILBERT
Tania Notarantonio
Luglio 2002
Il problema diofanteo
Un’equazione diofantea è
un’equazione della forma:
E0(x1,…,xn) = E1(x1,…,xn)
dove
E0 , E1
sono
poly(nomi) a
coefficienti
interi positivi.
poly::=monom|
|monom+monom
monom::=NAT|VAR|
|monom.monom
NAT::=(1|2|…|9)(0|1|2|…|9)*
VAR::=x|y|z|u|v|w|VAR NAT
Un’equazione
diofantea
esponenziale
è
una
equazione
della
forma:
E0(x1,…,xn) = E1(x1,…,xn)
dove E0, E1 sono polinomi
esponenziali (polyexp)
a
coefficienti interi positivi.
polyexp::=monom|
|monom+monom
monom::=NAT|VAR|
|monom.monom|
|monommonom
Esempio
Data l’equazione: (x+2)2 = 1 + 7y2
il cui grafico è il seguente:
Sue soluzioni intere
sono: (-1,0),(-3,0).
-3
-1
0
Ci chiediamo se esistono soluzioni sui
naturali: una breve ricerca rivela che
(6,3) è soluzione intera positiva per
l’equazione data.
Cercare soluzioni intere / naturali sono sottoproblemi del
cercare soluzioni reali ma non per questo risulta
essere più banale.
Il X problema di Hilbert era: trovare un metodo per
determinare se una equazione diofantea data ha
soluzioni su ℤ.
si
E0, E1
ALGORITMO
DI
DECISIONE
no
(u+1)2+
(w+1)2
z2
:questo problema specifica
le terne pitagoriche:
x2 + y2= z2, dove x,y,z > 1
:grazie
al
grande
teorema
di
Fermat
dimostrato nel 1995
L’enigma di Fermat
L’Ultimo teorema di Fermat o “enigma” di Fermat
afferma che non esistono numeri interi positivi
legati dalla relazione:
xn + yn = zn
con n > 2
INDICE
» casi decidibili emblematici
» riduzione del X a ℕ
» idea chiave della dimostrazione di insolubilità:
› insiemi diofantei;
› insiemi diofantei esponenziali;
› insiemi r.e. ( listabili ).
D

E

R
D
?
E
?
R
» insolubilità del X ( gödelizzazione, argom. diagonale )
» questioni aperte
› limitazione alla forma normale di Davis
› ampliamento del X a ℚ
Sottoproblemi classici (risolti) del X.
 equazioni lineari:
ax + by = c
con a, b, c > 0
 equazioni di Pell:
x2 - (b2 - 1) y2 = 1
con b > 0
C.N.S. per la risolubilità di  è che M.C.D(a,b) | c ;
 ha sempre infinite soluzioni.
 ricade come caso particolare nella
dell’aritmetica additiva (Presburger, 1929).
decidibilità
Sia  che  ricadono nella decidibilità di equazioni di 2°
grado.
Riduzione di altri problemi al diofanteo
A. Ogni istanza D(x1,…,xn)=0
del X problema di Hilbert si
può ridurre al problema di
soddisfare una congiunzione
di letterali insiemistici delle
forme:
yz= ø
x=yz
xy
|x| = |y|
x=yz
|x|  |y|
B. Se disponiamo di un
risolutore sugli interi, grazie
al teorema di Lagrange
(1772) possiamo adattarlo
ai naturali sostituendo ogni
incognita xi con la somma:
x²i1 + x²i2 + x²i3 + x²i4 .
Congettura di Martin Davis (1953)
Def.: (rappresentazione diofantea di un insieme S)
Si dice diofanteo un insieme S associato a un polinomio
parametrico diofanteo D come segue:
(a1, … , an)  S 
 x1, … , xm D(a1, … , an, x1, … , xm) = 0
(n si chiama dimensione di S)
Congettura:
le nozioni
diofanteo
di insieme
ricorsivamente enumerabile
si equivalgono
Dalla dimostrazione di questa discese, nel 1970,
l’insolubilità del X problema di Hilbert.
CRESCITA ESPONENZIALE
Paradigma di ricorrenza:
a=bc  a = b(c)
b(0) = 1
b(n+1)=b . b(n)
Varianti:
b(n)
= b(n)
=n
per n = 0,1
b(n+2) = b(n+1) + b . b(n)
b(n+2) = b(n+1) - b . b(n)
n
= 1(n)
[seq. Fibonacci]
La diofantinità di a = bc discende da quella di una delle segg.
relazioni:
v = 2u (1970);
a = b(c) (1970);
a = b(c) (1993)
Ecco il modo in cui Davis (1973) rappresenta
la relazione m = nk con m,n,k > 0:
pell(c,x,y)
Def
x2 - (c2 - 1) . y2 = 1
pell(a,x,y)
pell(a,u,v)
pell(b,s,t)
b>a>1
yk>0
b > 4y
4y | b - 1
v>0
y2 | v
u|b-a
s>x
u|s-x
tk
4y | t- k
( x - y . (a - n) - m)2 = f2 . (2a . n - n2 - 1)2
2a . n - n2 - 1 > m > 0
pell(w,a,(w - 1) . (g + 1))
w>n>0 w>k
Corollari della diofantinità di
m = nk
r.e secondo Turing
 Gli insiemi
diofantei esponenziali
coincidono
. . . diofantei

Per altra via:
• gli insiemi diofantei sono chiusi rispetto
alla quantificazione limitata (y)yx
• le funzioni diofantee sono tutte e sole
le ricorsive.
Gödelizzazione di polinomi - I
poly(N,P) :- natural(N), !,
M is N mod 3, (M==0 -> M1=3; M1=M), I is (N-M1) //3,
(N==0 -> P=1;
M==1 -> name(I,S), [X] = "x", name(P,[X|S])
;
cantor(L,R,I), poly(L,PL), poly(R,PR),
( M==2 -> P=PL+PR; P=PL*PR )).
poly(0,1).
poly(N,Xi) :- atom(Xi), name(Xi,[X|S]), [X]="x",
name(I,S), N is 3*I+1.
poly(N,P+Q) :- poly(L,P),poly(R,Q), cantor(L,R,C),
N is 3*C+2.
poly(N,P*Q) :- poly(L,P),poly(R,Q), cantor(L,R,C),
N is 3*C+3.
Gödelizzazione di polinomi - II
% l'N-simo numero triangolare e`...
triang(N,T) :- natural(N), !, T is (N*(N+1)) // 2.
%…la somma T= 0+1+2+...+N
triang(0,0).
triang(Np1,TT) :- triang(N,T), Np1 is N+1, TT is T+Np1.
cantor(L,R,C) :- natural(L), !, LpR is L+R, triang(LpR,T),
C is T+R.
cantor(L,R,C) :- triang(N,T),
(T==C -> L=N,R=0;
T>C -> R is C-T+N, L is N-1-R), !.
Indicheremo con L(n), R(n) le projez. associate alla
funzione di abbinamento, i.e., cantor(L(n), R(n) , n)
Argomento diagonale contro la risolubilità del X
Ora sappiamo gödelizzare i poly involgenti la sola
costante 1 e, come variabili, le x0 , x1 , x2 ,... :
n | Pn (x0 , x)
Di qui una enumerazione effettiva D0 , D1 , D2 ,…
di tutti i sottinsiemi diofantei di ℕ :
Dn = { x0 |  x PL(n) (x0 , x)= PR(n) (x0 , x)}
Possiamo trovare polynomi
PL(n*) (x0 , x) , PR(n*) (x0 , x)
anche per l’insieme, che si dimostra diofanteo,
{ k | R(k)  DL(k) } (=Dn* )
mentre è, evidentemente, non diofanteo il
 = { h | h  Dh }
-->-->-->
Argomento diagonale contro la risolubilità del X
-->-->-->
Se per assurdo potessimo risolvere il X, allora
avremmo modo di verificare se
R(k)  DL(k) , ossia  x PL(n*) (x0 , x) = PR(n*) (x0 , x)
o no; sarebbero dunque ricorsive la funzione
Dh (x)
(di h ed x) e la
1- D (x)
x
funzione caratteristica di  , che dunque sarebbe
diofanteo, contraddizione.
TEOREMA: indecidibilità forte del X problema
Esistono un polinomio diofanteo V(x0, x1, … ,xm) e una
funzione calcolabile tot. a tali che nessun algoritmo A dia
risposta corretta circa la risolubilità su ℕ dell’equazione
V(a(⌈A ⌉) , x1, … ,xm) = 0 :
A(a(⌈A⌉ ))  ‘SI’
x1, … ,xm ℕ

V(a(⌈A⌉) , x1, … ,xm) = 0
Già la famiglia
V(b, x1, … ,xm) = 0,
con bℕ
di
equazioni
diofantee
è
dunque indecidibile.
Compromesso fra il grado d di V e il numero massimo
m di incognite: l’uno può essere reso più piccolo a
costo di accrescere l’altro. Ecco alcuni record:
(d,m) = (4, 58), (8, 38), ….. , (1.6 . 1045, 9)
Limitazione alla FORMA NORMALE di Davis
La chiusura dei diofantei rispetto ad (y)yx, derivabile
dalla diofantinità di m = nk , era stata individuata come
possibile chiave per rispondere negativamente al X,
grazie alla scoperta di una rappresentazione degli r.e.,
nota come forma normale di Davis:
z (y)yzx1, … , xh P(y,z, x1, … , xh) = 0
Grazie alla diofantinità di m = nk , oggi sappiamo che
h2.
Può essere fissato h=1 ?
X in ambienti numerici diversi da ℕ
Risolvere una equazione:
D(X1,…..,Xm) = 0
nelle X1,…..,Xm su ℚ è equivalente a risolvere
l’equazione:
D((x1-y1)/(z+1),….., (xm-ym)/(z+1)) = 0
nelle incognite x1, y1,…..,,xm, ym, z su ℤ+.
Quest’ultima equazione è equivalente alla seguente
equazione omogenea:
(z+1)dD((x1-y1)/(z+1),….., (xm-ym)/(z+1)) = 0
dove d è il grado del polinomio D.
Due problemi interriducibili:
 stabilire se una equazione diofantea ha soluzione in ℚ;
 stabilire se una equazione diofantea omogenea ha soluzioni non-banali in ℤ.
Le equazioni  sono una sottoclasse delle equazioni
diofantee ed è pertanto possibile che questa sottoclasse
ridotta sia decidibile.
Inteso in senso largo il X problema di Hilbert rimane
ancora aperto.
In senso stretto, così come è stato letteralmente formulato,
risulta chiuso grazie ai contributi di Martin Davis, Hilary
Putnam, Julia Robinson e Yuri Matiyasevič.