Computation and Computability of Hilbert’s Tenth Problem
What is the 10th Problem?
Similar to the Problem
Computer and these Problems
Mathematics would seem to be one of
the most fascinating fields of human knowledge. Hardly have you found an area of science that mathematics plays no role. The
raw material and core of mathematics are numbers. The numbers have been invented by human to represent and model natural philosophy
of the logic in which how universe behaves. Numbers are means human use to reach reality. Since the invent of numbers thousands
of years ago, they have always created conceptual ambiguities and major problems for most of intellectuals and philosophers.
Numbers have become a way and method
for communication between human and nature, despite the fact that numbers may not represent an absolute reality on their own
but still they seem provide a better means of the way we can understand nature. Numbers not only establishes communication
between nature and us, they also realise the communication between us.
Numbers have not seemed to be only
staying in their abstract form, mathematicians have been able to translate and interpret them to geometry, philosophy, theology,
and etc. each group would find the meaning of numbers in their own ways. On the
other hand numbers have also created problems for each group, each on their way. Some of those problems still exist nowadays
and there are debates among these intellectuals and there still un answerable questions! Some of examples on these problems
What is zero and infinity? Do numbers still continue at both edges of the micro universe
and macro universe?
Dose prime have an upper bound? Is there the maximum prime number?
Is really p an irrational number?
What is the proportion of irrational numbers to the rational numbers?
Why are not there compact solutions for polynomial equations higher than order 4?
Is there any rule or algorithm predicting that a set of simultaneous equations has integer
And many more!! Like the above have really given headaches to most of mathematicians
But the question is whether advances
in technology and particularly computers will be able one day to set a universal rule for solving any of similar to the above
What is the Tenth Problem
In August 1900 the world's best mathematicians
gathered in Paris for the Second International Congress of Mathematicians. One of the participants in
the conference was the 38-year-old mathematician from the University of Gbttingen, David Hilbert in Germany.
He was known to be one of the leading mathematicians of the time. Hilbert was due to deliver one of the keynote addresses
to the meeting. The day fixed for his lecture was 8 August.
As the meeting was being held in the very first year of the twentieth century, Hilbert chose to
use his lecture not to look back over some recent work, but rather to point the way towards the future.
of whether the Hilbert’s tenth problem was discovered by Hilbert, the answer is no. Around AD 250 a mathematician named
by Diophantus referred to such problem.
What are Diophantus
equations? Simply Diophantus equations are polynomial equations in any number of variables, where the coefficient of the equations
are integers (.. –3,-2,-1,0,1,2..) an example on this system is:
2xy + y + z2
= 15, 5x2 + y –z = 4
The above equations
have a set of integer solution as x = 1, y = 2, z = 3.
The Hilbert’s problem now is to find some procedure, algorithm or computational method to tell that the Diophantus
equations have common solutions. The main problem is knowing the coefficients and the polynomial powers including the parameters
(x, y, z, . .) how one can tell if the sets have the same solutions. More difficult version of that is if the solutions are
integer. In some simple cases that could be easy, for example the equation
X4 + y4 = 5
has infinite number of real solution while non can be integers. The proof of that may not be difficult as if we assume
one of the unknown as integer and substitute back into the equation it will be proved impossible that the other unknown is
integer too. But certainly this cannot be converted into a general algorithm.
From the mathematics point of view this tenth problem is important because historically the exact statement of the
problem had not been mentioned and secondly what is the concept of algorithm here in this case? This point will be discussed
in the following sections.
We should note that Hilbert did not ask directly if there was an algorithm to determine whether a given set of Diophantine
equations have some solutions. Rather, he asked for such an algorithm to be produced.
Similar to the Problem
One of the famous problems in mathematics in which it has some similarity in the integer possible solution is Fermat’s
principle. the principle states that for the equation
xn + yn = zn
if n > 2 there is no integer solutions.
In 1993 after few years’ research and investigation a mathematician from Cambridge University after almost 300 years
on the principle he arrived to a conclusion why there are no integer solution. However the case with the Tenth Problem is
In 1769 the Swiss Mathematician Euler conjectured that the equation
x4 + y4 + z4 = w4
has no integer solutions. Since 60’s computer solutions have been attempted until 1987 in which the first set
was found and later on a second set which is as the following:
x = 95800, y = 217519, z =414560 and w = 422481
Diophantine Analysis, in mathematics, this is a branch of number theory concerned with determining the solutions in integers of algebraic equations
with two or more unknowns. Such problems were treated by Greek mathematicians including Pythagoras and Diophantus.
in Diophantine analysis would be to find two integers such that the sum of their squares is a square (3 and 4, or 5 and 12);
or two integers such that the sum of their cubes is a square (1 and 2); or three integers such that their squares are in arithmetic
progression (1, 5, and 7). In algebraic terms, the three examples call for integers x, y, and z
such that x2 +
z2; x3 + y3 = z2; and x2 + z2 = 2y2,
respectively. Usually an attempt is made to determine if a problem has no solutions at all, or whether it has a finite or
infinite number of solutions. Recent approaches to problems of this sort involve the use of high-speed computers to find solutions
or to establish counterexamples to the original problem.
A Persian mathematician called al-Khowarizimi in AD 825 wrote a book outlining the rules for performing basic
arithmetic using numbers (with columns for units, tens, hundreds, and so on, and decimal points to denote fractional quantities).
From his name comes the modern word 'algorithm'.
An algorithm is a step-by-step method for performing some kind of calculation.
Nowadays Algorithm has become so important to computers i.e. a way to instruct computers to perform tasks. To the mathematicians
exactly how the instructions are written down or specified is not important. The important point is that the instructions
should be complete and unambiguous, with no room for choice or chance and should work for all possible starting data, not
just particular values. The usual Euclidean Algorithm is a good example for that.
The tenth problem asks if there is an algorithm to determine whether a given Diophantus
equation has a solution. For some special cases of Diophantine equations such as linear and quadratic equations in at most
two unknowns, there are algorithms, while for higher case there are not. But is there an algorithm which works in all cases?
If the answer is yes. then in order to prove this it would be enough to write down the appropriate algorithm. But supposing
the answer is no. How do you set about proving that? The notion of a 'step-by-step instruction set', whilst adequate for recognizing
a specific algorithm as such, is altogether too vague to enable us to prove that there is no algorithm for performing a certain
Firstly Turing machine is a hypothetical computing device that provides the concept
and idea of computation. The machine is so simple; the status of a cell on its tape is either 0 or 1. As a result this machine
can work any computation however complicated.
The overall behaviour of the machine is determined by an instruction
set which says - for each state and each possible symbol read - exactly which three actions should be performed.
In terms of a Turing machine, an algorithm consists of a sequence of instructions
that determines the behaviour of the machine in the manner indicated before. Obviously with such a very simple machine even
the most basic calculation will require some detailed 'algorithm' . But the whole point of the concept is that it provides
a precise definition of an algorithm and of a computation which is simple enough to be handled mathematically and yet
which is adequate for performing any 'algorithmic calculation'. In a more realistic way it is not suggested that such a device
should made in a real world.
An important point in the way we understand the solution of Hilbert's
tenth problem is that of a computable set of integers. Let us assume this set as S which is a set of integers
for which there is an algorithmic method of determining which numbers are in S and which are not. In terms of a Turing
machine, a set S of integers is said to be computable if there is a Turing machine program which, given any
integer as input, halts with an output of 1 if the integer is a member of S and stops with an output of 0 if the integer
does not belong to S. an example on that is the set S of even integers is computable.
Notice that in the above definition of a computable set the Turing machine program
produces an answer for every input - it cannot, as so often occurs with real programs running on real computers, go into an
infinitely recurring loop or start a never-ending search for some data item that does not exist. A weaker notion, that allows
for such 'unending calculations', is that of a listable set of integers (known to mathematicians as a recursively
enumerable set). In terms of a Turing machine, a set S of integers is said to be listable if there is a
Turing machine program which, given any integer as input, stops with an output of 1 if, and only if, the integer belongs to
S. if the input integer does not belong to S, the program may halt with output 0 or it may not halt at all. Thus if
you run the program on a given input integer N, if it happens that N is a member of S then eventually
the program will tell you so. But if N is not a member of S, you might never find this out - the calculation might
go on for ever, though you could never be sure that it was not just about to stop. So it is a very one-sided situation.
As you might imagine, there is a close relationship between
the two notions of a computable set and a listable set. A set S of integers is computable if, and only if, both S and
S’ are listable, where S’ is the complement of S. It is fairly easy to see why this
is so. If S is computable. then any program P that testifies to this fact will also testify the listability of S,
and to obtain a program which shows that S is listable, take the program P and add a final step which replaces an output of 0 by 1, and an
output of 1 by 0. Conversely, if both S and S’ are listable, then to obtain a program showing that S is computable,
proceed as follows.
Let P and Q be programs which give the listability of S and S’, respectively.
If you now take two Turing machines, one running program P and the other Q, and if you feed a given Integer N simultaneously
into both machines, then If N is a member of S the program P will eventually halt with output 1, and if N
is a member of S’ the program Q will eventually halt with output 1. So taken together, the two Turing machines
give you a mechanical way of deciding whether a given integer Is In S or not. Intuitively this tells you that S
is computable. To make It precise in terms of the definitions. you have to construct just one Turing machine program that
does the job of the two programs P and Q. An obvious way is to write a program R which, for a given integer input, alternately
runs P and Q on that input (say 100 steps of each. in turn) until one of these halts with output 1. If It is the P part that
does this, then R outputs 1 and halts, if it is the Q part then R outputs 0 and halts. Obviously. program R will testify to
the computability of S.
Turing reached to an important conclusion; there are certain classes of problem that
do not have any algorithmic solutions. One example of that is Tiling problem.
Computer and these Problems
One sometimes may thing that computer can solve these problems. But certainly if the
algorithm is not known or does not exist at all computers can also find it difficult. However, there may be another way in
which one writes a program that can test variety of number, integer, possibilities until the solution is obtained if any.
In practice we will face a number of problems with this method such as:
The time factor, it will require a long time exceeding 100’s of hours even with
super computers. Indeed the computer does not get bored or tired but we may give up.
The space problem with mainly the memory.
The third one which could be the most important one; the address location for storing
numbers in computers however is powerful is limited and holding integers in them is impossible. Any number higher than that
will be represented in exponent or round format. As a result the solution will be lost. For example a powerful PC spreadsheet
can take up to 16-digit integer, for super computers this will be more higher but still is limited. What about if in reality
there is a solution which is some figures larger than any address the computer can hold!! Of course it will not be reached.