Universal Equations

One of the fundamental notion in Computability Theory is that of universal Turing machine or, equivalently, its counterpart universal listable set. Now the DPRM- theorem brings the idea of such kind of universality into the realm of Diophantine equations. Namely, for every fixed n, we can construct a particular Diophantine equation

which is universal in the following sense: solving an arbitrary Diophantine equation with n parameters

is equivalent to solving the equation

resulting from the Eq. (2.28) by choosing a particular value kD for the first parameter, that is, for this fixed value of k and for any choice of the values of the parameters a,...,am either both of the Eqs. (2.29) and (2.30) have a solution or neither of them has any.

What is remarkable in this reduction of one equation to another is the following: the degree and the number of unknowns of the Eq. (2.30) is fixed while the Eq. (2.29) can have any number of unknowns and be of arbitrarily large degree. This implies that hierarchies of Diophantine equations traditional for Number Theory (with 1, 2, 3, „.unknowns; of degree 1, 2, 3,...) collapse at some level.

Not only number-theorists never anticipated universal Diophantine equations, their possibility was incredible even for some logicians as it can be seen from the review in Mathematical Reviews on the celebrated paper by Martin Davis, Hilary Putnam, and Julia Robinson [14].

We can look at universal Diophantine equations as a purely number-theoretical result inspired by Computability Theory. But do we really need the general notion of listable sets for proving the existence of universal Diophantine equations or could we construct such equations by purely number-theoretical tools? In my book [37] I managed to prove the existence of universal Diophantine equations before proving the DPRM-theorem; in [41] I introduced another purely number-theoretical construction of universal Diophantine equations.

 
Source
< Prev   CONTENTS   Source   Next >