Math Conjectures

Hilbert’s Tenth Problem over Q\mathbb Q

OPENLandmarkOpen problemProposed 1970 · Standard version

Canonical statement

There is no Turing machine which, on every input polynomial f∈Z[x1,…,xn]f\in\mathbb Z[x_1,\ldots,x_n] (where nn is part of the input), halts and correctly decides whether there exists (q1,…,qn)∈Qn(q_1,\ldots,q_n)\in\mathbb Q^n with f(q1,…,qn)=0f(q_1,\ldots,q_n)=0.
View source LaTeX
There is no Turing machine which, on every input polynomial \(f\in\mathbb Z[x_1,\ldots,x_n]\) (where \(n\) is part of the input), halts and correctly decides whether there exists \((q_1,\ldots,q_n)\in\mathbb Q^n\) with \(f(q_1,\ldots,q_n)=0\).
NT-LOGIC-025:[Matiyasevich1970][Poonen2003H10Q][Koenigsmann2016ZDefinable][AIMDefinability2019]
Number theoryLogic and foundations

Notes

Hilbert's tenth problem asked for an algorithm to decide whether a polynomial equation with integer coefficients has a solution in integers. The present problem is its rational analogue: is there a Turing machine that, given f∈Z[x1,…,xn]f\in\mathbb Z[x_1,\ldots,x_n], decides whether ff vanishes somewhere on Qn\mathbb Q^n? Equivalently, is the existential first-order theory of Q\mathbb Q decidable? The question took its modern form in 1970, when Matiyasevich, completing work of Davis, Putnam and Robinson, proved that no such algorithm exists over Z\mathbb Z [Matiyasevich1970].

The natural route to a negative answer would be an existential (Diophantine) definition of Z\mathbb Z inside Q\mathbb Q, which would transfer the undecidability over Z\mathbb Z directly. Koenigsmann showed that Z\mathbb Z is definable in Q\mathbb Q by a purely universal formula [Koenigsmann2016ZDefinable], close in logical shape but on the wrong side of the quantifier divide, and Poonen proved undecidability for large subrings of Q\mathbb Q [Poonen2003H10Q]. These definability questions remain the focus of an active program [AIMDefinability2019].

The problem is open in both directions: no decision procedure is known for rational points, and no proof of undecidability either.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.