Author: silverxz
Proofreader: Acidmoon

This article proves that Diophantine sets are equivalent to recursively enumerable sets.

We have already noted that the direction from Diophantine sets to recursively enumerable sets is fairly straightforward. Let there be a Diophantine set $S$ and its corresponding Diophantine equation $D(x_1,...,x_n,y_1,...,y_m)=0$ ; for $(a_1,...,a_n)\in \mathbb{N}^n$ , we need only have a Turing machine $M$ systematically try every possible $y_1,...,y_m$ to see whether $D(a_1,...,a_n,y_1,...,y_m)=0$ holds. If $(a_1,...,a_n)\in S$ , the machine will eventually halt. The candidates must, of course, be enumerated in a reasonable way that guarantees every possible solution will be reached in finite time.

There is a subtle point here: given $S$ , we do not know what $D$ is. Yet such a $D$ always exists, so the corresponding Turing machine $M$ also exists.

That completes this direction of the proof. What really concerns us is how to prove that every recursively enumerable set is Diophantine. Our method is to construct Diophantine functions and relations that simulate each computational step of a Turing machine. This approach is not unusual. Readers familiar with basic computability theory may know the computation history method, a general technique used in undecidability proofs; the idea used here is much the same.

Diophantine Relations

We have already mentioned that a Diophantine relation is essentially the same thing as a Diophantine set, and that a Diophantine function can be viewed as a special Diophantine set or relation. Readers may not yet have an intuitive sense of what kinds of constructions this permits, however, so I will begin with a few simple examples before turning to the proof.

Perhaps the simplest example is the unary relation (predicate) “is even,” characterized as follows:

$\text{Even}(a) := \exists y (a=2y)$

Why is this a Diophantine relation? Let $D(x,y)=x-2y$ . The equation $D(x,y)=0$ , with $x$ as its parameter and $y$ as its unknown, defines the Diophantine set $S$ as follows:

$S=\{a\in \mathbb{N}\mid \exists y\left( D(a,y)=0\right)\}$

This shows that $\text{Even}$ is a Diophantine relation. Note that because we have restricted the solutions of Diophantine equations to natural numbers, all existential quantifiers $\exists$ are understood to range over the natural numbers.

Similarly, $\geq, >,=,<,\leq, \mid$ (divisibility) are also Diophantine binary relations. Taking $\geq$ as an example, we may write

$\geq (a,b):= \exists x(a=b+x)$

Of course, $\geq (a,b)$ is rather awkward notation; from here on, we will write such binary relations in the customary form $a\geq b$ instead.

Next come Diophantine functions. Recall that a multivariable function on the natural numbers $f(x_1,...,x_n)$ is itself, in essence, a subset of the relevant Cartesian product $F=\{(a_1,...,a_n,f(a_1,...,a_n))\mid (a_1,...,a_n)\in \mathbb{N}^n\}\subset \mathbb{N}^{n+1}$ , so when we say that $f$ is a Diophantine function, what we really mean is that $F$ is a Diophantine set or relation. Addition, subtraction, and multiplication are naturally Diophantine functions. Another example is the remainder function $\text{rem}(b,c)$ , defined as the remainder when $b$ is divided by $c$ . Since

$a = \text{rem}(b,c) \Leftrightarrow a < c\ \&\ c \mid (b-a)$

—that is, $a$ is the remainder when $b$ is divided by $c$ —is equivalent to $a < c$ and $c$ divides $b-a$ ; therefore, this is a Diophantine function. Wait, did you say “ $\&$ ”? That is logical conjunction. Recall that we proved Diophantine sets are closed under intersection and union. In the language of Diophantine relations, this means that Diophantine relations are closed under logical AND and OR. We may therefore join simple Diophantine relations and functions with logical connectives to construct highly complex relations. Consequently, $\neq$ , which was not listed above, is also Diophantine, because it is $>$ or $<$ . Likewise, integer division is a Diophantine function. Since all our arithmetic takes place in the natural numbers, all division below means integer division by default.

