Diophantine equations and Turing decidability

I enjoyed reading Yuri Matiyasevich’s Hilbert 10th Problem (Thanks Stéphane for the recommendation).
It is rather accessible overall, but some results and demonstrations do get quite mind-bending. Below are my notes on the key topics (mostly covering the first 5 chapters).

Diophantine equations, sets and relations

Diophantine equations are polynomials with integer coefficients and variables. They can be used to define Diophantine sets. To do so, you separate the variables of the polynomial into parameters and unknowns. Then the set of parameter values such that the polynomial’s unknowns can be solved is called a Diophantine set.
Any set for which you can find such a polynomial is a Diophantine set.

For instance, the set of even numbers is Diophantine because it is represented by polynomial a - 2x = 0 (where a is a parameter and x an unknown). Similarly, because of Lagrange’s four-square theorem, the set of non-negative numbers is represented by a - (x2 + y2 + w2 + z2) = 0.

The intersection and union of Diophantine sets is also Diophantine, if you consider the following polynomials respectively:

1. FirstPolynomial2 + SecondPolynomial2 = 0 (with the unknowns in SecondPolynomial renamed to avoid conflicts)
2. FirstPolynomial * SecondPolynomial = 0

By combining the above, you can make a polynomial representing the set of numbers that are both even and non-negative.
More generally, there is an equivalence between determining if a Diophantine equation has integer solutions or non-negative solutions. So the default is to focus on non-negative solutions.

The notion of Diophantine sets can naturally be extended to properties, relations and functions. I’ll just illustrate those with examples:

• We already saw that the set of even numbers is Diophantine, therefore so is the corresponding property: IsEven(a) -> bool.
• We could show that the set of pairs {a, b} where a is not equal to b is Diophantine, therefore so is the corresponding relation: NotEqual(a, b) -> bool.
• We could show that the set of triplets {a, b, c} where a is the remainder of b divided by c is Diophantine, therefore so is the corresponding function: a = rem(b, c).

In this fashion, step by step, you can show that more complex sets and relations are Diophantine, such as divisibility, non-divisibility, greatest common divisor, exponentiation (!) and primeness (!!!).

The exponentiation, which corresponds to the set of triplets {a, b, c} such that a = bc, can also be shown Diophantine.
This provides a method to reduce exponential Diophantine equations (where exponentiation can appear in the expression along with additions, substractions and multiplications) to equivalent polynomials. A simple example to illustrate the method: create a new variable z to substitute to an exponential, xy, and use this variable definition as SecondPolynomial (z - xy = 0) for the intersection formula above.
By the way, this method of introducing more variables can also be used to refactor any Diophantine equation into an equivalent equation of degree 4 at most.

The IsPrime(a) -> bool property is Diophantine too, which is quite an amazing result too. This means there exists a polynomial that generates exactly the set of primes when its parameters are allowed to take any and all natural numbers! (p. 55)

Codings: Cantor, Gödel and positional

There are multiple ways of coding tuples into lower dimensional spaces. This is useful to iterate through all possible tuples, refactor equations to fewer parameters and unknowns, and enumerate all polynomials.

The Cantor numbering allows to represent a tuple of length n as an integer (with n fixed).
For n=2, it sequences pairs following the diagonals: {0, 0}, the {1, 0}, {0, 1}, then {2, 0}, {1, 1}, {0, 2}, then {3, 0} and so on as shown in the following table.

For higher dimensions, the same method can be applied recursively to reduce the dimension one at a time.
Cantorn(a1, ..., an) -> c is a Diophantine function, and so is the converse CantorElementn,i(c). But the function CantorElement(n, i, c) which treats n and i as variables cannot easily be shown to be Diophantine. So other codings are considered.

The Gödel coding allows encoding tuples {a1, ..., an} of arbitrary dimension into a triplet (and you could even go further and encode that triplet with Cantor if you wanted). It’s based on the Chinese Remainder Theorem and is defined as the triples {a, b, n} such that ai = rem(a, b.i + 1) = GodelElement(a, b, i). There is more than one such triple for a given tuple, so the coding is not unique (unlike Cantor’s). There can be no converse function, Godel(a1, ..., an, n), as it would have a variable number of parameters. That coding is Diophantine as the remainder function is.

