As shown in Jones (1982), it is undecidable whether the equation below has a solution over the positive integers for given positive integers x and v:
![$$\begin{alignat*}{2} & &&(elg^2 + α - (b - xy)q^2)^2\\ &+ &&(q - b^{5^{60}})^2\\ &+ &&(λ + q^4 - 1 - λb^5)^2\\ &+ &&(θ + 2z - b^5)^2\\ &+ &&(l - u - tθ)^2\\ &+ &&(e - y - mθ)^2\\ &+ &&(n - q^{16})^2\\ &+ &&(\\ & && ~~~r\\ & &&~~~- [g + eq^3 + lq^5 + (2(e - zλ)(1 + xb^5 + g)^4 + λb^5 + λb^5q^4)q^4][n^2 - n]\\ & && ~~~- [q^3 - bl + l + θλq^3 + (b^5 - 2)q^5][n^2 - 1]\\ & &&)^2\\ &+ &&(p - 2ws^2r^2n^2)^2\\ &+ &&(p^2k^2 - k^2 + 1 - τ^2)^2\\ &+ &&(4(c - ksn^2)^2 + η - k^2)^2\\ &+ &&(k - r - 1 - hp + h)^2\\ &+ &&(a - (wn^2 + 1)rsn^2)^2\\ &+ &&(c - 2r - 1 - φ)^2\\ &+ &&(d - bw - ca + 2c - 4aγ + 5γ)^2\\ &+ &&(d^2 - (a^2 - 1)c^2 - 1)^2\\ &+ &&(f^2 - (a^2 - 1)i^2c^4 - 1)^2\\ &+ &&((d + of)^2 - ((a + f^2(d^2 - a))^2 - 1)(2r + 1 + jc)^2 - 1)^2\\ &+ &&(v - ((zuy)^2 + u)^2 - y)^2\\ &= &&~0 \end{alignat*}$$](https://blogger.googleusercontent.com/img/a/AVvXsEh01f7zLKbw2S_Kmxfk2uS06PUlcuesNlcQEXVeMuPxcU7Wlm3hlKIjaTNXqGHHcnYYy_2z6zOOBPh36Jbo-mWXkaj72yFPRod4G57e0YKiQgoidZ4gBudvPFPNCsIG3S1Eii8Pvl4KvuxfH8rdBa0OBH485LizklCch17PKlS_z7yTUEClVnvV0i1W=w470-h484)
That equation corresponds to the 19-equation system from Jones' Theorem 3 (1982). Jones' system of equations
L₁ = R₁, L₂ = R₂, …, L₁₈ = R₁₈, Lᵥ = Rᵥ
is equivalent to:
(L₁ – R₁)² + (L₂ – R₂)² + … + (L₁₈ – R₁₈)² + (Lᵥ – Rᵥ)² = 0
The single equation above has a solution just when x is a member of the vth semidecidable set, with v representing the index of each semidecidable set listed in an order determined by the equation. Some semidecidable sets are not decidable. Therefore, an algorithm capable of deciding the solvability of the equation for any given x and v would be able to decide membership in undecidable sets.
Reference: Jones, James P. (1982). Universal Diophantine Equation. The Journal of Symbolic Logic, 47(3), 549-571. https://doi.org/10.2307/2273588.
No comments:
Post a Comment