Two further elementary facts are useful. First, nesting Diophantine relations or adding more existential quantifiers outside them still yields a Diophantine relation, because we can always expand the definitions and move every existential quantifier to the outermost level. We should make full use of this freedom to introduce existential quantifiers in Diophantine relations; many later constructions rely on it: rather than constructing the desired object directly, we describe its properties and use existential quantifiers to “select” it. Second, for a Diophantine set $S$ , $S\times \mathbb{N}^k$ is also Diophantine; this merely adds a few irrelevant variables to the corresponding equation. We therefore need not worry about matching the number of variables when applying logical connectives—we can simply “pad” the sets as needed.

Combining these facts with Bézout’s identity from number theory, readers can verify that the greatest-common-divisor function $\gcd$ is also Diophantine.

$a=\gcd(b,c)\Leftrightarrow bc>0 \ \&\ a\mid b\ \&\ a\mid c\ \&\ \exists xy(a=bx-cy)$

By now, readers should have more confidence in our proof: Diophantine relations are indeed quite expressive. Our goal is to express the following statement with such relations. Given a recursively enumerable set $S\subset \mathbb{N}^n$ , there exist a Turing machine $M$ , an input $(a_1,...,a_n)$ , and a number of steps $k$ , such that $(a_1,...,a_n)\in S$ is equivalent to $M$ halting after $k$ steps (that is, reaching the final state $q_f$ ). We therefore need a Diophantine function capable of simulating $k$ steps of a Turing machine’s execution.

To simulate $k$ steps of execution, we must of course first simulate a single step. To do that, we must at least determine how to encode the Turing machine’s various states and its operation. Crucially, this encoding must itself be “Diophantine.”

Encoding a Turing Machine

Let us review the “information” contained in a Turing machine: a finite set of states $Q=\{q_1,...,q_{|Q|}\}$ , in which $q_1$ is the initial state, $q_{|Q|}$ is the final state (also denoted $q_f$ ); and a finite alphabet $\Sigma=\{0, 1,...,{|\Sigma|}-1\}$ , in which $0$ is the blank symbol. We will use $|Q|$ and $|\Sigma|$ for the sizes of the state set and the alphabet, thereby saving a few letters. Finally, there is a transition function.

A Turing machine’s transition function is usually defined as a single whole. For convenience, we divide it into three parts here. Suppose the machine is in state $q_i$ , and the symbol at the current position is $s_j$ . Let the index of the state reached by the transition be $Q(i,j)\in \{1,...,|Q|\}$ , the index of the symbol written by the machine be $\Sigma(i,j)\in \{0, 1,..., |\Sigma|-1\}$ , and the direction in which the tape head moves be $D(i,j) \in \{-,\text{L},\text{R}\}$ (stay, move left, or move right, which we may represent as $\{0,1,2\}$ ). We thus obtain three functions $Q(i,j),\Sigma(i,j),D(i,j)$ , where $Q$ and $\Sigma$ are once again “overloaded” to save letters. Their meanings should be clear from context.

For the Turing machine, these functions are meaningful only when $1\leq i\leq |Q|,0\leq j\leq |\Sigma|-1$ holds. But to make them Diophantine functions, we must extend their domains to $\mathbb{N}\times \mathbb{N}$ . The values assigned on the extended portion actually depend on what we will need later; here we simply specify them. In these otherwise meaningless cases, let $Q(i,j)$ equal $i$ , $\Sigma(i,j)$ equal $j$ , and $D(i,j)$ equal $-$ . This means invalid arguments leave the state, symbol, and direction unchanged. We now claim that the functions $Q,\Sigma,D$ are all Diophantine.

This is because each amounts to modifying a Diophantine function ( $f(i,j)=j$ and so on) at finitely many points ( $1\leq i\leq |Q|,1\leq j\leq |\Sigma|$ ), so we can simply use a logical expression to enumerate the cases. For the simplest example, suppose I want to describe a function whose value at $1$ is $2$ , and which equals $g(x)$ everywhere else. Call it $f(x)$ : I need only write

$y=f(x)\Leftrightarrow (x=1 \ \&\ y=2) \vee (x\neq 1\ \&\ y=g(x))$

Here, provided that $g(x)$ is a Diophantine function, $f(x)$ is one as well. The same applies to $Q,\Sigma, D$ : we need only enumerate the finitely many valid positions, then assign the “remaining cases” another Diophantine function of our choosing. This characterizes the Turing machine itself; $Q,\Sigma,D$ will also be the notation used below.

