References for Undecidability

 References:

The blog posts Diophantine set, Listable sets, Halting problem, DPRM Theorem are based on superb article by B Poonan. - Undecidability in Number Theory.
As the article points out, the undecidability problem was studied not only for Integers, but also for Rationals, Rings etc.,

One of the questions, Poonan posed earlier in the article - does $x^3+y^3+z^3=33$ has integer solutions? At the time of writing article answer to this question was unknown. The article prompted search for solution to above equation. In fact an integer solution was now found.

DPRM theorem & Hilberts 10th problem

DPRM theorem(Davis, Putnam, Robinson, Matiyasevich):

A subset of $\mathcal{Z}$ is listable iff it is diophantine.

Listable means that there is an algorithm that prints the subset. Diophantine set consists of integers for which diophantine equations has solutions. 

Undeciability of the halting problem yields a listable set that is not computable. By DPRM theorem, listable implies diophantine. Hence, diophantine set is not computable.

By definition of diophantine set, we have a polynomial $p(t,\overrightarrow{x})$ such that there is no algorithm for deciding for which values of $a \in \mathcal{Z}$ the equation $p(a,\overrightarrow{x})$ has a solution.

Thus, there is no algorithm for deciding the existence of integer solutions to all polynomial equations.

Computable sets and Halting problem

 A set A ⊆ Z is computable if there is an algorithm for deciding membership in A.

Deciding membership in $A$ means algorithm should respond back Yes/No for the given input element.

First thing to notice is that any computable set is listable. Listable set implies there is an algorithm that prints $L \in \mathcal{Z}$. Then, checking if a given input is there in the $L$ is simple. 

However, not very clear if every listable set is computable.

Assume for a moment, that the algorithm is very complicated and takes long time to output list elements. For example, say it takes a day to print each element of the list. Then, for a given integer say $42$, if the algorithm didn't print that yet, it is impossible to say if it will print this at all.

Once we agree that every listable set is not computable, next step is to see if we can identify listable sets that are not computable.

This leads to Halting problem:

Halting problem asks a simple question. Given a program $p$ and an input $x$, the question Halting problem seeks is can $p$ terminate or will it continue for ever?

Say our program $p$ is

while (true) {

    do something;

}

This is an infinite loop. Our Halting algorithm (if we can build one) returns NO to the question if $p$ terminates.

Similarly if $p$ is the following expression in Mathematica,

FindInstance[k == x^3 + y^3, {x, y}, PositiveIntegers, 2]

Our Halting algorithm returns YES to the question if $p$ terminates for $k=1729$.

Theorem: The halting problem is undecidable.

Proof is clever. Since, halting problem takes as input a program $p$ and input $x$, say we do have a program $A$ which returns true if $p$ halts and false otherwise.

Since, the universe of inputs is any possible program one can conceive, I can write a devilishly cunning program ($DCP$) that runs forever while indicating to $A$ that it will terminate and vice-versa.

Then, $DCP($A$) returns true while running forever and false while terminating which is a contradiction. This proves that the halting problem is undecidable.

Corollary identifies a set $A$ consisting of $2^p3^x$ such that program $p$ halts on input $x$. By above theorem, $A$ is not computable. However $A$ is listable.

The following algorithm shows how to make $A$ listable.

For input $N=0,1,2...$ and during iteration $N$, 

foreach $p$

    run $p$ on input $x \leq N$ in $N$ steps

    print $2^p3^x$ if program terminates within these $N$ steps.

 

 

Listable sets

 Definition:

A set $A \subset \mathcal{Z}$ is listable if there is an algorithm that prints it.

Picked up this short and sweet definition from Undecidability in Number Theory

Clearly Diophantine sets are listable. Others include

• the set of all primes
• the set of Fibonacci numbers

A set of integers expressible as sum of three cubes is listable. 

For example, one can list elements using the following Mathematica code.

scp[z_] :=
 FindInstance[z == x^3 + y^3 + t^3, {x, y, t}, PositiveIntegers]
listS = Map[scp, Range[10]]

As we change the Range, we get larger and larger lists. The fact we have an algorithm that yields a list of elements is sufficient to characterize listable sets.

Diophantine Sets

 Diophantine set

is simply set of positive integers for which a particular Diophantine equation has solution.

For example, if we have a polynomial equation of single variable,

$x^2=4$

Then the Diophantine set for this equation contains $4$ as above equation can be factored into integers.

Now, instead of $4$, we use a $z \in \mathcal{Z}$, then we get lots of elements for Diophantine set.

In two variables, say our equation of interest is,

$(x+1)(y+1)=z$.

Here, we are looking for $z$. Based on above equation, we are seeking composite numbers.

The following Mathematica code generates Diophantine set for the first 20 integers - that is $z=1,2,...$.

f[z_] := FindInstance[z == (1 + y) (1 + x), {x, y}, PositiveIntegers]
S = Map[f, Range[20]]
Complement[Range[20], Position[S, {}] // Flatten]

Yields
$\{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20 \}$

Which are elements of Diophantine set, that is set of integers for which above polynomial has solution. Notice we restricted the range to first 20 integers. Same Mathematica expression can be extended for higher ranges.

From Wik, lets take the sum of squares example.

$z = x^2+y^2$

We can reuse above Mathematica expresions to find the Diophantine set elements when we restrict to first 20 integers.

ss[z_] := FindInstance[z == x^2 + y^2, {x, y}, PositiveIntegers]
SS = Map[ss, Range[20]]
Complement[Range[20], Position[SS, {}] // Flatten]

Yields
{2, 5, 8, 10, 13, 17, 18, 20}
Another example is beautiful Pell equation which manages to avoid all the perfect squares.

Mathematica code given below.

pel[z_] := FindInstance[z == (y^2 - 1)/x^2, {x, y}, PositiveIntegers]
PEL = Map[pel, Range[20]]
Complement[Range[20], Position[PEL, {}] // Flatten]

Yields
{2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20}

Mathematica code written above looks for solutions in positive integer space. However, in general, both positive and negative integer solutions are permitted.

Based on these examples, one can understand the definition of Diophantine set.

A set $A \subset Z$ is diophantine if there exists a ploynomial $p(t,\overrightarrow{x})=\{a \in Z|(\exists \overrightarrow{x} \in \mathcal{Z}^n) p(a,\overrightarrow{x})=0$.

Here we think of $p$ as a family of polynomials depending on parameter $t$. Then $A$ captures values of $t$ for which $p$ has solution.