42.04.07 · mathematical-logic / computability-degrees

Unsolvable Problems: the Word Problem and Hilbert's Tenth

shipped3 tiersLean: none

Anchor (Master): Matiyasevich 1993 *Hilbert's Tenth Problem* (MIT Press) Ch. 1-6, 10 (the full MRDP arc: Diophantine and exponential-Diophantine sets, the Davis normal form, the Davis-Putnam-Robinson reduction, the Pell equation $x^2-(a^2-1)y^2=1$ giving a Diophantine definition of exponentiation, c.e. $=$ Diophantine, prime-representing polynomials, the undecidability of Hilbert's tenth problem); Lyndon-Schupp 2001 *Combinatorial Group Theory* (Springer Classics in Mathematics) Ch. IV (the Novikov-Boone theorem, the Higman embedding theorem, the Adian-Rabin theorem on Markov properties); Rotman 1995 *An Introduction to the Theory of Groups* 4e (Springer) Ch. 12 (semigroup and group word problems, Britton's lemma, the construction of a finitely presented group with unsolvable word problem); Soare 2016 *Turing Computability* (Springer) Ch. 9-10 (the unsolvable-problems survey: PCP, tiling, the word problems, Hilbert's tenth, and the reduction of $K$ to first-order validity)

Intuition Beginner

The previous unit showed one question has no mechanical answer: will a given program stop or run forever? That impossibility might seem to be a fact only about programs — a quirk of self-reference that stays trapped inside computer science. The surprise of this unit is that the same impossibility leaks out into the rest of mathematics. Honest, old questions that people asked long before computers — about equations in whole numbers, about simplifying expressions in algebra, about fitting tiles together — turn out to have no general method of solution, and the reason is always the halting problem wearing a disguise.

The trick that carries the impossibility across is called a reduction. You show that if you could answer the new question, you could rig up that answer to solve the halting problem too. Since the halting problem has no general solution, neither can the new one. So the new question inherits its impossibility, like a debt passed down.

Two famous old questions fall this way. The first is from algebra. Suppose you have a few basic symbols and a few rules saying which combinations of symbols are equal. Given two longer expressions, are they equal under the rules? This is the word problem, and for the right set of rules no algorithm can always decide it.

The second is from number theory, and it is the most striking. Hilbert's tenth problem, posed in 1900, asked for a procedure to decide whether a polynomial equation — like $x^{2} + y^{2} = z^{2} + 7$ — has a solution in whole numbers. For seventy years people hunted for such a procedure. There is none, and the proof is that every listable set of numbers can be captured exactly by such an equation, so deciding equations would decide everything listable, including halting.

Visual Beginner

