0
$\begingroup$

There is a diophantine equation in some number (I think the minimum is now 9) of variables, that can be used to represent

  1. All other diophantine equations (could be wrong on this)
  2. Any particular set of numbers -- such as the primes

So to ask some questions around the consequence of this fact with another fact : the non-existence of a universal procedure for solving any diophantine.

Since no such procedure can exist, am I correct in concluding from these two facts that, at least as represented by a diophantine set, the primes can not be enumerated?

Or is the caveat that, maybe a particular procedure for solving a class or case of diophantine equations, of which the universal one mentioned above could be a member, exists and thus the primes could be enumerated by solving the universal one using such a yet-to-be-discovered specific method.

Also, one final question: Am I right in my feeling that construction of this universal diophantine is not really "adding any new insight" to the area of primes, but simply finding a way to represent some kind of computer or turing machine as a diophantine and program it.

If anyone would be so kind as to offer a simple explanation of the specific method of "programming" this diophantine or the constraints that actually give rise to this "universal" diophantine being able to encode the set of the primes, I would be grateful.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Matiyasevich "Hilbert's 10th problem". See also en.wikipedia.org/wiki/Hilbert's_tenth_problem . The question is answered by Wikipedia. Voted to close. $\endgroup$
    – user6976
    Commented Nov 20, 2011 at 15:13

1 Answer 1

Reset to default
5
$\begingroup$

Any Diophantine set can be enumerated, in the sense that there is a procedure that will list any given member of the set after a finite amount of time. In fact, Diophantine sets are precisely those which can be so listed: the recursively enumerable sets.

For the primes and many other Diophantine sets, more is true: the elements can be listed in order, since there are procedures for determining not only existence but also non-existence. These sets are called recursive or decidable.

You are right that finding a Diophantine representation for primes does not add much if anything to the study of primes. It serves, rather, to increase our understanding of Diophantine equations.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks for the answer. so, where would I find the procedure for running over that recursively enumerable set described by that universal equation I mentioned. I would be interested to see how far my computer got? $\endgroup$
    – Cris Stringfellow
    Commented Nov 20, 2011 at 15:24
  • $\begingroup$ Loop max from 0 to infinity. For each value, loop every variable in the equation from -max to max. If the equation yields an acceptable value (positive in the case of the Jones-Sato-Wada-Wiens equation), output it. Optionally, output only if it has not been output before. $\endgroup$
    – Charles
    Commented Nov 20, 2011 at 21:02
  • $\begingroup$ Okay and here I was thinking there might exist an efficient procedure. Thank you $\endgroup$
    – Cris Stringfellow
    Commented Nov 21, 2011 at 5:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .