I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem.

Can you either explain it to me or give me a credible source from which I can study it?

  • $\begingroup$ The program is if (the equation has a solution) then return 0 else <infinite loop>. $\endgroup$
    – Dmitry
    Commented Feb 5, 2023 at 20:12
  • 1
    $\begingroup$ @Dmitry, can I encourage you to write that in the answer box rather than a comment, so we can upvote it and the question can be treated as answered? The Stack Exchange format discourages answering in comments. I don't think you have to write anything more than that -- even a short answer is better than none. $\endgroup$
    – D.W.
    Commented Feb 5, 2023 at 21:30
  • $\begingroup$ worth noting this idea works to reduce lots of problems to the halting problem. (Anything of the form "is there a solution?" when the number of possible solutions is countably infinite) $\endgroup$ Commented Mar 6, 2023 at 19:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.