1. Turing machines

  A Turing machine, introduced by A. Turing, [7], is a way to formalize the idea of an algorithm. We will only need an informal description. A Turing machine is a finite program with an unbounded tape: on any particular finite computation it visits only finitely many tape cells, but there is no fixed a priori memory bound. It does not execute infinitely fast. Rather, computability theory asks whether it halts after finitely many discrete steps, without imposing a bound on the number of steps.

  Visually, a Turing machine $ T $ can be viewed as a string of code, which is equivalent to a finite piece of tape:

\[1, 0, 0, 1, 1, 1\]

Its memory $ M $ is likewise a piece of tape, but this time infinite, although at any point during the computation, it can only contain finitely many 1's:

\[\dots, 0, 0, 0, 1, 1, 0, 1\]

Thus, $ M $ is initialized to some infinite sequence containing finitely many 1's, and then $ T $ acts on $ M $ until it halts; it is also possible that the machine does not halt.

  Fix an effective encoding of Turing machines and finite inputs by natural numbers. We write $T_e$ for the machine with code $e\in\mathbb N$ and $T_e(a)$ for its computation on input $a\in\mathbb N$. The notation $T_e(a)$ denotes an output only when the machine halts; a nonhalting computation has no output.

  Let $P\subseteq\mathbb N$. A Turing machine decides $P$ if it halts on every input $a$, returning $1$ when $a\in P$ and $0$ otherwise. There are uncountably many subsets of $\mathbb N$ but only countably many Turing machines, so not every decision problem is decidable.

  We call $P$ recursive (or decidable) if some Turing machine decides it. We call $P$ listable (or recursively enumerable) if some machine prints elements over time whose set of outputs is exactly $P$; repetitions are allowed, and the machine may print nothing when $P$ is empty.

Proposition 1.1.   Recursive implies listable.

Proof. Run a decider for $P$ on $0,1,2,\ldots$ and print precisely those inputs on which it returns $1$. Q.E.D.

  Fix a computable pairing function $\langle-,-\rangle\colon\mathbb N^2\to\mathbb N$. The halting problem asks whether a machine can decide, from the code $\langle e,a\rangle$, whether $T_e(a)$ halts. Turing showed that it cannot.

Theorem 1.2 ([7]).   The halting problem is undecidable.

Proof. Suppose a halting decider $H$ exists. Construct a machine $G$ which, on input $e$, loops forever if $H(\langle e,e\rangle)=1$ and halts otherwise. If $g$ is the code of $G$, then $G(g)$ halts if and only if it does not halt, a contradiction. Q.E.D.

Corollary 1.3.   There exists a listable set $K\subseteq\mathbb N$ which is not recursive.

Proof. Set

\[K=\{\langle e,a\rangle:T_e(a)\text{ halts}\}.\]

This set is not recursive by Theorem 1.2. It is listable by dovetailing: at stage $N$, simulate the first $N$ machines on the first $N$ inputs for $N$ steps and print every pair observed to halt. Q.E.D.

2. Hilbert's 10th problem

  Hilbert's 10th problem asks whether an algorithm can determine if a polynomial with integer coefficients has an integer solution. Since polynomials in finitely many variables admit an effective encoding, this is the decision problem

\[P=\{\ulcorner F\urcorner:F\in\mathbb Z[X_1,\ldots,X_n]\text{ for some }n,\quad \exists a\in\mathbb Z^n,\ F(a)=0\};\]

we are interested in whether $ P $ is recursive.

  We say a set $ S \subseteq \mathbb{Z}^n $ is diophantine if there exists a polynomial

\[F \in \mathbb{Z}[X_1, \dots, X_n, Y_1, \dots, Y_m],\]

where $ S $ is the set of points $ a \in \mathbb{Z}^n $ such that there exists a $ b \in \mathbb{Z}^m $ with $ F(a, b) = 0 $. If we let $ \mathcal{V}(F) \subseteq \mathbb{Z}^{n+m} $ denote the zero locus of $ F $, this is the same as saying

\[S=\{a\in\mathbb Z^n:\exists b\in\mathbb Z^m,\ (a,b)\in\mathcal V(F)\}.\]

The following result about diophantine sets was shown by Y. Matiyasevich, [4], using the work of M. Davis, H. Putnam, and J. Robinson, [2].

Theorem 2.1.   Let $S\subseteq\mathbb Z^n$. Under any fixed effective encoding of integer tuples, $S$ is listable if and only if it is diophantine.

Proof. In [2], it is shown that every listable set is exponential diophantine, i.e., the zero set of a function created from integers and variables using addition, multiplication, and exponentiation. It is then shown in [4] that the exponential relation $ y = C^x $ is, in fact, diophantine; this is done using sequences of integer solutions of the Pell equation

\[X_1^2-nX_2^2=1,\]

where $n$ is not a square. We will not reproduce this difficult part of the argument; see [3] for an exposition. Q.E.D.

