Other Impossibilities

DPR-theorem and DPRM-theorem turned out to be very powerful tools for establishing that many other things cannot be done algorithmically. Only a few examples will be mentioned here, surveys of many others can be found, for example, in [37, 40].

The Number of Solutions

In his tenth problem Hilbert demanded to find a method for deciding whether a given Diophantine equation has a solution or not. But one can ask many other similar questions, for example:

  • • is the number of solutions of a given Diophantine equation finite or infinite?
  • • is the number of solutions of a given Diophantine equation odd or even?
  • • is the number of solutions of a given Diophantine equation a prime number?

Martin Davis showed in [9] that Hilbert’s tenth problem can be reduced to the above and analogous decision problems, and hence all of them are undecidable. Namely, the following theorem holds.

Theorem (Martin Davis). Let N = {0, 1, 2,..., to) and let M be a proper subset of N; there is no algorithm for deciding, for given Diophantine equation, whether the number of its solutions belongs to M or not.

Clearly, the case M = {0} is the original Hilbert’s tenth problem.

 
Source
< Prev   CONTENTS   Source   Next >