Mike Stay <metaweta@gmail.com> wrote:
Simon Plouffe <simon.plouffe@gmail.com> wrote:
Is there simpler method to generate any number of primes ?
"Simplicity" depends entirely on the programming language. In Mathematica, the simplest way is Prime[n]. One might think that there are "natural" universal Turing machines, in the sense that unnatural ones can simulate natural ones with short interpreters, but not vice-versa. Somewhat surprisingly, that turns out to be false.
Cite? Also, from context I think Simon really means a faster way, not a simpler way. There's often a trade-off between the speed and the complexity of an algorithm. And how difficult it is to write a program often depends on how well the programming language hides the complexity. Just because it's easy to write Factor(1+2^3^4^5^6^7^8^9) doesn't mean you'll get an answer before the heat death of the universe. Also, physically building Turing-equivalent machines requires physical components, such as transistors, gears, or electromechanical relays. Some tasks inherently require either more such components, or that the fixed number of such components change state more times, than other tasks do.