We present details of
the most important
mathematical problem
solved in 1970
Hilbert's 10th Problem
Margaret Davy
In the summer of 1900 at the 2nd International Congress of Mathematicians held in Paris, Hilbert gave a now famous address to his fellow mathematicians. In it he put forward a list of 23 unsolved problems varying in character from the posing of specific questions to the indication of topics which urgently needed further research; by focusing such attention on them he did much to guide as well as to predict future developments. The only decision problem included was the tenth on the list and the formulation of this problem is well known:
Specify a procedure which, in a finite number of steps, enables one to determine whether or not a given diophantine equation with an arbitrary number of indeterminates and with integral coefficients has a solution in rational integers.
In view of the difficulty of finding effective methods for solving particular diophantine equations it seemed most unlikely that there would be an algorithm capable of dealing with an arbitrary diophantine equation. Such an algorithm would indeed cause the disappearance of much number theory research. As an illustration consider the diophantine equation:
y^2 = x^3 + k (a)
Integral solutions can be found for many particular values of k, e.g. it has been proved that (a) has no solution in integers if k=7. There are only a finite number of solutions in integers for (a) (by the Thue-Siegel-Roth theorem) and yet there is no known way of solving it for a general value of k.
A proof that no algorithm of the type specified by Hilbert exists required an approach from mathematical logic rather than from number theory. Hilbert's 10th problem is a decision problem and either a positive or a negative solution must be found.
A positive solution consists of furnishing the required algorithm.
A negative solution consists of proving that no such algorithm can exist and in this case we declare the problem 'unsolvable' in the sense that there is no algorithm for solving it.
The first problem is that of finding a precise mathematical formulation equivalent to our intuitive notion of algorithm. We conceive of an algorithm as being a set of instructions which provide a mechanical procedure for solving a group of related problems. Such instructions are to require no 'creative' thought in their execution, and in principle it is always possible to prepare a program by means of which a digital computer (with arbitrarily large storage facilities) can carry them out.
If a problem can be solved algorithmically it is termed 'effectively calculable' and it was proposed, around 1935, that this idea of effective calculability should be identified with one of a number of precise concepts - those of computability (Turing), lambda-definability (Church), general recursiveness (Herbrand-Godel-Kleene), binormality (Post). All these concepts were well-defined and each seemed to correspond with what we would intuitively regard as an effective process in that field of mathematics. At this time a satisfactory formalisation of the idea of a constructive sequence was being sought, and it was Church who in 1936 first referred to this idea as being that of 'effectively calculable function'. He further suggested that it be identified with the precise notion of 'general recursive function' and this tentative identification has drawn strong support from the fact that the other candidates for identification have proved to to be demonstrably equivalent to each other and to general recursiveness.
We shall use the equivalence of general recursiveness and computability in what follows, and by accepting the identification of these concepts with our idea of effectively calculable we are in a position to treat the decision problem precisely. A few definitions are needed at this stage.
(1) If a Turing machine
with initial tape X1, X2,
... Xn has as its end state the predicate PSIz(X1,
X2, ... Xn ), where
f(X1, X2, ... Xn)
= PSIz(X1, X2,
... Xn) and X1, X2,
... Xn are
integers,
we say that the function f is partially computable. If f is also
a total function (i.e. its domain is the set of all n-tuples) then f is
computable.
(2) A set is said to be computable if its characteristic function is computable. (f(x) = 1 if and only if x belongs to A, the set.)
(3) A function is recursive iff (if and only if) it is computable and a set is recursive iff its characteristic function is recursive or computable.
(4) A function is partial recursive iff it is partially computable.
By turning to look at the class of non-computable predicates and in particular semi-computable predicates we can establish the well-known result that there exist recursively enumerable sets which are not recursive.
(5) A predicate P(X1, X2, ... Xn) is semi-computable if there exists a partially computable function whose domain is the extension of P. i.e. {(X1, X2, ... Xn); P(X1, X2, ... Xn)}.
Using the theorem that a predicate R(X1, X2, ... Xn) is computable iff both R(X1, X2, ... Xn) and R(X1, X2, ... Xn) are semi-computable, we can now furnish a example of a semi-computable predicate which is not computable.
Consider the predicate T(Z, X1, X2, ... Xn, Y) (n>0) defined by 'Z is the Godel number of a Turing machine, Z, and Y is the Godel number of a computation with respect to Z beginning with initial tape X1, X2, ... Xn. We have the theorem that if R(X1, X2, ... Xn) is a semi-computable prealcate, then there exists some Z0 such that
R(X1, X2, ... Xn) <---------------> Exists Y Tn(Z0, X1, X2, ... Xn, Y) (b)
The predicate Exists Y; Tl(x, x, y) is semi-computable, ~Exists Y; Tl(x, x, y) is not. For, suppose ~Exists Y; Tl(x, x; y) were semicomputable, then by (b), we get
~Exists YTl(x, x, y) <---------------> Exists Y T1(Z0, X, Y)
Setting x = z0 yields a contradiction.
Now the study of semicomputable predicates is effectively that of the domains of partially computable functions and we can get essentially the some results by studying their ranges instead.
(6) A set is called recursively enumerable if it is the extension of a semicomputable predicate, thus:
K = {x; Exists yT1(x,x,y)} is recursively enumerable.
We have seen that Exists yT1(x,x,y) is not computable and so it is not recursive and so we have an example of a recursively enumerable set which is not recursive.
We shall now turn to another aspect of the problem and to the work of Julia Robinson. A relation p(X1, X2, ... Xn ) is existentially definable in terms of O1, O2, ...Ok if there exists an equivalence
p(X1, ... Xn )<-----> Exists U1 Exists U2 ... Exists Um PSI (X1, ... Xn, U1, ... Um) (c)
where PSI is an expression composed of the free variables X1, ... Xn, the bound variables U1, ... Un, the logical connectives &, V, =, and and O1, ...Ok and the symbols for particular natural numbers where O1, ... Ok are relations or operations.
If in addition Ok itself is existentially definable in terms of O1, ...Ok-1 then P(X1, ... Xn) is existentially definable in terms of O1, ...Ok-1 only. (d)
A solution to a diophantine equation would normally be a solution in integers but here we have restricted ourselves deliberately to the natural numbers. We may continue to do this because the problem of finding an algorithm to determine the solutions of a diophantine equation in integers is equivalent to that of finding an algorithm to determine natural number solutions.
As a particular case of (c), P(X1, ... Xn) is existentially definable in terms of addition and multiplication if there in an equivalence
p(X1, ... Xn )<-----> Exists U1 Exists U2 ... Exists Um PSI (X1, ... Xn, U1, ... Um)
where PSI is composed of X1, ... Xn, U1, ... Um, &, V, =, +, . , and symbols for natural numbers. Such a relation is diophantine. Similarly a set of natural numbers, S, is called diophantine iff there exists an equivalence
s belongs to S <---------> Exists U1 Exists U2 ... Exists Um (P(v, U1, ... Um) = 0)
where P is a polynomial with integral coefficients. P(s, U1, ... Um) = 0 is a diophantine equation.
A set R of natural numbers is exponential diophantine (i.e. existentially definable in terms of addition, multiplication and exponentiation) if and only if there exists an equivalence
v belongs to R <--------> Exists U1 Exists U2 ... Exists Um (E(v, U1, ... Um) = 0)
where E is a linear combinrtion with integral coefficients of products of terms of the form alpha to the beta where alpha, beta are various or particular natural numbers. E(v, U1, ... Um) = 0 is an exponential diophantine equation.
The following result was obtained by Julia Robinson (3)
THEOREM
The relation given by x = y^z is existentially definable in terms of
addition, multiplication and any relation o(u, v) satisfying the following
two conditions:
(J1) For some n, o(u,v) implies that v <u*n
(J2) There is no n such that o(u,v): implies v < u^n where
'the nth superpower of n', x*n is defined recursively:
x*0 = 1
x*(n+l) = x^(x*n)
(These two conditions ensure that o(u,v) has roughly exponential growth)
The importance
of this theorem lies in its application to 'bridging the gap' between
a diophantine and an exponential diophantine set. x = y^z is existentially
definable in terms of addition, multiplication and exponentiation, but
by the above theorem it is also existentially definable in terms of
addition, multiplication and o(u, v). Now suppose that a o(u,v) could
be found which was itself diophantine, then by (d) the existential definition
of x = y^z could be made using addition and multiplication alone i.e.
x = y^z would be diophantine.
From the work of Davis, Putnam and Robinson (2) we have:
THEOREM
Every recursively enumerable set is exponential diophantine.
An a corollary of this theorem we have that there is no general algorithm for determining whether or not a given exponential diophantine equation is solvable. For we know that there are recursively enumerable sets which are not recursive and so there will be some non-recursive set H of positive integers which can be expressed (by the above theorem) in the form
n belongs to H <--------> Exists U1 Exists U2 ... Exists Um (N(n, U1, ... Um) = 0)
N=0 is an exponential diophantine equation. H is the set of values of the parameter n for which N=0 is solvable.
If there were an algorithm for determining the solutions of exponential diophantine equations, we would be able to determine whether N = 0 was solvable for a given value of n, say n0 and heonce whether n0 belongs to H. As H is non-recursive this is not possible in general and so there can be no such algorithm.
Now suppose a o(u,v) satisfying (J1) and (J2) and also being a diophantine could be found. We could use the fact that x = y^z is diophantine to transform mechanically every exponential diophantine equation into an ordinary diophontine equation with more variables. The corollary just derived would then apply to diophantine equations and we could immediately say that there is no algorithm for determining whether or not an arbitrary diophantine equation isn solvable.
Matijasevic's
contribution consisted of finding just such a o(u,v). He considered
the predicate P(u,v) which he defined by 'v is the 2u-th Fibonacci
number'. He used for his conditions of roughly exponential growth:
(M1) P(u,v) implies that v <= u^u
(M2) For each k there exists u, .v such that P(u, v) and u^k
< v.
It caneasily be shown that any predicate satisfying (M1) and (M2) will automatically satisfy (J1) and (J2) and that P(u, v) does in fact satisfy (MI) and (M2). The major part of Matijasevic's paper (2) is devoted to the proof that P(u, v) is diophantine. The main result is:
THEOREM
In order for v to be the 2u-th Fibonacci number it is necessary and
sufficient that there exist numbers g, h, l, m, x, y, z such that:
(1) u <=
v <= 1
(2) l^2 - lx -z^2 = 1
(3) g^2 -gh -h^2 = 1
(4) l^2 divides g
(5) 1 divides (m-2)
(6) (2h+g) divides (m - 3)
(7) x^2 - mxy + y^2 = 1
(8) l divides (x-u)
(9) (2h+g) divides (x - v)
The conditions (1) to (9) could be transformed mechanically into a single diophantine predicate which would define P(u, v) existentially.
Thus x=y^z is diophantine and the proposed transformation of exponential diophantine equations into ordinary diophantine equations can now be carried out, and it follows that Hilbert's Tenth Problem is unsolvable.
REFERENCES
AND BIBLIOGRAPHY
1 Davis, Putnam
and Robinson: Annals of Math. vol 74,3, Nov.1961.
2 Matijasevic: Enumerable sets are diophantine. Soviet Math.Dok.
vol 2 1970, no.2.
3 J.Robinson: Tran.A.M.S. 72(1952), 437-449.
4 M.Davis Computability and Unnolvability.