A Rigorous Introduction to Hilbert's Tenth Problem (IV): Basic Concepts and Proof Framework

Author: silverxz
Proofreader: Shiguang

  We now turn to the proof itself. This is not the original proof, but Matiyasevich’s greatly simplified version from his book Hilbert’s Tenth Problem, so its route differs somewhat from the history described earlier. We will simplify parts of the argument further and skip details that are laborious without adding new ideas. The exposition often works backward: it starts from a result, asks what tools are needed to prove it, and then supplies those tools one by one. I will also use ordinary language to give an intuitive account of the proof and explain its motivation. That approach is better suited to a popular introduction.

What is Hilbert’s Tenth Problem?

  Let us first restate the problem we want to solve.

  A Diophantine equation is a multivariable polynomial equation with integer coefficients, written as . When its variables are known or irrelevant to the discussion, we abbreviate it as D.

  We want to know whether this equation has an integer solution. For a given D, the yes-or-no question is an individual instance, whose information is completely determined by the polynomial D itself.

  Every Diophantine equation determines one such instance. Taken together, these instances form a decision problem: does an algorithm—a Turing machine M—exist such that, for every Diophantine equation D, M gives the correct answer to the corresponding instance, namely whether D has an integer solution?

  This is Hilbert’s Tenth Problem. Our goal is to prove that no such algorithm exists.

  In fact, we will not analyze algorithms directly. Instead, we prove another statement:

MRDP theorem: the Diophantine sets are exactly the recursively enumerable sets.

  As is well known—if it is not, there is a short discussion of recursive sets below that you can try to follow—some recursively enumerable sets are undecidable. The MRDP theorem then gives undecidable Diophantine sets, hence families of Diophantine equations for which the existence of integer solutions is undecidable. If solvability cannot be decided even for one such family, it certainly cannot be decided for all Diophantine equations. Hilbert’s Tenth Problem is therefore unsolvable.

  This article first presents some elementary properties of Diophantine equations and explains the relevant concepts in more detail. The next article will prove the MRDP theorem by using Diophantine relations to simulate the operation of a Turing machine. To keep that article to a reasonable length, however, we will have to assume that “exponentiation is Diophantine.” A proof may appear in the article after that—or it may never materialize. The plan, then, is to finish the proof of Hilbert’s Tenth Problem over the next two or three articles. Let us begin.

Two important observations: systems of equations and natural-number solutions

  The first important observation is that solvability of a system of Diophantine equations is equivalent to solvability of a single Diophantine equation.

  This is because the system is equivalent to:

  Expanding the left-hand side above plainly produces another multivariable polynomial with integer coefficients, so the result is still a Diophantine equation. This observation lets us safely “stack” Diophantine equations into systems: in the end, they can always be combined into one.

  The second important observation is that deciding whether an integer solution exists is equivalent to deciding whether a natural-number solution exists. (Here, natural numbers include 0.)

  More precisely, a Diophantine equation = 0 has an integer solution if and only if another Diophantine equation = 0 has a natural-number solution. We can compute from , and conversely. Thus, a Turing machine M that decides the existence of integer solutions can easily be turned into a Turing machine M′ that decides the existence of natural-number solutions, and vice versa. In this sense, the two decision problems have the same difficulty. Natural-number solutions are simply easier for us to handle.

  Here is the proof. Deciding whether has an integer solution is equivalent to deciding whether has a natural-number solution, which immediately establishes one direction. Conversely, suppose we want to decide whether has a natural-number solution. By Lagrange’s four-square theorem—every natural number is a sum of four squares of natural numbers—this is equivalent to deciding whether:

  has an integer solution. A Turing machine can clearly carry out both constructions. This proves the second observation.

  Natural-number solutions will be more convenient, so from this point on we study only the decision problem for their existence.

Diophantine sets

  A Diophantine set is a set of ordered n-tuples of natural numbers for which there exists a Diophantine equation such that:

  has a (natural-number) solution.

  We call the Diophantine equation corresponding to S. Here D is treated like a parametric equation, or a family of Diophantine equations: substituting each into D determines a new Diophantine equation. We call the parameters of D and its unknowns. The parameters determine the arity of the elements in the corresponding Diophantine set, so that arity is essential information about the set. For convenience, however, we usually distinguish parameters from unknowns by using different letters rather than stating the distinction explicitly.

  The reader should know some basic set-theoretic terminology. A relation is a subset of a Cartesian product. Thus, if an n-ary relation on the natural numbers is a Diophantine set, we call it a Diophantine relation.

  Likewise, a multivariable function on the natural numbers is itself represented by a subset of the relevant Cartesian product. Consider the exponential function:

  It is represented by the following set:

  If the set representing a function is Diophantine, we call the function a Diophantine function. To ask whether a function can be expressed by a Diophantine equation is precisely to ask whether it is a Diophantine function.