Think of the halting problem as a single poison, and reductions as the pipes that carry it from one room of mathematics to another. The halting room is known to be poisoned. A pipe from the halting room to a new room means: if the new room were safe (decidable), you could pump that safety back to the halting room — but the halting room cannot be made safe, so the new room is poisoned too.

                 [ HALTING PROBLEM ]   <- known: no general decision method
                    /     |      \
       reduction   /      |       \   reduction
                  v       v        v
        [ word problem ] [ tiling ] [ Diophantine
          for groups ]   the plane    equations ]
                                       (Hilbert's 10th)

   A pipe  X --> Y  means: "an algorithm for Y would give an algorithm for X."
   Since no algorithm decides HALTING, no algorithm decides any room
   reachable by a pipe out of it.

The Post correspondence game is the easiest pipe to picture. You are given a handful of domino types, each a top word and a bottom word:

domino	top	bottom
1	`a`	`baa`
2	`ab`	`aa`
3	`bba`	`bb`

You may use each type as often as you like, in any order, and you must end with the same string read along the tops as along the bottoms. Finding a winning sequence can be very hard, and the question "does a winning sequence exist?" has no general method — because the dominoes can be built to record, step by step, the run of any program, so that a match exists exactly when the program halts.

Worked example Beginner

We solve one Post correspondence puzzle by hand, to feel why a match is a kind of "successful run," and then say what general impossibility this points to. Take three domino types over the letters a and b:

domino	top	bottom
1	`a`	`ab`
2	`b`	`ca`
3	`c`	`a`

Step 1. Start. We need the same final string on top and bottom. Domino 1 is a good opener because top a is a prefix of bottom ab: after using it, top reads a, bottom reads ab. The bottom is one letter ahead, with an unmatched b.

Step 2. Catch up the b. To cover the extra b, play domino 2, whose top is b. Now top reads ab, bottom reads abca. Bottom is ahead by ca.

Step 3. Cover the c. Play domino 3, top c. Top reads abc, bottom reads abcaa. Bottom is ahead by aa.

Step 4. Cover the remaining letters. Play domino 1 (top a): top abca, bottom abcaab. Then domino 1 again is wrong; instead play domino 3 (top c) — but there is no c next on the bottom, so backtrack. The point is made without forcing a full match: each move is pinned down by what the other row left unmatched.

What this tells us: building a match is exactly like following a forced computation — each step is determined by the "state" left behind, the gap between top and bottom. That is why a list of dominoes can imitate a program, and why no single recipe can decide, for every list, whether a match exists. The puzzle is the halting problem in costume.

Check your understanding Beginner

Formal definition Intermediate+

Fix the standard enumeration ${φ_{e}}$ of partial computable functions, the halting set $K = {e : φ_{e} (e) ↓}$ , and many-one reducibility $\leq_{m}$ from 42.04.02. A decision problem is identified with a set $A \subseteq N$ (or a set of finite strings, encoded into $N$ ); it is decidable if $A$ is computable and undecidable otherwise. The working method throughout is: to prove a problem $B$ undecidable, exhibit a computable reduction witnessing $K \leq_{m} B$ (or $\overline{K} \leq_{m} B$ ), so $B$ inherits undecidability ^{[Soare Ch. 9]}.

A Diophantine set is a set $S \subseteq N^{n}$ for which there is a polynomial $P$ with integer coefficients such that $$ \langle a_1,\dots,a_n\rangle \in S \iff \exists x_1,\dots,x_m \in \mathbb N\ \big[,P(a_1,\dots,a_n,x_1,\dots,x_m) = 0,\big]. $$ The $a_{i}$ are parameters and the $x_{j}$ are unknowns. An exponential-Diophantine set allows $P$ to use the additional binary operation $u^{v}$ . The Diophantine sets are closed under union, intersection, existential projection, and bounded universal quantification; a single equation suffices because $P_{1} = 0 \land P_{2} = 0$ is equivalent to $P_{1}^{2} + P_{2}^{2} = 0$ and $P_{1} = 0 \lor P_{2} = 0$ to $P_{1} P_{2} = 0$ ^{[Matiyasevich Ch. 1]}. Hilbert's tenth problem is the decision problem: given a polynomial $P$ with integer coefficients, does $P = 0$ have a solution in integers (equivalently, after replacing each variable by a difference or by Lagrange four-squares, in naturals)?

A finite presentation of a group is $G = ⟨ x_{1}, \dots, x_{n} ∣ r_{1}, \dots, r_{k} ⟩$ , the quotient of the free group on the $x_{i}$ by the normal closure of the relator words $r_{j}$ . The word problem for $G$ is the decision problem: given a word $w$ in the generators and inverses, does $w = 1$ in $G$ ? The analogous word problem for a finitely presented semigroup (Thue system) asks whether two words are equal under a finite set of defining relations $u_{i} = v_{i}$ rewritable in both directions. A property $P$ of finitely presented groups is a Markov property if it is invariant under isomorphism, some f.p. group has $P$ , and some f.p. group $G_{-}$ embeds in no f.p. group with $P$ .

Counterexamples to common slips Intermediate+

"Hilbert's tenth problem is about whether equations are true." It is about solvability: whether unknowns exist making the equation hold. A fixed equation with all variables quantified is a single sentence with a definite truth value; the problem is the lack of a uniform algorithm across all equations.
"A Diophantine set is anything definable by a polynomial." The defining feature is the existential quantifier over unknowns and the positive equation $P = 0$ . There is no negation, no universal quantifier, and no inequality except as encoded ( $a \leq b$ is $\exists x [a + x = b]$ ). Diophantine sets are exactly the projections of polynomial zero sets, which is why they coincide with the c.e. sets, not with all arithmetically definable sets.
"The word problem is undecidable for all groups." It is undecidable for some finitely presented groups. Free groups, finitely generated abelian groups, hyperbolic groups, and one-relator groups all have solvable word problem. The theorem produces one f.p. group where it fails; the hypothesis "finitely presented" is essential, since a non-recursive presentation deforms the question in the wrong direction.
"Adian-Rabin says every property of presentations is undecidable." It governs Markov properties — isomorphism-invariant properties with the embedding obstruction. Properties of the presentation as a syntactic object (number of generators, length of the longest relator) are decidable. The Markov hypotheses do real work.

Key theorem with proof Intermediate+

The signature result of the unit is the MRDP theorem, which identifies a purely number-theoretic class with a purely computational one and thereby settles Hilbert's tenth problem. Everything else — the word problem, the Post correspondence problem, the tiling problem — is a reduction from $K$ of the same shape.

Theorem (MRDP; Matiyasevich-Robinson-Davis-Putnam). A set $S \subseteq N^{n}$ is Diophantine if and only if it is computably enumerable. Consequently Hilbert's tenth problem is undecidable: there is no algorithm deciding, for an arbitrary integer polynomial $P$ , whether $P = 0$ has a natural-number solution.

Proof. ( $\Rightarrow$ ) Every Diophantine set is c.e.: given $P$ , dovetail over all tuples $⟨ x_{1}, \dots, x_{m} ⟩ \in N^{m}$ and enumerate $⟨ a_{1}, \dots, a_{n} ⟩$ as soon as some tuple makes $P = 0$ . The search is effective, so $S = dom$ of a partial computable function, hence c.e. ^{[Matiyasevich Ch. 1]}.

( $\Leftarrow$ ) Every c.e. set is Diophantine. The argument runs in three movements. First, the Davis normal form: every c.e. set $S$ can be written $$ a \in S \iff \exists z, \forall y \le z, \exists x_1,\dots,x_m\ \big[,Q(a,y,z,x_1,\dots,x_m) = 0,\big] $$ with a single bounded universal quantifier in front of an existential-polynomial matrix, obtained by arithmetising a machine computation via the Kleene predicate and contracting the unbounded quantifiers ^{[Matiyasevich Ch. 3]}. Second, the Davis-Putnam-Robinson theorem: the bounded universal quantifier $\forall y \leq z$ can be eliminated at the cost of admitting the exponential function, so every c.e. set is exponential-Diophantine — definable by a $P = 0$ in which the symbol $u^{v}$ may appear ^{[Matiyasevich Ch. 4]}. The elimination repackages $\forall y \leq z (\dots)$ as a single congruence statement about a product $\prod_{y \leq z}$ , encoded by binomial-coefficient and factorial identities that are exponential-Diophantine. Third, Matiyasevich's step: the relation $y = x^{n}$ is itself Diophantine. The solutions of the Pell equation $u^{2} - (a^{2} - 1) v^{2} = 1$ form a sequence growing exponentially in $a$ and satisfying linear recurrences; the congruence and divisibility relations among these solutions pin exponentiation down by a polynomial system without the exponential symbol ^{[Matiyasevich Ch. 5]}. Substituting the Diophantine definition of exponentiation into the exponential-Diophantine definition removes every occurrence of $u^{v}$ , leaving an ordinary polynomial equation. Hence every c.e. set is Diophantine.

For the corollary, take an $m$ -complete c.e. set, $K$ itself. By the equivalence there is a polynomial $P_{K} (a, x)$ with $a \in K ⟺ \exists x [P_{K} (a, x) = 0]$ . An algorithm deciding solvability of arbitrary Diophantine equations would, applied to $P_{K} (a, x)$ for each $a$ , decide $a \in K$ , contradicting the undecidability of $K$ from 42.04.02. So no such algorithm exists. $□$

Bridge. This theorem is the foundational reason undecidability is not confined to the theory of computation: it shows that the c.e. sets, defined by unbounded search, coincide exactly with the Diophantine sets, defined by polynomial solvability, so the halting problem reappears verbatim as a question about whole-number equations. The Pell-equation construction that makes exponentiation Diophantine is exactly the number-theoretic engine that lets a single polynomial simulate a Turing machine, and this is exactly the move — encode a computation as an algebraic object — that reappears again in the word problem, where machine configurations become group words, and in the Post correspondence problem, where they become matching dominoes. The reduction $K \leq_{m} (Hilbert’s tenth)$ builds toward the Adian-Rabin theorem, where the same encoding shows that nearly every natural property of finitely presented groups is undecidable, and it appears again in the undecidability of first-order validity, where a halting computation becomes a logical sentence (Church's theorem, cross-ref 42.01.10 pending). The central insight is that arithmetic, algebra, and combinatorics are each rich enough to host a universal machine, so putting these together one impossibility — the halting problem of 42.04.02 — casts a shadow into every one of them at once.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that the order relation $a \leq b$ and the divisibility relation $d ∣ n$ are Diophantine, and conclude that the set of non-powers-of-two is Diophantine without using MRDP.

Hint

$a \leq b$ means some natural fills the gap. $d ∣ n$ means some natural is the quotient.

Answer

$a \leq b ⟺ \exists x [a + x = b]$ over $N$ , a single linear equation $a + x - b = 0$ . Divisibility $d ∣ n ⟺ \exists q [n = d q]$ , the equation $n - d q = 0$ . For non-powers-of-two: $n$ is not a power of two iff $n$ has an odd factor exceeding $1$ , i.e. $\exists q \exists k [n = q (2 k + 3)]$ (an odd number $\geq 3$ is $2 k + 3$ ), giving $n - q (2 k + 3) = 0$ . (The empty product convention is handled by requiring $q \geq 1$ , encodable as $q = q^{'} + 1$ .) Each is an existential over a polynomial equation, hence Diophantine. Rubric: full credit for the linear gap-filler for $\leq$ , the quotient witness for $∣$ , and an odd-factor existential for non-powers-of-two.

Exercise 4 (medium, symbolic).

Assuming MRDP, prove there is a polynomial $U (a, e, x)$ with integer coefficients such that for every c.e. set $W_{e}$ , $a \in W_{e} ⟺ \exists x [U (a, e, x) = 0]$ — a universal Diophantine equation. Explain why this single equation already gives the undecidability of Hilbert's tenth problem.

Hint

Apply MRDP to the single c.e. set ${⟨ a, e ⟩ : a \in W_{e}}$ .

Answer

The set $V = {⟨ a, e ⟩ : a \in W_{e}} = {⟨ a, e ⟩ : φ_{e} (a) ↓}$ is c.e. (dovetail). By MRDP it is Diophantine: there is $U$ with $⟨ a, e ⟩ \in V ⟺ \exists x [U (a, e, x) = 0]$ . Fixing $e$ recovers each $W_{e}$ . Undecidability of Hilbert's tenth: deciding solvability of $U (a, e, x) = 0$ for varying $⟨ a, e ⟩$ would decide $V$ , hence (taking $e$ an index for $K$ ) would decide $K$ . Since $K$ is undecidable, no algorithm decides solvability even of this one parametrised family, let alone of arbitrary equations. Rubric: full credit for applying MRDP to the universal c.e. set and reducing $K$ to solvability of the resulting equation.

Exercise 5 (medium, multiple-choice).

The Adian-Rabin theorem implies which of the following is undecidable for finitely presented groups given by a presentation?

Whether the presentation has more than five generators.
Whether the group is the one-element group.
Whether the longest relator has even length.
Whether the presentation lists exactly three relators.

Hint

Markov properties are isomorphism-invariant with an embedding obstruction. Which option is a property of the group, not the syntax?

Answer

B. Being the one-element group is isomorphism-invariant, holds for that group, and the embedding obstruction is met (a larger f.p. group does not embed in the one-element group), so it is a Markov property and undecidable by Adian-Rabin. Options A, C, D are syntactic properties of the presentation string, decidable by inspection, and not isomorphism-invariant.

Exercise 6 (hard, symbolic).

Prove the Post correspondence problem (PCP) is undecidable, given that the halting problem for Turing machines is undecidable. Sketch the computation-history encoding.

Hint

Make a domino sequence build, on top and bottom offset by one configuration, the successive configurations of the machine, so a full match forces the run to reach a halting configuration.

Answer

Reduce machine-halting to PCP. Given a Turing machine $M$ and input $w$ , build a domino list over an alphabet containing the tape symbols, the states, and a separator $#$ . The dominoes are designed so that any partial match has the bottom string one configuration ahead of the top: the top spells $# C_{0} # C_{1} # \dots # C_{t}$ and the bottom $# C_{0} # C_{1} # \dots # C_{t} # C_{t + 1}$ , where $C_{i + 1}$ is the configuration following $C_{i}$ under $M$ 's transition function. "Copy" dominoes $\frac{x}{x}$ carry unchanged tape cells forward; "transition" dominoes near the state symbol encode one step of $M$ ; a starting domino seeds $# C_{0}$ with $C_{0}$ the initial configuration on $w$ ; and "halting" dominoes, available only once a halting state appears, let the top finally catch up to the bottom by consuming the tape around the halting state. A complete match exists iff the configuration sequence reaches a halting state, i.e. iff $M$ halts on $w$ . Thus halting $\leq_{m}$ PCP, so PCP is undecidable. (A technicality forces the first domino; the standard fix uses a marked variant, MPCP, then reduces MPCP to PCP.) Rubric: full credit for the offset computation-history idea, the three domino kinds (copy, transition, halt), and the equivalence "match exists iff $M$ halts."

Exercise 7 (hard, symbolic).

Show that the word problem for finitely presented semigroups (Thue systems) is undecidable by reducing the halting problem, and explain in one sentence why the group case (Novikov-Boone) is strictly harder.

Hint

Encode a Turing-machine configuration as a word; make each defining relation $u_{i} = v_{i}$ a rewrite that performs one machine step. A word equals the halting word iff the machine halts.

Answer

Represent a configuration of $M$ — tape contents, head position, state — as a word over an alphabet of tape symbols and state symbols, with the state symbol placed just left of the scanned cell. For each transition of $M$ introduce a defining relation $u_{i} = v_{i}$ where $u_{i}$ is the local pattern (state symbol plus adjacent tape symbol) and $v_{i}$ is its image after one step; add relations collapsing a halting configuration to a fixed word $h$ . Then the word $w_{0}$ coding the initial configuration on input satisfies $w_{0} = h$ in the semigroup iff some sequence of rewrites (machine steps) reaches a halting configuration, i.e. iff $M$ halts. Since the rewrites are reversible as semigroup relations, equality in the Thue system matches reachability, giving halting $\leq_{m}$ (semigroup word problem); this is the Markov-Post theorem. The group case is harder because in a group every generator is invertible and relations can be applied with inverses, so a naive rewrite is no longer one-directional; controlling cancellation requires the HNN-extension machinery and Britton's lemma, which is the content of the Novikov-Boone construction. Rubric: full credit for the configuration-as-word encoding, transitions-as-relations, the halting-word collapse, and the one-sentence reason inverses make the group case harder.

Advanced results Master

The reductions of the Key theorem are one half of the subject; the other half is the machinery that makes a finitely presented group, rather than a recursively presented one, carry the undecidability — Higman embedding — and the sweeping conclusion that the obstruction is generic — Adian-Rabin. The results below assemble the group-theoretic arc, sharpen MRDP into its number-theoretic consequences, and close the loop back to logic.

Theorem 1 (Novikov-Boone). There is a finitely presented group $G = ⟨ x_{1}, \dots, x_{n} ∣ r_{1}, \dots, r_{k} ⟩$ whose word problem is undecidable ^{[Lyndon-Schupp Ch. IV]}. The construction encodes a semigroup (Thue system) with unsolvable word problem — available from the Markov-Post theorem — into a group by a tower of HNN extensions. The governing tool is Britton's lemma: in an HNN extension $⟨ H, t ∣ t^{- 1} a t = ϕ (a) (a \in A)⟩$ , a word containing the stable letter $t$ that equals an element of the base $H$ must contain a pinch $t^{- 1} c t$ or $t c t^{- 1}$ with $c$ in the associated subgroup. Iterating, a word in $G$ reduces to $1$ exactly when a controlled sequence of pinches mirrors a halting computation of the encoded machine, so deciding $w = 1$ would decide halting. The group is explicit and finite: undecidability lives inside a single finite list of relations.

Theorem 2 (Higman embedding theorem). A finitely generated group has a recursively enumerable set of defining relations if and only if it embeds in a finitely presented group ^{[Lyndon-Schupp Ch. IV]}. The reverse direction is immediate; the forward direction is the deep one and is what upgrades a recursively presented group built directly from a machine into a finitely presented one — the c.e. list of relations is internalised by finitely many relations plus auxiliary generators that simulate the enumeration. Higman's theorem is the structural reason Novikov-Boone can be stated with a finite presentation: the undecidability is first built recursively, then embedded. It also yields an algebraic characterisation of computability — the finitely generated groups embeddable in finitely presented groups are exactly the recursively presented ones — making "c.e." a property visible in pure group theory.

Theorem 3 (Adian-Rabin). Let $P$ be a Markov property of finitely presented groups. Then ${$ presentations of groups with $P}$ is undecidable ^{[Lyndon-Schupp Ch. IV]}. Given the witnessing groups $G_{+}$ (has $P$ ) and $G_{-}$ (embeds in no group with $P$ ), one builds, uniformly from a word $w$ in a group with unsolvable word problem, a presentation $G_{w}$ that is isomorphic to a group with $P$ when $w = 1$ and contains a copy of $G_{-}$ (so lacks $P$ ) when $w \neq = 1$ . Deciding $P$ would decide $w = 1$ , which is impossible. The properties trapped by this single theorem include being the one-element group, finite, abelian, nilpotent, solvable, free, torsion-free, simple, having solvable word problem, and being isomorphic to any fixed group: each is a Markov property, so each is undecidable from a presentation.

Theorem 4 (consequences of MRDP in number theory). Three corollaries follow from Diophantine $=$ c.e. ^{[Matiyasevich Ch. 6]}. First, every c.e. set $S$ is the set of nonnegative values of a polynomial: there is $Q$ with integer coefficients whose nonnegative outputs over $N$ -tuples are exactly $S$ , obtained from $a - (1 + P (a, x)^{2}) \cdot (slack)$ so that positivity forces $P = 0$ . Applied to the primes, this yields a prime-representing polynomial — a polynomial in several variables whose positive values, as the arguments range over $N$ , are precisely the prime numbers (Jones-Sato-Wada-Wiens exhibited one of degree $25$ in $26$ variables). Second, there is a universal Diophantine equation: a single polynomial $U (a, e, x)$ enumerating all c.e. sets as $e$ varies. Third, the threshold for unsolvability is low: the undecidable instances can be taken with bounded degree and a bounded number of unknowns, so even narrow Diophantine families have no decision procedure.

Theorem 5 (the Diophantine form of incompleteness; the bridge to logic). For any consistent, computably axiomatised theory $T$ extending a weak base for arithmetic there is a polynomial $P_{T}$ with no natural-number solution such that $T$ does not prove " $P_{T} = 0$ has no solution" ^{[Matiyasevich Ch. 10]}. This is Gödel's first incompleteness theorem 42.01.09 pending rephrased without any syntactic self-reference: undecidability of $K$ supplies, via MRDP, an equation whose unsolvability is true but unprovable. The same arithmetisation reduces $K$ to the set of valid first-order sentences — from a machine and input one writes a sentence valid iff the machine halts — so first-order validity is undecidable, which is Church's theorem on the Entscheidungsproblem (cross-ref 42.01.10 pending).

Synthesis. The undecidability landscape outside computation theory is connected, not scattered, and the foundational reason is that arithmetic, finitely presented algebra, and one-dimensional combinatorics are each universal: a Turing machine can be simulated by a polynomial equation, by a group word, or by a domino sequence, so the single diagonal at $K$ from 42.04.02 is exactly what makes Hilbert's tenth problem, the word problem, and the Post correspondence problem undecidable at once. MRDP is the sharpest instance — Diophantine $=$ c.e. is dual to the halting set in the precise sense that the unbounded search defining a c.e. set is the existential quantifier defining a Diophantine set, and Matiyasevich's Pell-equation construction is the central insight that exponential growth is algebraic, which is what lets a polynomial count computation steps. Putting these together with Higman embedding, the c.e. relations of a recursively built group are internalised into a finite presentation, so undecidability lives in a finite object, and Adian-Rabin then shows the obstruction is generic: every Markov property of finitely presented groups is undecidable, which generalises the single Novikov-Boone group to the whole isomorphism-invariant landscape. The bridge from this algebraic and arithmetic picture back to logic is the same arithmetisation read in the language of provability and validity — the Diophantine form of incompleteness 42.01.09 pending and Church's theorem on first-order validity 42.01.10 pending are the logical face of the halting problem, with MRDP supplying the polynomial that Gödel's self-referential sentence supplies syntactically.

Full proof set Master

Proposition 1 (Diophantine sets are c.e.). Every Diophantine set is computably enumerable.

Proof. Let $S = {a : \exists x [P (a, x) = 0]}$ with $P$ an integer polynomial. Define a partial computable $ψ$ on $a$ that dovetails over all $x \in N^{m}$ , evaluating the integer $P (a, x)$ at each, and halts at the first $x$ with $P (a, x) = 0$ . Then $dom (ψ) = S$ , so $S$ is c.e. The same argument with parameters shows a Diophantine subset of $N^{n}$ is c.e. as a set of codes of tuples. $□$

Proposition 2 (closure of Diophantine sets). The Diophantine subsets of $N^{n}$ are closed under finite union, finite intersection, and existential projection; a single equation suffices for any finite system.

Proof. Let $S_{i} = {a : \exists x_{i} [P_{i} (a, x_{i}) = 0]}$ for $i = 1, 2$ with disjoint unknown-tuples. Intersection: $a \in S_{1} \cap S_{2} ⟺ \exists x_{1} \exists x_{2} [P_{1} = 0 \land P_{2} = 0] ⟺ \exists x_{1} x_{2} [P_{1}^{2} + P_{2}^{2} = 0]$ , since over $Z$ a sum of two squares vanishes iff both do. Union: $a \in S_{1} \cup S_{2} ⟺ \exists x_{1} x_{2} [P_{1} P_{2} = 0]$ , since a product vanishes iff a factor does. Existential projection: if $S = {⟨ a, b ⟩ : \exists x [P = 0]}$ then ${a : \exists b ⟨ a, b ⟩ \in S} = {a : \exists b \exists x [P = 0]}$ , again a single existential block over one equation. Composing, any finite Boolean-positive combination with projections reduces to one polynomial equation under one existential quantifier. $□$

Proposition 3 (MRDP, hard direction, modular structure). Every c.e. set is Diophantine, given (i) the Davis normal form, (ii) the Davis-Putnam-Robinson elimination of the bounded universal quantifier into exponential-Diophantine form, and (iii) the Diophantineness of exponentiation.

Proof. Let $S$ be c.e. By (i) there is an integer polynomial $Q$ with $$ a \in S \iff \exists z, \forall y \le z, \exists \vec x, [Q(a, y, z, \vec x) = 0]. $$ By (ii) the prefix $\exists z \forall y \leq z \exists x [Q = 0]$ is equivalent to an exponential-Diophantine condition $\exists u [R (a, u) = 0]$ , where $R$ is built from $+, \cdot$ and finitely many exponential terms $s^{t}$ ; the elimination encodes the bounded product $\prod_{y \leq z}$ controlling the universal quantifier through factorial and binomial-coefficient identities that are exponential-Diophantine. By (iii) the graph ${⟨ p, q, r ⟩ : r = p^{q}}$ is Diophantine, say defined by $\exists w [E (p, q, r, w) = 0]$ . Replace each exponential term $s^{t}$ occurring in $R$ by a fresh unknown $r$ together with the conjunct $E (s, t, r, w) = 0$ ; by Proposition 2 the augmented system is a single polynomial equation under one existential block, with no exponential symbol. This is a Diophantine definition of $S$ . $□$

Proposition 4 (exponentiation is Diophantine via Pell). The relation $r = a^{n}$ is Diophantine.

Proof (structure). For $a \geq 2$ consider the Pell equation $u^{2} - (a^{2} - 1) v^{2} = 1$ and let $⟨ u_{k} (a), v_{k} (a)⟩$ enumerate its nonnegative solutions in increasing order, so $v_{0} = 0, v_{1} = 1$ , and $v_{k + 1} = 2 a v_{k} - v_{k - 1}$ . The sequence $v_{k} (a)$ grows like $(2 a)^{k}$ and satisfies a battery of relations each Diophantine in $⟨ a, k, v_{k} ⟩$ : divisibility properties $v_{k} ∣ v_{k ℓ}$ , the congruence $v_{k} (a) \equiv k (mod a - 1)$ , step-comparison $u_{k} - v_{k} (a - y) \equiv \dots$ , and a "masking" congruence isolating $k$ from $v_{k}$ . Robinson's earlier work reduced "exponentiation is Diophantine" to the existence of any Diophantine relation of roughly exponential growth obeying two growth conditions; the Pell sequence supplies it. Assembling these congruences yields a polynomial system $E (a, n, r, w) = 0$ solvable iff $r = a^{n}$ , using the closure of Proposition 2 to fold the finitely many congruence and divisibility conditions (each Diophantine by Exercise 3-style witnesses) into one equation. The cases $a \in {0, 1}$ are handled separately by the equations $r = [n = 0]$ and $r = 1$ . Hence $r = a^{n}$ is Diophantine. $□$

Proposition 5 (undecidability of Hilbert's tenth problem). There is no algorithm that decides, for an arbitrary integer polynomial $P$ , whether $P = 0$ has a solution in $N$ (equivalently in $Z$ ).

Proof. By Propositions 3-4, the c.e. set $K$ is Diophantine: there is $P_{K}$ with $a \in K ⟺ \exists x [P_{K} (a, x) = 0]$ . An algorithm $D$ deciding solvability of arbitrary integer polynomial equations would decide $K$ by running $D$ on the instance $P_{K} (a, x) = 0$ (with $a$ a fixed coefficient) and returning its verdict; this contradicts the undecidability of $K$ from 42.04.02. The natural-number and integer versions are interreducible: a natural-number unknown $x$ becomes $x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2}$ by Lagrange, and an integer unknown becomes a difference of two naturals, so neither version is decidable. $□$

Proposition 6 (Markov-Post; semigroup word problem is undecidable). There is a finite Thue system whose word problem is undecidable.

Proof. Fix a Turing machine $M$ with $K$ -complete halting problem. Encode each configuration of $M$ as a word over an alphabet $Σ$ of tape symbols and a disjoint set of state symbols, the state symbol immediately left of the scanned cell, flanked by an endmarker. For each transition $(state p, read s) \to (state q, write s^{'}, move)$ introduce a defining relation equating the local pattern before the step to the local pattern after; add relations contracting any configuration in a halting state to a single fixed symbol $h$ . The relations are reversible (a Thue system is symmetric), and a derivation $w_{0} \leftrightarrow^{*} h$ corresponds to a sequence of forward or backward machine steps from the initial configuration $w_{0}$ ; by determinism the only way to reach $h$ is the forward halting run. Hence $w_{0} = h$ in the semigroup iff $M$ halts on its input, so deciding the word problem would decide $K$ . Thus the word problem for this finite Thue system is undecidable. $□$

Proposition 7 (every c.e. set is a polynomial value-set). For every c.e. set $S \subseteq N$ there is an integer polynomial $Q$ such that $S = {Q (x) : x \in N^{m}, Q (x) \geq 0}$ — the set of nonnegative values of $Q$ .

Proof. By MRDP take $P$ with $n \in S ⟺ \exists x [P (n, x) = 0]$ . Set $$ Q(n, \vec x) = n \cdot \big(1 - P(n, \vec x)^2\big) - 1. $$ If $P (n, x) = 0$ then $Q (n, x) = n - 1$ , but to land exactly on $S$ use instead $Q (n, x) = (n + 1) (1 - P (n, x)^{2}) - 1$ : when $P = 0$ this equals $n$ , and when $P \neq = 0$ then $P^{2} \geq 1$ so $1 - P^{2} \leq 0$ , forcing $Q \leq - 1 < 0$ . Thus the nonnegative values of $Q$ over $N^{m + 1}$ are exactly the $n$ with some $x$ giving $P (n, x) = 0$ , i.e. exactly $S$ . Applied to $S =$ the primes, this yields a prime-representing polynomial whose positive values are the primes. $□$

Connections Master

The halting problem and the recursion theorem 42.04.02 supply the single undecidable set $K$ that every reduction in this unit starts from: the diagonal that makes $K$ uncomputable is what the MRDP polynomial, the Novikov-Boone group, and the Post correspondence dominoes each encode. That unit owns the abstract undecidability and the $m$ -completeness of $K$ ; this unit owns its projection onto concrete arithmetic, algebra, and combinatorics, turning "the halting problem is hard" into "these specific classical questions are unsolvable."
Computably enumerable sets 42.04.03 are exactly the class MRDP identifies with the Diophantine sets: the equivalence Diophantine $=$ c.e. is the headline of this unit and rests on the c.e.-set theory built there — the equivalent characterisations, the normal forms, and the fact that $K$ is a c.e. set with non-c.e. complement (which is why $\overline{K}$ is not Diophantine, so the Diophantine sets are not closed under complement). That unit owns the structure theory of c.e. sets; this unit owns their number-theoretic incarnation.
The Pell equation and continued fractions 21.01.08 provide the number theory that Matiyasevich's step depends on: the solutions of $u^{2} - (a^{2} - 1) v^{2} = 1$ and their recurrence are exactly the exponentially growing Diophantine sequence used to define exponentiation. That number-theory unit owns the Pell solution theory in its own right; this unit applies it as the engine that makes exponentiation, and therefore every c.e. set, Diophantine.
Gödel incompleteness 42.01.09 pending and Church's theorem 42.01.10 pending are the logical face of the same arithmetisation: MRDP gives the Diophantine form of incompleteness — a polynomial with no solutions that a consistent theory cannot prove has none — and the reduction of $K$ to first-order validity gives the undecidability of the Entscheidungsproblem. Those units own the syntactic and semantic sides of undecidability in logic; this unit supplies the equation and the reduction that make incompleteness and Church's theorem concrete consequences of the halting diagonal.

Historical & philosophical context Master

Hilbert posed the tenth of his twenty-three problems in his 1900 address to the International Congress of Mathematicians: to devise a process deciding, in finitely many operations, whether a Diophantine equation has a solution in integers. The problem presupposed that such a process existed; the twentieth-century answer was that it cannot. The decisive line of attack came from Martin Davis, who in his 1950 thesis conjectured that the Diophantine sets coincide with the c.e. sets and proved the normal form reducing every c.e. set to one bounded universal quantifier over an existential-polynomial matrix ^{[Matiyasevich Ch. 3]}. Julia Robinson, working from the late 1940s, isolated the role of exponential growth, showing that a single Diophantine relation of roughly exponential growth would make exponentiation Diophantine — the "Julia Robinson hypothesis." Davis, Hilary Putnam, and Robinson combined these in 1961 to prove every c.e. set exponential-Diophantine. The final step waited until 1970, when the twenty-two-year-old Yuri Matiyasevich showed the Fibonacci and Pell relations supply the missing exponential-growth Diophantine relation, completing the theorem now abbreviated MRDP ^{[Matiyasevich Ch. 5]}.

The algebraic side developed in parallel. Axel Thue posed the word problem for semigroups in 1914; Andrey Markov and Emil Post independently proved it unsolvable in 1947 by encoding Turing machines into Thue systems ^{[Soare Ch. 9]}. The group case resisted longer because inverses destroy the one-directionality of semigroup rewriting; Pyotr Novikov announced an unsolvable word problem for a finitely presented group in 1955, with a full proof, and William Boone gave an independent construction completed in 1958, both controlling cancellation through HNN extensions and what is now called Britton's lemma ^{[Lyndon-Schupp Ch. IV]}. Graham Higman's 1961 embedding theorem tied the algebra to computability by characterising the finitely-generated subgroups of finitely presented groups as exactly the recursively presented ones. Sergei Adian and Michael Rabin, around 1955-1958, generalised Novikov-Boone to show that every Markov property of finitely presented groups is undecidable, so the unsolvability is not a feature of one contrived group but of nearly every natural group-theoretic property.

Bibliography Master

@incollection{hilbert1900problems,
  author    = {Hilbert, David},
  title     = {Mathematische {Probleme}},
  booktitle = {Nachrichten von der K\"{o}niglichen Gesellschaft der Wissenschaften zu G\"{o}ttingen, Mathematisch-Physikalische Klasse},
  year      = {1900},
  pages     = {253--297}
}

@article{davis1953arithmetical,
  author  = {Davis, Martin},
  title   = {Arithmetical problems and recursively enumerable predicates},
  journal = {The Journal of Symbolic Logic},
  volume  = {18},
  number  = {1},
  year    = {1953},
  pages   = {33--41}
}

@article{davisputnamrobinson1961,
  author  = {Davis, Martin and Putnam, Hilary and Robinson, Julia},
  title   = {The decision problem for exponential {Diophantine} equations},
  journal = {Annals of Mathematics},
  volume  = {74},
  number  = {3},
  year    = {1961},
  pages   = {425--436}
}

@article{matiyasevich1970enumerable,
  author  = {Matiyasevich, Yuri V.},
  title   = {Enumerable sets are {Diophantine}},
  journal = {Doklady Akademii Nauk SSSR},
  volume  = {191},
  year    = {1970},
  pages   = {279--282}
}

@article{robinson1952existential,
  author  = {Robinson, Julia},
  title   = {Existential definability in arithmetic},
  journal = {Transactions of the American Mathematical Society},
  volume  = {72},
  number  = {3},
  year    = {1952},
  pages   = {437--449}
}

@article{novikov1955algorithmic,
  author  = {Novikov, Pyotr S.},
  title   = {On the algorithmic unsolvability of the word problem in group theory},
  journal = {Trudy Matematicheskogo Instituta imeni V. A. Steklova},
  volume  = {44},
  year    = {1955},
  pages   = {1--143}
}

@article{boone1959word,
  author  = {Boone, William W.},
  title   = {The word problem},
  journal = {Annals of Mathematics},
  volume  = {70},
  number  = {2},
  year    = {1959},
  pages   = {207--265}
}

@article{higman1961subgroups,
  author  = {Higman, Graham},
  title   = {Subgroups of finitely presented groups},
  journal = {Proceedings of the Royal Society of London A},
  volume  = {262},
  number  = {1311},
  year    = {1961},
  pages   = {455--475}
}

@article{post1946correspondence,
  author  = {Post, Emil L.},
  title   = {A variant of a recursively unsolvable problem},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {52},
  number  = {4},
  year    = {1946},
  pages   = {264--268}
}

@article{jonessatowadawiens1976,
  author  = {Jones, James P. and Sato, Daihachiro and Wada, Hideo and Wiens, Douglas},
  title   = {Diophantine representation of the set of prime numbers},
  journal = {The American Mathematical Monthly},
  volume  = {83},
  number  = {6},
  year    = {1976},
  pages   = {449--464}
}

@book{matiyasevich1993hilbert,
  author    = {Matiyasevich, Yuri V.},
  title     = {Hilbert's Tenth Problem},
  series    = {Foundations of Computing},
  publisher = {MIT Press},
  year      = {1993}
}

@book{lyndonschupp2001,
  author    = {Lyndon, Roger C. and Schupp, Paul E.},
  title     = {Combinatorial Group Theory},
  series    = {Classics in Mathematics},
  publisher = {Springer},
  year      = {2001}
}

@book{rotman1995introduction,
  author    = {Rotman, Joseph J.},
  title     = {An Introduction to the Theory of Groups},
  edition   = {4},
  publisher = {Springer},
  year      = {1995}
}

@book{soare2016turing,
  author    = {Soare, Robert I.},
  title     = {Turing Computability: Theory and Applications},
  series    = {Theory and Applications of Computability},
  publisher = {Springer},
  year      = {2016}
}

Prerequisites

42.04.02

Tier anchors

beginner: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 2, 9 (read the informal account of how the single undecidable halting problem is smuggled into a question about something else — a puzzle with sliding tiles, a list of word pairs, an equation in whole numbers — so the new question inherits the impossibility); Sipser 2013 *Introduction to the Theory of Computation* 3e (Cengage) §5.2 for the Post correspondence problem stated as a domino-matching game before any reduction is run
intermediate: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 9-10 (reductions from the halting set into concrete mathematics: the Post correspondence problem via computation histories, the word problem for semigroups and the Novikov-Boone theorem for groups, the statement of the MRDP theorem that the Diophantine sets are exactly the c.e. sets); Matiyasevich 1993 *Hilbert's Tenth Problem* (MIT Press) Ch. 1-4 (Diophantine sets, the Davis normal form, the Davis-Putnam-Robinson theorem on exponential-Diophantine relations, and the Pell-equation construction of exponentiation)
master: Matiyasevich 1993 *Hilbert's Tenth Problem* (MIT Press) Ch. 1-6, 10 (the full MRDP arc: Diophantine and exponential-Diophantine sets, the Davis normal form, the Davis-Putnam-Robinson reduction, the Pell equation $x^2-(a^2-1)y^2=1$ giving a Diophantine definition of exponentiation, c.e. $=$ Diophantine, prime-representing polynomials, the undecidability of Hilbert's tenth problem); Lyndon-Schupp 2001 *Combinatorial Group Theory* (Springer Classics in Mathematics) Ch. IV (the Novikov-Boone theorem, the Higman embedding theorem, the Adian-Rabin theorem on Markov properties); Rotman 1995 *An Introduction to the Theory of Groups* 4e (Springer) Ch. 12 (semigroup and group word problems, Britton's lemma, the construction of a finitely presented group with unsolvable word problem); Soare 2016 *Turing Computability* (Springer) Ch. 9-10 (the unsolvable-problems survey: PCP, tiling, the word problems, Hilbert's tenth, and the reduction of $K$ to first-order validity)

References

Matiyasevich, Yu. V. — Hilbert's Tenth Problem · MIT Press, Foundations of Computing (1993). Ch. 1-2 define a Diophantine set as the set of parameter values $\langle a_1,\dots,a_n\rangle$ for which a polynomial equation $P(a_1,\dots,a_n,x_1,\dots,x_m)=0$ with integer coefficients has a solution in the unknowns $x_1,\dots,x_m$ over the natural numbers, and show the Diophantine sets are closed under union, intersection, projection, and bounded quantification; Ch. 3 develops exponential-Diophantine relations (those defined by such equations with the additional symbol of exponentiation $a^b$) and proves the Davis normal form, that every c.e. set is $\{a : \exists z\, \forall y \le z\, \exists x_1\dots x_m\, [P=0]\}$ with a single bounded universal quantifier; Ch. 4 proves the Davis-Putnam-Robinson theorem that the single bounded universal quantifier can be eliminated in favour of exponentiation, so the exponential-Diophantine sets are exactly the c.e. sets; Ch. 5 is Matiyasevich's 1970 construction showing the relation $y = x^n$ (and hence exponentiation) is itself Diophantine, via the Pell equation $x^2-(a^2-1)y^2=1$ whose solutions grow at an exponential rate satisfying second-order recurrences expressible by congruences and divisibilities, completing the proof that the Diophantine sets equal the c.e. sets (the MRDP theorem); Ch. 6 derives the unsolvability of Hilbert's tenth problem, the existence of a prime-representing polynomial whose positive values are exactly the primes, the universal Diophantine equation, and a Diophantine equation with no algorithm to decide solvability; Ch. 10 connects to logic via the Diophantine form of Gödel incompleteness, that for any consistent axiomatised theory there is a Diophantine equation with no solutions which the theory cannot prove has no solutions.
Lyndon, R. C. and Schupp, P. E. — Combinatorial Group Theory · Springer, Classics in Mathematics (2001 reprint of the 1977 edition). Ch. IV develops the word problem for groups: a finite presentation $\langle x_1,\dots,x_n \mid r_1,\dots,r_k\rangle$ has solvable word problem if there is an algorithm deciding, for an arbitrary word $w$ in the generators and their inverses, whether $w=1$ in the group; the Novikov 1955 and Boone 1958 theorem constructs a finitely presented group with unsolvable word problem by encoding the halting computations of a Turing machine (equivalently a Thue system / semigroup with unsolvable word problem, after Markov 1947 and Post 1947) into the relations, using HNN extensions and Britton's lemma to control when a word reduces to the identity; the Higman embedding theorem (a finitely generated group is recursively presented iff it embeds in a finitely presented group) and its use to internalise the c.e. construction; the Adian-Rabin theorem that any Markov property of finitely presented groups — any property preserved under isomorphism, possessed by at least one f.p. group and excluded by embedding into another — is undecidable, so triviality, finiteness, abelianness, freeness, and being torsion-free are each undecidable from a presentation.
Soare, R. I. — Turing Computability: Theory and Applications · Springer, Theory and Applications of Computability (2016). Ch. 9-10 collect the classical applications of undecidability outside computability theory proper: the Post correspondence problem (PCP), given finite lists $(g_1,\dots,g_k)$ and $(h_1,\dots,h_k)$ of words over an alphabet, asks whether some nonempty sequence of indices $i_1\dots i_p$ satisfies $g_{i_1}\cdots g_{i_p} = h_{i_1}\cdots h_{i_p}$, proved undecidable by reducing the halting problem through Turing-machine computation histories so that a match codes an accepting run; the tiling (domino) problem of whether a finite set of Wang tiles tiles the plane, undecidable by simulating a machine on successive rows; the mortality problem for finite sets of integer matrices (is the zero matrix a product?), undecidable by encoding PCP; Rice-type undecidability for context-free grammars (ambiguity, equivalence, universality); and the reduction of the halting set $K$ to the set of valid first-order sentences, giving Church's theorem on the Entscheidungsproblem, together with the statement of the Novikov-Boone and MRDP results as the algebraic and number-theoretic faces of the same phenomenon.

Estimated time

beginner: 20m
intermediate: 55m
master: 95m