We recall the MRDP Theorem, the Universal Diophantine Equation of Jones, and the degree hierarchy of Diophantine equations over $\mathbb{N}$, as codified in the study of Hilbert's Tenth Problem.

Operational summary: each artifact below is a published degree-3 polynomial whose bounded satisfiability can be checked directly from its coefficient table.

• Degree 2. Certain structured quadratic forms are decidable via classical number-theoretic methods (Hasse–Minkowski, Lagrange). Degree-2 constraints lack the expressive power to encode arbitrary proof checking.
• Degree 4. Every recursively enumerable set is the solution set of a degree-4 Diophantine equation in 58 variables. Undecidability follows classically from MRDP.
• Degree 3. The open case, identified by Jones (1980), cf. “Secondary Literature” on this page.

The artifacts shown here are computable witnesses rather than classic existence claims. Their coefficients are published, their degrees can be directly examined, and their bounded satisfaction predicates are decidable by finite search. The constructions are strictly more informative: where tradition asserts that some polynomial encodes all recursively enumerable sets, the effective construction demonstrates this.

We start with simple resource parameters signifying the number of lines, the digit width, and the base:

A generator in $\mathsf{Python}$ emits one concrete cubic coefficient table $U_{k,w}$ and establishes bounded proof-check satisfiability:

Analogy. We imagine a polynomial as a command-line interface (without a monitor). We can define a query and feed it into its variables. The equation evaluates to 'zero' if the encoded statement is true, and to a nonzero value otherwise. The polynomial itself is fixed; only the input changes.

Realization proceeds in layers.

Given a weak arithmetic we define as Register Arithmetic or $\mathsf{RA}$, situating its comprehension (with extensional multiplication) between Robinson Arithmetic ($\mathsf{Q}$) and Peano Arithmetic $(\mathsf{PA})$:

(ii) Compilation. A primitive recursive map

takes sentence codes to finite systems of degree-3 Diophantine equations, such that

(iii) Constraining. Syntactic and inference checks compile to quadratic constraints (degree-2). Cubic terms arise only when a degree-1 selector variable activates a quadratic obligation. The resulting system is collapsed to a single cubic equation by mixed-radix aggregation, avoiding the sum-of-squares degree doubling that would otherwise raise degree to 6.

(iv) Metatheory. Each fixed bounded slice is decidable, yet no total correct uniform decider for the compiled family exists. By the Diagonal Lemma, such a decider would compose with the compiler to decide theoremhood: contradiction. If $\mathsf{RA}$ could internally certify such a decider, it would witness its own $\Sigma_1$-reflection, contradicting Gödel's Second Incompleteness Theorem, hence ad absurdum.