Elementary properties of Diophantine sets

  We first verify an elementary property of Diophantine sets: they are closed under intersection and union.

  Let be Diophantine sets corresponding to the Diophantine equations and .

  Consider . If , then after substituting , at least one of the two equations has a solution. This is equivalent to:

  having a solution. Hence S is a Diophantine set, with corresponding Diophantine equation:

  Therefore, Diophantine sets are closed under union.

  Now consider . If , an analogous construction makes this equivalent to:

  having a solution. Hence S′ is also a Diophantine set, with corresponding Diophantine equation:

  Thus, Diophantine sets are also closed under intersection.

Recursive sets and recursively enumerable sets

  I do not know whether any reader understands Turing machines but has never encountered recursive or recursively enumerable sets, but I will briefly explain them. A Turing machine’s input can be regarded as a string over a finite alphabet Σ, containing 0, 1, spaces, or any other symbols we choose. Such a string can always be encoded as a natural number by treating it as a base-|Σ| numeral. We may therefore regard a Turing machine as a function on . Given a natural number a, it has three possible behaviors: halt after finite time and output True, halt after finite time and output False, or never halt.

  For a set , suppose there is a Turing machine M such that M outputs True when a ∈ S and False when a ∉ S. Then S is a recursive set, also called decidable. If there is a Turing machine M that outputs True when a ∈ S but never halts when a ∉ S, then S is a recursively enumerable set. A decision problem is decidable when, after encoding each of its instances as a natural number, the set S of codes for instances whose answer is True is recursive.

  The same definitions extend to subsets of , because tuples can also be encoded as integers and thereby treated as a subset of . There is nothing artificial about this encoding: the preceding paragraph already encoded strings as integers. We will later see that the particular encoding does not matter; any computable one will do.

  Every recursive set is recursively enumerable: simply make M enter an infinite loop whenever it would otherwise output False. The converse does not hold. Readers may accept that some recursively enumerable sets are not recursive, or study a little elementary computability theory.

  Returning to our problem, Hilbert’s Tenth Problem asks: “Is the set of all solvable Diophantine equations recursive?” This immediately raises another issue: encoding. We must encode Diophantine equations as natural numbers before we can ask whether a set of such equations is recursive or recursively enumerable. Encoding has appeared repeatedly in the last few paragraphs, so we now discuss it directly.

Encoding

  We will use two kinds of encoding: encoding in a general, unspecified sense, and particular encoding schemes.

  When stating Hilbert’s Tenth Problem, for example, we take a Diophantine equation D as input to a Turing machine. D must therefore be encoded in a form that the machine can receive. Asking whether the set of all solvable Diophantine equations is recursive likewise requires encoding each equation as a natural number. This is encoding in the general sense: we have not specified how it works. Perhaps the coefficient and degree of every term are entered in some format; perhaps something else is done. Nothing has been fixed.

  Why leave this unspecified? Could Hilbert’s Tenth Problem be solvable under one encoding of Diophantine equations but unsolvable under another?

  This issue is not peculiar to Hilbert’s Tenth Problem. It is a basic question in computability theory. The same concern arises when Turing machines themselves are encoded in order to discuss the undecidability of the halting problem: can the encoding affect whether the problem is solvable?

  Computability textbooks usually answer this question. For readers without that background, the conclusion is simple: the choice of encoding does not change the result.

  If two encodings can be converted into one another computably, a Turing machine can perform that conversion as an intermediate step, and solvability under the two encodings is equivalent. By the Church–Turing thesis, we accept that any encoding of Diophantine equations that can actually be computed is obtainable by a Turing-computable procedure. In that sense, all reasonable encodings can be converted into one another, so the answer to Hilbert’s Tenth Problem is independent of the encoding. This is why its statement uses only an unspecified encoding. When solving a concrete problem, we need only choose a particular Turing-computable encoding that is convenient to use.

  Here “reasonable” means, in effect, obtainable. One proposed encoding could simply include the answer, encoding D as (…, True/False). Hilbert’s Tenth Problem would then be trivially solvable. But how did we obtain that answer? The unsolvability of Hilbert’s Tenth Problem, together with the Church–Turing thesis, tells us in return that such an encoding is unreasonable: it cannot be obtained by computation.

  By the same reasoning, we can discuss recursive and recursively enumerable subsets of . How they are encoded as subsets of is immaterial, provided the encoding is computable. We will give one concrete encoding later.

  This completes the necessary preliminaries. In the next article, we prove the MRDP theorem.