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