|
Author
|
Topic: Wolfram on generating primes -- puzzling
|
Paul A. Nelson
Member
Member # 26
|
posted 28. May 2002 09:44
My ongoing reading of Stephen Wolfram's A New Kind of Science has raised some questions on which I invite commentary.
One of Wolfram's most provocative arguments holds that cellular automata (CAs) can generate patterns previously ascribed solely to intelligent causes - for instance, the computation of prime number sequences. As is well-known from the SETI and ID literature, the detection of a (sufficiently long) sequence of primes has widely been thought to be a reliable indicator of an intelligent cause. Wolfram claims that his discoveries with CAs refute this.
But the evidence Wolfram offers in support of this claim seems to undermine his own position. Given, however, that (a) Wolfram spent 10 years writing A New Kind of Science, and that (b) I don't know much about CAs, I want to ask other Brainstorms readers if I've missed something important.
Wolfram writes:
quote:
In discussions of extraterrestrial intelligence it is often claimed that mathematical constructs - such as the sequence of primes - somehow serve as universal signs of intelligence. But from the results of this book it is clear that this is not correct. For while in the past it might have seemed that the only way to generate primes was by using intelligence, we now know that the rather straightforward computations required can actually be carried out by a vast range of different systems - with no apparent need for intelligence. (p. 837)
On page 639-640, Wolfram gives a CA that computes the primes. He writes:
quote:
...cellular automata can in fact perform what are in effect arbitrarily sophisticated computations. And as one example of a somewhat more sophisticated computation, the picture on the next page shows a cellular automaton that computers the successive prime numbers: 2, 3, 5, 7, 11, 13, 17, etc. (p. 639)
But the prime-computing CA in question is far from simple. As Wolfram continues:
quote:
The rule for this cellular automaton is somewhat complicated - it involves a total of sixteen colors possible for each cell - but the example demonstrates the point that in principle a cellular automaton can compute the primes. (p. 640)
That a CA can compute primes is not the bold and novel claim that Wolfram later makes, however. I don't think anyone doubted that intelligently-constructed computational systems (such as CAs) could generate prime number sequences.
The novel claim is that this computation occurs "with no apparent need for intelligence" (p. 837).
Yet this is precisely what Wolfram does not demonstrate. Here are the rules for the prime-computing CA:
quote:
{{13, 3, 13} --> 12, {6, _, 4} --> 15, {10, _, 3 | 11} --> 15, {13, 7, _,} --> 8, {13, 8, 7} --> 13, {15, 8, _} 1, {8, _, _} --> 7, {15, 1, _} --> 2, {_, 1 _} --> 1, {1, _, _}--> 8, {2 | 4 | 5, _, _} 13, {15, 2, _} 4, {_, 4, 8} --> 4, {_, 4, _} 5, {_, 5, _} 3, {15, 3, _} --> 12, {_, x: (2 | 3 | 8), _} --> {_, x: (11 | 12), _} --> x - 1 {11, _, _} --> 13, {13, _, 1 | 2 | 3 | 5 | 6 | 10 | 11} --> 15, {13, 0, 8} --> 15, {14, _, 6 | 10} --> 15, {10, 0 | 9 | 13, 6 | 10} --> 15, {6, _, 6} --> 0, {_, _, 10} --> 9 {6 | 10, 15, 9} --> 14, {_, 6 | 10, 9 | 14 | 15} --> 10, {_, 6 | 10, _} --> 6, {6 | 10, 15, _} --> 13, {13 | 14, _, 9 | 15) --> 14, {13 | 14, _, _} --> 13, {_, _, 15} --> 15 {_, _, 9 | 14} --> 9, {_, _, _} --> 0} and the initial conditions consist of {10, 0, 4, 8} surrounded by 0's. (p. 1109)
Now, these rules were not, as nearly as I can tell from the book, themselves generated by a randomly-selected CA, or by any CA, for that matter. I'm guessing that Wolfram himself carefully assembled this CA, using what he calls (p. 640) "the standard sieve of Eratosthenes method."
Where then is the demonstration that the computation of primes can occur "with no apparent need for intelligence"?
[ 28 May 2002, 10:50: Message edited by: Paul A. Nelson ]
IP: Logged
|
|
complex
Member
Member # 259
|
posted 28. May 2002 11:12
Paul,
I think that CA's are overplayed, not in their capability to do various and fascinating calculatins and mappings, but in that it is implied they differ from a Turing machine. Obviously they are a Turing machine since all the CA calculations were able to done on a regular computer that the author had access to. It can also be shown theoretically that any CA can be mapped to a Turing machine.
If that is the case, then all of the classic CS theorems and observations apply about the generation of information and algorithms.
The question that you are really asking is "Can there be a generalized CA algorithm that will generate all other algorithms of interest? (such as a prime generating algoritm)." And the answer is no since there is non such for Turing machines -- a more general class.
You still need a mind to look "outside of the system" and figure it out.
IP: Logged
|
|
LePlage
Member
Member # 221
|
posted 28. May 2002 14:18
I believe that Dembski´s critique of smuggling in specified complexity would apply here. The automata certainly need to be carefully set up by an intelligent agent nonetheless.
However, as far as I understand, Wolframs idea is that the universe itself is an automata. He could postulate the cosmic automata as a brute fact. The cosmic automata could then generate specified complexity in form of further automatas, that themselves could generate yet another bunch of automatas.
Perhaps he would consider intelligence itself to be a automata in action?
IP: Logged
|
|
Paul A. Nelson
Member
Member # 26
|
posted 28. May 2002 18:14
LePlage wrote:
Perhaps he would consider intelligence itself to be a automata in action?
Perhaps -- but then why bother to show that CAs can generate patterns previously ascribed to intelligent causes only (e.g., the sequence of primes)? Wolfram allows that one can detect "intelligence" as an ontologically distinct mode of causation. He argues, however, that the sequence of primes is a poor diagnostic of intelligent causation, insofar as he has shown (or so he argues) that CAs can also generate such sequences.
The whole point of Wolfram's argument is that a pattern previously thought to require intelligent causation (the primes) has now been shown to be unintelligently generated by a CA. This argument becomes nonsense if "intelligence" is au fond a cellular automata itself. One would have cashed in the very distinction at issue.
[ 28 May 2002, 18:18: Message edited by: Paul A. Nelson ]
IP: Logged
|
|
James A. Barham
Member
Member # 50
|
posted 28. May 2002 19:34
Paul:
I haven't succeeded in getting hold of a copy of Wolfram's book yet, but I have read several reviews and have some sense of what is at stake.
The only reason I would like to jump in is to mention that there is a very deep metaphysical problem here that I am seeing replicated elsewhere that is very troubling to me and which is going to make discussion of this issue very difficult, I fear.
Over on FIS (Foundations of Information Science) I have practically made myself persona non grata by insisting that pan-informationism is a form of idealism. I hold this view because I think that "information" in the proper sense of the term is structure that is meaningful for a cognitive agent. No semantic component, no information, just structure tout court.
Therefore, if we posit information as an elementary principle on a par with matter and energy we have effectively smuggled intelligent agency into the foundations of the universe itself! Now, this may be perfectly acceptable for ID folks to do, but how do people who would cheerfully describe themselves as naturalists (like all the FIS folks and Wolfram) think they can get away with this? I don't know the answer, I only know that the tendency is by now deeply rooted in the scientific community and that they are not easily going to acknowledge its fundamental incoherence.
IP: Logged
|
|
LePlage
Member
Member # 221
|
posted 29. May 2002 04:36
Hi Paul.
Ok. Maybe I unfairly "read in" reductionism into Wolframs proposal. I have not read the book, I´m merely familar with it from reviews. I presumed that he also wanted to revolutionize cognitive science with the automatas.
That, as far as I understand, implies a reduction of intelligence from being a distinct ontological cause to become a expression of the natural operation of CA:s (If Wolfram indeed envisions a revolution in cognitive science based on CA:s)
But if he means that CA:s can produce specified complex patterns, does not that imply that a CA can specify another CA? Perhaps even in a regression all the way up to the cosmological level?
To my understanding Wolframs main thrust is that CA:s underly most natural processes, but maybe
I have not accurately understood his basic ideas.
IP: Logged
|
|
Paul A. Nelson
Member
Member # 26
|
posted 04. June 2002 13:08
To LePlage and others:
Let's travel (in our minds) to Wolfram's office in Champaign, Illinois. Pour ourselves a cup of coffee -- and one for Wolfram, too, of course.
Then we ask Stephen about the origin of this CA:
quote:
{{13, 3, 13} --> 12, {6, _, 4} --> 15, {10, _, 3 | 11} --> 15, {13, 7, _,} --> 8, {13, 8, 7} --> 13, {15, 8, _} 1, {8, _, _} --> 7, {15, 1, _} --> 2, {_, 1 _} --> 1, {1, _, _}--> 8, {2 | 4 | 5, _, _} 13, {15, 2, _} 4, {_, 4, 8} --> 4, {_, 4, _} 5, {_, 5, _} 3, {15, 3, _} --> 12, {_, x: (2 | 3 | 8), _} --> {_, x: (11 | 12), _} --> x - 1 {11, _, _} --> 13, {13, _, 1 | 2 | 3 | 5 | 6 | 10 | 11} --> 15, {13, 0, 8} --> 15, {14, _, 6 | 10} --> 15, {10, 0 | 9 | 13, 6 | 10} --> 15, {6, _, 6} --> 0, {_, _, 10} --> 9 {6 | 10, 15, 9} --> 14, {_, 6 | 10, 9 | 14 | 15} --> 10, {_, 6 | 10, _} --> 6, {6 | 10, 15, _} --> 13, {13 | 14, _, 9 | 15) --> 14, {13 | 14, _, _} --> 13, {_, _, 15} --> 15 {_, _, 9 | 14} --> 9, {_, _, _} --> 0} and the initial conditions consist of {10, 0, 4, 8} surrounded by 0's. (p. 1109)
Simple question. Did Wolfram himself construct this, and test it (by simulation) to make sure it worked -- i.e., that the CA actually generated the sequence of primes?
If the answer is Yes, then I'm not interested in any claims that CAs can mimic the action of intelligence. We have Stephen Wolfram, in the flesh. He constructed the prime-generating CA above.
We do not have a CA for the biological object "Stephen Wolfram." Nor should any be expected, within the lifetime of the physical universe.
Sorry if this seems crude or unsympathetic to Wolfram's project -- or more precisely, his claims on behalf of his project -- but after hundreds of pages of hyperbole in A New Kind of Science, some plain talk is in order.
IP: Logged
|
|
complex
Member
Member # 259
|
posted 04. June 2002 16:29
Paul,
We can similarly ask that of finite automata or a Turing machines. Can a Turing machine (which has infinite memory) be clever enough to even determine if a particular algorithm produces only primes? The answer is no. This can be demonstrated by a similar proof to what is pointed out by
http://www.math.uaa.alaska.edu/~afkjm/cs450/handouts/tmintro.pdf.
If a CA (or collection of them) cannot even tell if a particular collection of CA's is producing primes, how are they expected to come up with the algorithm?
IP: Logged
|
|
Iain Strachan
Member
Member # 96
|
posted 12. June 2002 14:51
Maybe I'm being thick or something, but I can't really see the difference between a Fortran subroutine generating primes "unintelligently" via the sieve or eratosthenes and a cellular automaton generating primes "unintelligently".
Both have an amount of data to specify the "program" (I wrote a Fortran subroutine to generate and print out a list of primes that required less space than the CA specification), and also a machine of some sort to actualize the specification. I don't see how a specification as complex as the CA version of the prime generator could arise at random any more than the Fortran program; if either are to arise without "intelligent input", then presumably they have to arise through an evolutionary process. But as I understand it, Wolfram is challenging evolution with his ideas on cellular automata.
Somewhat more interesting, I think is the technique of "template metaprogramming" in C++, described Here
Templates were a simple feature added to the C++ programming language to make syntactical substitution easier to use. What turned out quite by accident was that the language feature that was put in turned the Compiler into a universal turing machine, capable of making arbitrarily complex calculations during the compilation of the program (as opposed to at run time). An example program was written be Erwin Unruh, of a C++ template program that caused the compiler to generate a list of primes as error messages. The program itself was incorrect, and produced the following error messages:
erwin.cpp: Cannot convert enum to 'D<2>'
erwin.cpp: Cannot convert enum to 'D<3>'
erwin.cpp: Cannot convert enum to 'D<5>'
erwin.cpp: Cannot convert enum to 'D<7>'
erwin.cpp: Cannot convert enum to 'D<11>'
erwin.cpp: Cannot convert enum to 'D<13>'
etc.
I do not know if Unruh's program produced the list of primes by accident or design, but the ability of making the compiler into a Turing machine was certainly not intended by the designers of that particular language feature, and it is therefore an interesting example of apparent design that came about by accident.
Iain.
IP: Logged
|
|
|
Printer-friendly view of this topic