The positional coding also represents a tuple as a triplet {a, b, n}, but where a is the representation in base b of the tuple. That means a = an.bn-1 + ... + a1.b0. Not every tuple is a positional code, but the property IsPositionalCode(a, b, n) can tell which ones are. That property is Diophantine, and so are the relations for comparing such encoded tuples, PositionalEqual(a1, b1, c1, a2, b2, c2).

Universal Diophantine equations

It gets trippy when Universal Diophantine Equations are introduced. Those are polynomials where the variables are broken into 3 groups: code parameters, element parameters and unknowns. Such an equation is universal if it can code (by choosing the code parameters) for any Diophantine equation (which means it will represent the same set).
Chapter 4 demonstrates that such a universal Diophantine equations can be constructed. This relies heavily on the codings introduced above.

Turing machines

Chapter 5 provides a very nice introduction to Turing machines. The specific design introduced uses { *, 0, 1, 2, 3, null } as its alphabet and reserves two states as final states for Yes and No.
The tape encodes a stack of integers by using 0 to separate sequences of 1’s. During the functioning of the machines, the 1’s will typically be marked as 2’s or 3’s temporarily, then reverted to 1’s.

After explaining how to compose machines into sequences, conditionals and loops, a number of increasingly complex machines are introduced by composition:
Left, Right, Write(x), Read(x) (goes to state Yes or No depending on the value read at the cursor position), Stop, NeverStop, ReadNot(x), Star (jumping to head of the tape), Vacant (jumping to the first empty spot down the tape), Find(k) (which jumpts to the k’th integer on the tape), Increase (adds a 1 to the last integer), Decrease, Delete (deletes the last integer), Mark(x) (replace 1’s with x’s in the current integer), IsThere(x) (which tries to find an x on the tape), ThereWas(x) (which finds an x and writes it back to 1), Restore (set all the 2’s and 3’s back to 1), Append(k) (increment the head of the stack by the value of the k-th integer), Copy(k) (adds an entry on the stack, copied from the k-th integer), Add(k, l) (adds an entry on the stack with the sum of the k-th and l-th integers), Mult(k, l), NotGreater(k, l), Equal(k, l), NotEqual(k, l), Next (updates the two entries on top of the stack according to Cantor’s numbering), and Decode (gets the Cantor pair represented by the entry on top of the stack and adds two entries storing that pair).

Turing decidability and Hilbert’s Tenth Problem

All these primitive machines can be used to construct a machine that recognizes a given Diophantine set (the machine will halt if and only if initialized with tuples from the set). The machine starts with the parameters on tape and then enumerates all the possible values for the unknowns, one tuple at a time. For each, it checks whether those values solve the parameterized Diophantine equation.

A set is called Turing semidecidable if such a Turing machine exists (that will halt when and only when the machine is initialized with an n-tuple from the set). As mentioned above, from every Diophantine set we can construct a Turing machine that will recognize n-tuples from that set. But the converse turns out to be possible to, and every Turing semidecidable set is Diophantine.

A set is called Turing decidable if a Turing machine exists that will halt on state Yes for n-tuples in the set and halt on state No otherwise. From a decidable machine, you can easily make a semidecidable one. Conversely, if a set and it’s complement are both semidecidable, then they are decidable. You could construct a “schizophrenic” machine that runs one step of each machine, and therefore would be guaranteed to halt with a Yes or No.

In this context, Hilbert Tenth Problem asks whether the set of codes of all solvable Diophantine equations (without parameters) is Turing decidable.
Matiyasevich proves the negative: there is no way that is guaranteed to halt for determining if a Diophantine equation is solvable.

Moreover, based on Church’s Thesis, this conclusion holds in general; it is not contingent on the specific Turing machine introduced above.