[Haskell] Generator Function for Prime Numbers

[Gen Zhang]

On Tue, 13 Mar 2007 10:15:53 +0100
Thorkil Naur <naur at post11.tele.dk> wrote:

> Hello,
> 
> On Tuesday 13 March 2007 00:40, Jacques Carette wrote:
> > And yet Taral would be wrong and Dave Feustel correct:
> > http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
> > 
> 
> I wouldn't say that a polynomium applies as "using only addition and 
> subtraction".
> 
> > There is a polynomial (of degree 25) in 26 variables which
> > generates only primes whenever it is positive.  Surprising, yes it
> > is.  Note that this polynomial is actually rarely positive!
> > 
> 
> Yes, and as noted in the Prime-GeneratingPolynomial reference, it is
> really a set of diophantine equations (equations where only
> integer/natural/rational solutions qualify) in disguise. In fact, if
> I remember correctly, one of the variables that you have to stick
> into the polynomium is one less (or some such) than the prime that
> you get out. So as a prime generating device, it is rather useless.
> 
> The idea of defining sets of numbers by diophantine equations was
> used in 1970, to prove one of the 10th of Hilberts famous 23 problems
> from 1900 impossible. See
> 
>   http://en.wikipedia.org/wiki/Matiyasevich's_theorem

Incidentally, the proof is of a constructive nature, in that it shows
how to encode any computable function as Diophantine equations. In
particular, the output of the functions are encoded as solutions to the
equations. Thus any computable has concrete corresponding equations.
However, as has been noted, this does not actually imply the resulting
equations are useful for computation.

Gen
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell/attachments/20070313/f6a2d932/signature-0001.bin