We must also describe the state of the Turing machine during execution: the string on the tape $(s_1,...,s_l)$ , the current state $q_i$ , and the tape head’s position. These three quantities are often called the machine’s configuration—its instantaneous state during execution. We need a suitable way to record them. Using $s_1,...,s_l$ directly will not work, because $l$ may grow linearly as the machine runs, whereas a Diophantine equation always has only finitely many unknowns. We therefore need the technique of tuple encoding.

Encoding Tuples: Cantor Encoding and Positional Encoding

(We actually use only positional encoding. Cantor encoding is also simple and elegant, however, so I will present it as well. Comparing the two should make it clearer why we choose positional encoding.)

We begin with a relatively “classical” method: Cantor encoding. First, how can we encode $(a,b)\in \mathbb{N}^2$ as a single natural number? Cantor supplied a beautiful method. Readers can verify that the following function $\text{Cantor}$ gives a bijection $\mathbb{N}^2\to \mathbb{N}$ .

$\text{Cantor}(a,b)\mapsto \frac{(a+b)^2+3a+b}{2}$

Readers who are not interested may simply accept this result. If you have trouble verifying it, try drawing a two-dimensional table and substituting $(0,0),(0,1),(1,0),...$ ; you may notice something interesting.

This is a useful encoding: it is a Diophantine function, and given a Cantor code $c$ , the functions that recover $a,b$ , namely $\text{ElemA}(c),\text{ElemB}(c)$ , are Diophantine as well. For $\text{ElemA}(c)$ , for example, we have

$a = \text{ElemA}(c)\Leftrightarrow \exists b (\text{Cantor}(a,b)=c)$

Furthermore, a triple may be represented by $\text{Cantor}_3(a,b,c)=\text{Cantor}(a, \text{Cantor}(b,c))$ ; the coordinate functions $\text{Elem}$ are similar. Continuing inductively, we obtain Cantor encodings for tuples of any fixed length $\text{Cantor}_n$ . Note, however, that here $n$ must be a fixed constant; it cannot be supplied as a variable input.

This encoding makes it easy both to encode a fixed-length tuple as a natural number and to recover it. Should we therefore use it for our tuples? No. Useful though it is, it is not quite enough: variable-length tuples are difficult to handle, and more complex operations such as concatenation are harder still.

We therefore introduce another encoding, called positional encoding; it applies when the tuple’s entries have an upper bound.

Let there be a tuple $(x_1,...,x_n)$ , whose entries have an upper bound $b>x_i$ ; we may then use base $b$ . Define

$a_x=x_1+x_2b + ... + x_n b^{n-1}$

Then $(a_x,b,n)$ is called a positional encoding of $(x_1,...,x_n)$ ; $b$ is called the encoding’s base or radix. It records the tuple length $n$ , the radix $b$ , and its value in base $b$ , namely $a_x$ . Readers need not understand the principle behind Cantor encoding, but they do need to understand positional encoding—which is simply place-value notation—because we will make concrete use of many properties of this expression, really just properties of numeral systems. They reveal what an elegant choice this is.

Sometimes we can use Cantor encoding to encode this triple still further. At other times, all we actually need is $a_x$ , because $b$ will be known and need not be included in the code, while $n$ may not matter. In that case, we also call $a_x$ itself a positional code, when the context makes the meaning clear. One further point: an advantage of positional encoding is that if $n$ is larger than the length of the original code, decoding merely produces additional trailing $0$ , and in many situations we do not care about extra $0$ .

Its coordinate function is likewise Diophantine, but using radix notation has a drawback: we must introduce something more powerful. Let $\text{Elem}(a,b,d)$ denote the value at position $d$ , so

$e = \text{Elem}(a,b,d) \Leftrightarrow \exists xy(a = xb^d+eb^{d-1} + y \ \&\ e \text{<} b\ \&\ y\text{<}b^{d-1}\ \&\ d\text{>}0)$

Did you notice the “more powerful” ingredient we introduced? We used an exponential function such as $b^d$ , which we have not yet proved to be Diophantine. As the historical account showed, this is in fact a very difficult part of the proof. For now, we assume that exponentiation is a Diophantine function; a proof may be supplied in the next article.

It follows that $\text{Elem}(a,b,d)$ is also a Diophantine function. But recall that we introduced this encoding to perform more complex operations. For example, componentwise addition: we need only add the positional codes directly, provided the result in every position does not exceed $b$ ; for positional encoding, this is nearly trivial.

Now consider another operation: concatenation $\text{Cat}$ . Let there be another tuple $(y_1,...,y_m)$ , which we want to append to $(x_1,...,x_n)$ to form $(x_1,...,x_n,y_1,...,y_m)$ . If $(y_1,...,y_m)$ also has an upper bound $b$ , it too may be represented positionally by $(a_y,b,m)$ . The positional code of the concatenated tuple $a$ is easy to calculate. Readers can verify that the following relation holds exactly when the values $a,b,c$ form the positional code of the concatenation:

$\text{Cat}(a_x,b_x,n,a_y,b_y,m,a,b,c) \Leftrightarrow b_x=b_y=b\ \&\ c=n+m\ \&\ a=a_x+a_yb^n$

Strictly speaking, we must also use $\&$ to conjoin two further conditions: $(a_x,b_x,n)$ and $(a_y,b_y,m)$ must indeed be valid positional codes. Unlike Cantor encoding, positional encoding need not be a bijection, so invalid cases may occur. The validity relation $\text{Pos}(a,b,n)$ is also Diophantine, because

$\text{Pos}(a,b,n)\Leftrightarrow b\geq 2 \ \&\ a < b^n$

Again, this requires assuming that exponentiation is a Diophantine function.

Encoding Turing-Machine Configurations

With positional encoding in hand, we can return to the unfinished task of encoding Turing-machine configurations. As noted above, a configuration contains three pieces of information: the string on the tape, the head position, and the current state. In fact, these can be summarized by two tuples. The first tuple $(0,...,0,i,0,...,0)$ simultaneously records the tape head’s position and the machine’s current state $q_i$ , while the second tuple $(s_1,...,s_l)$ records the string currently on the tape. Both tuples have length $l$ .

More importantly, the entries of both tuples are bounded. An entry of the first tuple cannot exceed the number of states $|Q|$ , while an entry of the second cannot exceed the size of the alphabet $|\Sigma|$ . We therefore choose a fixed base $\beta>\max\{|Q|,|\Sigma|\}$ , use positional encoding to encode the first tuple as $(p,\beta,l)$ , and encode the second as $(t,\beta,l)$ .

Since $\beta$ is constant, $l$ is their common length—and, as we will see, we scarcely need it—so we directly regard $p,t$ as the encoding of the Turing-machine configuration. For convenience, we also use $p,t$ to refer to the two tuples themselves.

Diophantine Functions for One Step of a Turing Machine

The preliminaries are complete: we have nearly all the parts, and it is time to assemble them. Our first goal in this section is to construct the Diophantine functions $\text{NextP}(p, t)$ and $\text{NextT}(p, t)$ ; respectively, they give the two components of the code for the configuration obtained from $p,t$ by one step. We will later use them to construct $\text{AfterP}(k,p,t)$ and $\text{AfterT}(k,p,t)$ ; these Diophantine functions represent the codes of the configurations obtained from $p,t$ after $k$ steps of execution.

We begin with $\text{NextT}(p,t)$ ; the idea is relatively simple. Consider what must be done: from the tuple $p=(0,...,0,i,0,...,0),t=(s_1,...,s_l)$ we must produce a new tuple $t'=(s_1',...,s_l')$ , in which, at every position where $p$ takes $0$ in the original tuple, we simply copy the value of $t$ into $t'$ ; at the position where it takes $i$ —the position of the tape head—the corresponding symbol must be changed. This is exactly what our existing Turing-machine function $\Sigma(i,j)$ does, because $\Sigma(i,j)$ leaves the symbol unchanged when $i=0$ , returning $j$ ; otherwise it returns the modified symbol. In fact, this requirement is precisely why we designed $\Sigma(i,j)$ .

But $\Sigma$ handles only a single position, whereas we want to process an entire tuple. We therefore need some syntactic sugar that extends a function from one entry to a variable-length tuple, applying the function to every entry. This should be easy to understand, since such syntactic sugar is common in modern programming languages.

In general, consider a Diophantine function $f(x)$ , and assume that every entry of the tuples below is less than $b$ . We wish to construct a Diophantine function $f_b(a,c)$ , which maps the positional code $(a,b,c)$ of the tuple $(a_1,...,a_c)$ to the tuple $(f(a_1),...,f(a_c))$ ; its positional code is $(f_b(a,c),b,c)$ . When $(a,b,c)$ is not a valid code, $f_b(a,c)$ may be assigned arbitrarily.

This construction requires some care and is slightly laborious. I will give its outline and leave the proof to you. The key idea is this: because $b$ is a fixed finite bound, we enumerate its possible values and decompose the tuple into a collection of 0–1 indicator vectors.

Specifically, let $h_i(i=0,...,b-1)$ be the positional code of the vector $(h_{i,1},...,h_{i,c})$ , where $h_{i,j}$ indicates whether $a_j=i$ : it takes the value $1$ when the equality holds and $0$ otherwise. In other words, $h_i$ records the positions at which $a$ takes the value $i$ .

Recall that positional codes can be added directly. Thus, observe that

$0\cdot h_0 + 1\cdot h_1 + \dots + (b-1)\cdot h_{b-1}=a$

Also observe that

$f(0)\cdot h_0 + f(1)\cdot h_1 + \dots + f(b-1)\cdot h_{b-1}=f_{b}(a,c)$

It therefore suffices to show that $h_i$ are vectors determined by Diophantine functions and relations; this will establish that $f_b(a,c)$ is a Diophantine function.

Define the function $\text{Repeat}(x,b,c)$ as the positional code of the tuple $(x,x,...,x)$ ( $x\text{<}b$ ), with $c$ entries, in base $b$ . Define the relation $\text{Orth}_b(x_1,x_2, c)$ to mean that the tuples encoded by $(x_1,b,c)$ and $(x_2,b,c)$ are $01$ indicator vectors that are mutually disjoint: two $1$ values never occur at the same position. You can verify that both are Diophantine. These two Diophantine relations, together with the preceding equation—which is itself essentially a Diophantine relation because $b$ is constant—uniquely determine all the $h_i$ . This shows that $f_b(a,c)$ is a Diophantine function. Notice that this uses the earlier idea: we do not write down $h$ directly, but instead use relations such as $\text{Repeat}$ to constrain $h$ , ensuring that a qualifying $h$ exists and is unique; we then use the existential quantifier $\exists$ to select it.

More generally, this construction extends to multivariable functions $f(x_1,...,x_n)$ , yielding $f_b(a_1,...,a_n,c)$ , because we still need only a finite enumeration. This is precisely what we wanted.

Returning to our construction of $\text{NextT}(p,t)$ , this syntactic sugar completes it:

$t' = \text{NextT}(p,t)\Leftrightarrow \exists w (t'=\Sigma_\beta (p, t, w))$

Here $w$ serves as the tuple length. Readers may notice that when $w>l$ , $p,t$ can still be decoded. Could this produce an incorrect $t'$ ? No, because it merely produces extra $0$ s; after the $\Sigma$ mapping, they remain $0$ s, so they do not affect the value of $t'$ . The reason we must proceed this way is that $l$ changes as the Turing machine runs, making it difficult and unnecessary to maintain a changing $l$ . Instead, we rely only on the existence of $l$ and the useful property that “redundant $0$ entries do not change a positional code.”

We have thus obtained $\text{NextT}$ . Although the construction is lengthy, its idea is not complicated. Next comes $\text{NextP}(p,t)$ , whose construction is less direct. $t$ changes componentwise, so our syntactic sugar handles it neatly. The Turing machine’s tape head moves left or right, however, which means that the change in $p$ depends on neighboring values.

This obstacle can nevertheless be overcome. A positional code can easily be shifted by multiplying by $\beta$ or dividing by $\beta$ ! For a base- $\beta$ positional code $a$ , we use $a^L=a/\beta$ (integer division) to represent a left shift—removing the first entry and appending $0$ —and use $a^R=a\beta$ to represent a right shift—making the first entry $0$ and shifting every other entry one place to the right.

We can now apply our syntactic sugar to the tuples after shifting them left and right. At the level of a single entry, this amounts to “taking neighboring entries into account.” Specifically, we want to define a function $DQ$ (because it combines the Turing-machine functions $D$ and $Q$ ) such that its lifted, componentwise form $DQ_\beta$ gives $\text{NextP}$ as follows:

