theoremnovelinferred_depunresolved_ref
Hilbert's tenth problem over Q is undecidable
Solvability of polynomials over Q is undecidable
the headline result
Theorem·
thm:main·§1 IntroductionStatement (paper)
There is no algorithm which, given a polynomial
, with part of the input, decides whether
has a zero in .
In plain English
No algorithm can take a polynomial , with part of the input, and decide whether has a zero in .
Why it's here
This is the paper's main result. It is obtained by reducing integer solvability (Hilbert's tenth problem over ) to rational solvability. The two dependencies supply the reduction: the recursive theory has the standard integers as a model, and if all finite rational tests for are solvable then has an integer zero. A rational decision procedure would therefore decide integer solvability, which is impossible.
Classified novel:
Undecidability of Hilbert's tenth problem over Q has been a long-standing open problem; Matiyasevich's theorem (1970) covers only Z, and no prior reduction from integer to rational solvability was known. The paper's reduction through finite rational tests and the recursive theory T is its central new contribution.