Computation and Computability of Hilbert’s Tenth Problem

Introduction

What is the 10^th Problem?

Computer and these Problems

Introduction

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 are:

· 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 solutions?

· And many more!! Like the above have really given headaches to most of mathematicians and philosophers.

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 problems.

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.

The question 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 + z² = 15, 5x² + 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

X⁴ + y⁴ = 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

Fermat’s Principle

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

xⁿ + yⁿ = zⁿ

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 quite different.

Euler Equations

In 1769 the Swiss Mathematician Euler conjectured that the equation

x⁴ + y⁴ + z⁴= w⁴

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.

Example problems 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 + y2 = 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.

Algorithms

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 task.

Turing Machine

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.

Computation

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.