Re: specified complexity

From: Iain Strachan (iain.strachan.asa@ntlworld.com)
Date: Sat Aug 09 2003 - 07:27:19 EDT

  • Next message: Howard J. Van Till: "Re: specified complexity"

    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