Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • 1
    $\begingroup$ Of course I understand what it means to "solve a diophantine equation" - you find numbers that satisfy the equation. I don't see why Matiyasevich's indecidability theorem or recursively enumerable sets need to be brought into the discussion. But I think that last paragraph could explain it... $\endgroup$ Commented May 17, 2012 at 17:15
  • 1
    $\begingroup$ Alright this new edit explains it - that also explains why the Halting problem is not in NP, since the steps it takes to halt could be arbitrarily large. Thanks! $\endgroup$ Commented May 17, 2012 at 17:17
  • $\begingroup$ My suggested edit was to remove the first two paragraphs. The first two paragraphs explain why Hilbert's 10th problem is undecidable, which is completely tangential to the question; they just detract from the rest of the answer (which is a great answer otherwise!). $\endgroup$ Commented May 17, 2012 at 21:59
  • $\begingroup$ @BlueRaja-DannyPflughoeft if the first paragraph insulted you, then I can remove it (although you did ask "what is wrong with my understanding?"). The second paragraph is necessary to set the problem up more formally since you don't in your question. $\endgroup$ Commented May 17, 2012 at 22:02
  • 3
    $\begingroup$ @BlueRaja-DannyPflughoeft It is best if questions and answers are self-contained. My second paragraph sets up the problem and explains what it means for this problem to be undecidable. My third paragraph gives the quick answer. My 4th and 5th paragraph expand on that in more detail. As far as I can tell, all paragraphs are necessary. $\endgroup$ Commented May 17, 2012 at 22:08