Re: [math-fun] a long series of primes
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.
On Sat, Feb 15, 2020 at 12:03 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
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?
I wish I could! I remember the result from maybe 15 years ago---I was a grad student in New Zealand at the time. I spent a few hours looking for the paper, but couldn't find it. The closest thing I could find was a disappointing comment by Marcus Hutter in _Universal Artificial Intelligence_ that defines "natural" machines as ones with short interpreters relative to some fixed machine. The paper I recall demonstrated that for any universal machine U there were always clusters of universal machines that mutually simulated each other with small programs but required an arbitrarily large prefix to simulate U and vice-versa. My vague reconstruction of the argument is that you can pick a very long, random string as the output of the machine V on each program up to some very long length, and then have some long prefix simulate U. The fact that it simulates U means V is universal, but for U to simulate V, it needs to encode all the results of the short programs of V in the compiler; and for V to simulate U, it needs that very long prefix. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
participants (2)
-
Keith F. Lynch -
Mike Stay