Corollary 2.2.   Hilbert's 10th problem is undecidable.

Proof. Transport the set $K$ from Corollary 1.3 to a subset $L\subseteq\mathbb Z$ using a computable bijection $\mathbb N\cong\mathbb Z$. Then $L$ is listable but not recursive. By Theorem 2.1 there is a polynomial $F\in\mathbb Z[X_1,Y_1,\ldots,Y_m]$ such that

\[L = \{ a \in \mathbb{Z} \mid \exists b \in \mathbb{Z}^m \text{ s.t. } F(a, b) = 0 \}.\]

If Hilbert's tenth problem had a positive answer, then for each $a\in\mathbb Z$ we could decide whether $F(a,Y)=0$ has an integer solution. This would decide $K$ (after a computable identification of $\mathbb N$ with $\mathbb Z$), a contradiction. Q.E.D.

3. Hilbert's 10th problem for arbitrary rings

  A natural question is whether the analogous problem is decidable over rings other than $\mathbb Z$. Such a question presupposes an effective encoding of coefficients and arithmetic in the ring. With that understood, it is important to distinguish three statuses: decidable, undecidable, and open. For example, the problem is decidable over finite fields by finite search, over effectively presented algebraically closed fields by elimination theory, and over effectively presented real closed fields by quantifier elimination. It is undecidable over $\mathbb Z$, while the case of $\mathbb Q$ remains open.

  The status for rings of integers changed after the 2003 survey [6]. If $K$ is any number field and $\mathcal O_K$ its ring of integers, Alpöge, Bhargava, Ho, and Shnidman proved that Hilbert's tenth problem over $\mathcal O_K$ is undecidable [8]. Their theorem subsumes the earlier conditional and special-case results. Questions over fields and over more general subrings remain substantially subtler; [1] surveys local-global methods and the rational case.

4. Mazur's conjectures

  In [5], B. Mazur made a series of conjectures about the closure of $V(\mathbb Q)$ inside the real manifold $V(\mathbb R)$. Write $\overline{V(\mathbb Q)}$ for this Euclidean closure. Mazur's first conjecture said that, for smooth $V$ with $V(\mathbb Q)$ Zariski dense, this closure is a finite union of connected components of $V(\mathbb R)$; this was later disproved. A weaker conjecture is:

Mazur's conjecture.   $\overline{V(\mathbb{Q})} $ has at most a finite number of components.

  Let $X$ be an algebraic set over $\mathbb Q$. A subset $S\subseteq X(\mathbb Q)$ is diophantine over $\mathbb Q$ if there is a regular morphism $f\colon Y\to X$ such that $S=f(Y(\mathbb Q))$.

Theorem 4.1.   If $\overline{Y(\mathbb Q)}\subseteq Y(\mathbb R)$ has finitely many connected components, then the closure of $S$ in $X(\mathbb R)$ has finitely many connected components.

Proof. Suppose $\overline{Y(\mathbb Q)}$ has $n$ connected components. The continuous image of each component is connected, and its closure remains connected. Moreover,

\[\overline{S}=\overline{f(Y(\mathbb Q))} =\overline{f(\overline{Y(\mathbb Q)})}.\]

Thus $\overline S$ is a union of at most $n$ connected closed sets. Q.E.D.

Corollary 4.2.   If $\mathbb Z\subseteq\mathbb A^1(\mathbb Q)$ is diophantine over $\mathbb Q$, then Mazur's finite-component conjecture cannot hold for every variety used to parametrize diophantine sets.

Proof. The closure of $\mathbb Z$ in $\mathbb R$ is $\mathbb Z$ itself, which has infinitely many connected components. Apply Theorem 4.1 to a morphism whose rational image is $\mathbb Z$. Q.E.D.

5. References

  1. S. Anscombe, V. Karemaker, Z. Kisakürek, V. Mehmeti, M. Pagano, and L. Paladino, A survey of local-global methods for Hilbert's tenth problem (2023), arXiv:2309.14987. Link
  2. Martin Davis, Hilary Putnam, and Julia Robinson, The decision problem for exponential diophantine equations, Ann. of Math. (2) 74 (1961), 425–436.
  3. J.P. Jones and Y.V. Matiyasevich, Proof of recursive unsolvability of Hilbert’s tenth problem, Amer. Math. Monthly 98 (1991), no. 8, 689–709.
  4. Yuri Matiyasevich, The diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279–282.
  5. Barry Mazur, The topology of rational points, Experiment. Math. 1 (1992), no. 1, 35–45.
  6. Bjorn Poonen, Hilbert's 10th problem over rings of number-theoretic interest, Arizona Winter School (2003). Link
  7. Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. (2) 42 (1937), 230–265.
  8. L. Alpöge, M. Bhargava, W. Ho, and A. Shnidman, Rank stability in quadratic extensions and Hilbert's tenth problem for the ring of integers of a number field, Invent. Math. 243 (2026), 1129–1139. Link