1
$\begingroup$

The halting problem (https://en.wikipedia.org/wiki/Halting_problem) has been shown to be equivalent to the problem of determining whether a given Diophantine equation has solutions.

I need to see a reference about this statement

$\endgroup$
4
  • $\begingroup$ There are plenty references here: en.wikipedia.org/wiki/Diophantine_set $\endgroup$ – Wojowu Dec 16 '19 at 11:05
  • $\begingroup$ @Wojowu: I need the one specified for the halting problem. $\endgroup$ – Safwane Dec 16 '19 at 11:07
  • 2
    $\begingroup$ @Germany, there will not be one particular equation. Each Turing machine can be translated into a Diophantine equation, and then the existence of a solution to that equation is equivalent to that particular Turing machine halting. $\endgroup$ – Mees de Vries Dec 16 '19 at 11:14
  • $\begingroup$ The one-way proof is easy: for a given equation, write an algorithm that tries all possibilities exhaustively and stops on a solution. If you had a Halting Test, you could use it to check the existence of a solution. $\endgroup$ – Yves Daoust Dec 16 '19 at 13:05
3
$\begingroup$

Deciding whether a given Diophantine equation has a solution is Hilbert's tenth problem.

What you're looking for is Matiyasevich's theorem

A good reference is this survey from Jochen Koenigsmann.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.