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