From: Iain Strachan (iain.strachan.asa@ntlworld.com)
Date: Sat Aug 09 2003 - 07:27:19 EDT
I think it might be useful to think a bit more specifically about this
algorithm, which I would claim to be an example of irreducible complexity.
For reference, here it is again:
Function primes(n As Long) As Variant
nout = Application.Caller.Rows.Count
ReDim v(1 To nout)
ReDim p(1 To n) As Integer
For i = 1 To n
p(i) = 1
Next i
p(1) = 0
nfound = 0
For i = 2 To n
If (p(i) > 0) Then
nfound = nfound + 1
v(nfound) = i
If nfound = nout Then
Exit For
End If
For j = i * i To n Step i
p(j) = 0
Next j
End If
Next i
primes = Application.Transpose(v)
End Function
David wrote (in part):
> >Interesting question; can anyone imagine a way that this algorithm might
have build up gradualistically as a series of simpler algorithms, which also
perform "useful" functions, such as a mathematical series, each one more
useful than the last?<
>
> Obviously each line of the algorithm performs some sort of useful
function.
Yes, but their usefulness is dependent on other lines.
For example the line:
For j = i * i To n Step i
.. on its own performs no useful function whatsoever. It simply states that
the index j starts from the square of i and takes values at intervals of i
that are less than n. By itself, it does not even make a legal bit of
program. In an environment that "mixed and matched" lines of code, this
would in most cases not produce a legal program as its dependent on there
being a "Next j" further on. Furthermore, something else that is dependent
on j has to be inbetween the "For" and the "next"...
p(j) = 0
Next j
... and once we've got this, we are also dependent on p(j) being a
meaningful expression; that an array called p has been declared elsewhere,
and that it is the right size not to cause the program to crash with an
array bounds violation. This is from the statement:
ReDim p(1 To n) As Integer
that appears earlier.
Already we have a pretty intricate nest of interdependencies & we haven't
even started yet. Even given the complete For loop that sets the i_th
elements from i squared to zero, that in itself is not useful unless two
conditions are specified:
(1) That the array positions aren't zero anyway (an earlier 3 line loop does
this)
(2) Yet another bit of the program actually _does something_ with this array
that has had the ith elements set to zero. This is (in this case) the
earlier loop:
For i = 2 To n
If (p(i) > 0) Then
nfound = nfound + 1
v(nfound) = i
... in which the other loop is nested. This is the bit that finds the
primes and sets the step interval and start point for the inner loop.
Now; I'm not saying that each individual line couldn't be used in a quite
different program performing some kind of function. But I hope this shows
that even the most basic elements depend pretty inextricably on other
elements.
>
> If the pieces were present in an environment that could mix and match them
and then take the "useful" initial combinations as the starting point for
further variation, it seems likely that a relatively complex "useful"
function would be produced.
OK, here's another question. I've shown that the final program is pretty
well interconnected. Perhaps it would be interesting to consider what the
precursor program was, that was a very small "mutation" away from the final
one, but didn't compute the primes. (Incidentally, there are lots of
possible precursors that compute the primes and then don't do anything with
them, for example if the line
v(nfound) = i
is omitted, then the sieve is left with ones in the prime position and then
thrown away at the end, with no software interface to it; so the function is
completely useless. It counts the number of primes less than the input
value n, but again, the function does not return this value to the
spreadsheet.
I do not believe that an evolutionary environment would produce such a
program unless the programmer of the algorithm built in a list of
predecessor functions, each of which was a small step from the last one, and
each of which was defined to have slightly greater "fitness" than the last
one. Without doubt, that would be "Intelligent design", and would probably
require a much greater degree of intelligence than it took to write the
algorithm in the first place :-) [I guess it took me about 10 minutes to
write it].
Iain.
This archive was generated by hypermail 2.1.4 : Sat Aug 09 2003 - 07:30:06 EDT