$p'=\text{NextP}(p,t)\Leftrightarrow \exists w (p'=DQ_\beta(p^L,p,p^R,t^L,t,t^R,w))$

If you already see what we are doing, excellent: spelling out the definition of $DQ$ is genuinely cumbersome. If not, compare it with the explicit definition of $DQ$ and work through it again. We define $DQ(i_r, i, i_l, t_r, t, t_l)$ as follows. Notice that left and right are reversed here: shifting $p$ left moves the entry on the right into place, so the variable corresponding to $p^L$ is denoted $i_r$ ; the other cases are analogous:

$DQ=\left\{\begin{matrix} Q(i_l,j_l) & i_l>0, i=i_r=0,D(i_l,j_l)=L \\ Q(i,j) & i_l=i_r=0, i>0, D(i,j)=-\\ Q(i_r,j_r) & i_l=i=0, i_r>0, D(i_r,j_r)=R\\ 0 & \text{otherwise} \end{matrix}\right.$

Thus, $\text{NextP}$ has been constructed as well.

Diophantine Functions for Multiple Steps of a Turing Machine

The end is in sight. We now prove that $\text{AfterP}(k,p,t)$ and $\text{AfterT}(k,p,t)$ are also Diophantine functions. They encode the configurations obtained from $p,t$ after $k$ steps of execution.

The evident difficulty is $k$ . We all know that iterating $\text{NextP}$ and $\text{NextT}$ exactly $k$ times yields the two desired functions, but $k$ is a variable rather than a constant, so this iteration does not establish that the functions are Diophantine.

The solution follows the computation-history idea: consider the entire computation over these $k$ steps—that is, all $k+1$ configurations—find enough conditions to constrain them, and then select them with existential quantifiers.

Continue to use the aforementioned $\beta$ as the radix for positional encoding. Let $p_0=p,t_0=t$ , and let $p_i,t_i(i\leq k)$ be the encoded result after $i$ iterations.

Recall that positional encoding lets us concatenate tuples. To handle these $k+1$ configurations, we concatenate them. Concatenation requires a specified tuple length, however, while the configuration tuples vary in length. This is not a problem: we can assign a length $l$ greater than every tuple involved. This merely introduces a few trailing $0$ upon decoding, and we already know that extra $0$ entries cause no error.

Specifically, let $(p_L,\beta, kl)$ be the result of concatenating the positional codes $(p_0,\beta, l),(p_1,\beta,l),...,(p_{k-1},\beta, l)$ ; let $(p_R,\beta, kl)$ be the result of concatenating $(p_1,\beta, l),(p_2,\beta,l),...,(p_{k},\beta, l)$ in the same way. We do likewise for $t_L,t_R$ .

Why define them this way instead of concatenating all $k+1$ configurations? Because we have the following observation: $p_R=\text{NextP}(p_L,t_L),t_R=\text{NextT}(p_L,t_L)$ . This holds because $\text{NextT}$ acts componentwise, so it can operate on several concatenated configurations at once, while $\text{NextP}$ is almost componentwise, except that it also examines adjacent entries. We need only insert $0$ between configurations to prevent interference, which merely requires taking $l$ sufficiently large.

This observation supplies an important constraint. We can also see that if $(p_M,\beta, (k-1)l)$ denotes the “middle portion,” namely the concatenation of $(p_1,\beta,l),...,(p_{k-1},\beta,l)$ , and we define $t_M$ analogously, then: $(p_L,\beta,l)$ is the concatenation of $(p_0,\beta,l)$ and $(p_M,\beta,(k-1)l)$ ; while $(p_R,\beta,l)$ is the concatenation of $(p_M,\beta, (k-1)l)$ and $(p_k,\beta,l)$ . $t_L,t_R$ are analogous.

This transformation may look almost trivial, but it makes an essential difference. Now $p_L$ is no longer a concatenation of $k$ tuples; it has become a concatenation of just $p_0$ and $p_M$ —two tuples—so it is now an operation of a Diophantine function. The same is true of $p_R,t_L,t_R$ . Yet $p_M,t_M$ remains a concatenation of $k-1$ tuples. It may seem that we have not really solved the problem, but we have. We can now assert that the relations above uniquely determine $p_L,t_L,p_M,t_M,p_R,t_R,p_k,t_k$ .

To see this, let us collect the constraints obtained so far (we write $+_c$ for tuple concatenation):

$\begin{align*}p_R&=\text{NextP}(p_L,t_L)\t_R&=\text{NextT}(p_L,t_L)\(p_L,\beta,kl)&=(p,\beta,l)+_c(p_M,\beta,(k-1)l)\(p_R,\beta,kl)&=(p_M,\beta,(k-1)l)+_c(p_k,\beta,l)\(t_L,\beta,kl)&=(t,\beta,l)+_c(t_M,\beta,(k-1)l)\(t_R,\beta,kl)&=(t_M,\beta,(k-1)l)+_c(t_k,\beta,l)\end{align*}$

Existence is immediate, because we can in fact run the machine for $k$ steps; only uniqueness remains to be proved. For this purpose, consider the entries represented by $p_L$ and the other encoded tuples one by one.

$p_L$ has its first $l$ entries equal to $p$ itself, so they are uniquely determined. From $p_R=\text{NextP}(p_L,t_L)$ and the decomposition of $p_R$ , it follows that $p_M$ is determined through its first $l-1$ entries (because $\text{NextP}$ 's first $l-1$ output entries depend only on the first $l$ input entries). Once $p_M$ has been determined through its first $l-1$ entries, the decomposition of $p_L$ determines $2l-1$ entries, and so on. Repeating this argument determines $p_L,p_M$ in full.

A careful reader may spot a remaining issue: the last entry of $p_R$ has not yet been determined. This is because $\text{NextP}$ determines an output one entry shorter than its input. Recall, however, that we made $l$ slightly larger, so the last entry of $p_R$ is actually $0$ . This determines $p_R,p_k$ as well. The argument for $t_L,t_R,t_M,t_k$ is exactly analogous—and even simpler.

This is equivalent to saying that $p_k=\text{AfterP}(k,p,t)$ and $t_k=\text{AfterT}(k,p,t)$ are Diophantine functions. If you insist on writing the definition explicitly, it requires only a large collection of existential quantifiers: there exists a sufficiently large $l$ , there exist $p_L,p_M,...$ and all the other variables above, and the listed conditions are joined by logical conjunction. This completes the final part.

Hilbert’s Tenth Problem Is Unsolvable

Everything now falls into place. Given a Turing machine $M$ and its corresponding recursively enumerable set $S$ , define the Diophantine functions as above. Then $(a_1,...,a_n)\in S$ holds if and only if:

$\exists krpt (\text{Elem}(\text{AfterP}(k,p,t),\beta, r)=|Q|\ \&\ p=1\ \&\ t=\sum_{i=1}^n a_i \beta^{i-1})$

Let us unpack these three conditions. $\text{Elem}(\text{AfterP}(k,p,t),\beta, r)$ says that after $k$ steps, the Turing-machine head is at position $r$ , and the current state is $q_{|Q|}$ (the final state). $p=1$ is the index of the initial state $q_1$ , so $(1,0,...)$ is the code of this tuple, representing the machine’s initial head position and state. $t=\sum_{i=1}^n a_i \beta^{i-1}$ is the encoding of the machine’s initial input. Notice that $n$ is a fixed constant, so this sum is a valid operation. Together, the conditions say that the Turing machine, on input $(a_1,...,a_n)$ , halts after $k$ steps.

All three conditions are Diophantine, establishing that $S$ is a Diophantine set. We have therefore proved the MRDP theorem:

Diophantine sets are precisely the recursively enumerable sets.

We already know that some recursively enumerable sets are not recursive—for example, the recursively enumerable set associated with the halting problem. The process above is entirely constructive. Thus, in principle, given a Turing machine corresponding to such a recursively enumerable set, we can explicitly write down the variables and coefficients of a family of Diophantine equations corresponding to that set. The existence of integer solutions for this family must be undecidable; otherwise, the set itself would be decidable.

If solvability is undecidable even for a subclass of Diophantine equations—and we can explicitly provide their variables and coefficients, so there is no obstacle of encoding conversion—then solvability for all Diophantine equations is certainly undecidable. We may therefore conclude: Hilbert’s Tenth Problem is unsolvable.

(\Finished—time to celebrate!/)