Non-effectivizable Estimates

Suppose that we have an equation

which for every value of the parameter a has at most finitely many solutions in x,...,xn. This fact can be expressed in two form:

  • • Equation (2.33) has at most v(a) solutions;
  • • in every solution of (2.33) xi < a (a), xn < a (a)

for suitable functions v and a.

From a mathematical point of view these two statements are equivalent. However, they are rather different computationally. Having a(a) we can calculate v(a) but not vice versa. Number-theorists have found many classes of Diophantine equations with computable v(a) for which they fail to compute o(a). In such cases number-theorists say that “the estimate of the size of solutions is non-effective”.

Now let us take some undecidable set M and construct an exponential Diophantine equation

giving a single-fold representation for M. Clearly, Eq. (2.34) has the following two properties:

  • • for every value of the parameter a,Eq. (2.34) has at most one solution in x1, ...,xn;
  • • for every effectively computable function о there is a value of a for which the Eq. (2.34) has a solution x1,...,xn such that max{x1, ...,xn} > о (a) (otherwise we would be able to determine whether a belongs to M or not).

In other words, the boundedness of solutions of equation (2.34) cannot be made effective in principle. This relationship between undecidability and non- effectivizability is one of the main stimuli to improve the DPRM-theorem to singlefold (or at least to finite-fold) representations and thus establish the existence of non-effectivizable estimates for genuine Diophantine equations.

< Prev   CONTENTS   Source   Next >