The Possible Irreducibility of Artificial Software Life - Bruce Edmonds
Clearly if one allows non-deterministic programs
in the definition of "systematically realisable reduction" above, any theoretical reduction is also a possible systematically realisable reduction. To see this, just imagine a program that picks an integer n with probability
. This could "find" the correct index of any statement (given enough time!).
Thus it is possible that a non-deterministic algorithm could produce (evolve) an systematically unreachable program (in the above sense) using a combination of chance and design. In such algorithms a very low probability corresponds to the absolute of unreachability for the deterministic algorithms discussed above. Thus certain programs may still be almost certainly unreachable even by such a non-deterministic algorithm (we will call this probabilistic unreachability). However, it is by far from certain that systematic reachability and probabilistic unreachability always coincide. Thus there may be occasions where the probabilistically reachable will be systematic unreachable (and vice versa). In this case we may evolve a program that we can't program.
It may be objected that once we have such a program (however achieved) we could then reverse-engineer it and discover how to program it. This is not the case, since if we had a reliable method for such de-compilation we could use the following method to get round the systematic unreachability of some programs, namely: "for each number, m, in turn (1, 2, 3, ...), find the corresponding program,
, decompile it and find out how to program it". This would contradict the proof above. Thus such a reverse-engineering strategy can not be systematised. We could still copy it (or large portions) wholesale, but this is still not the same as systematically programming it.
Of course, in practice, it is ususal to use a pseudo-random source rather than what might be a true source of random numbers. In such cases any algorithm (for example a genetic programming algorithm) that used a source of pseudo-random numbers, would, in principle, be systematically realisable. However this does not alter the practicalities of the situation - it would still be very difficult to reduce such an algorithm to an understandable determinisitc system, even if this is possible. Also is presumes that one would have access to the generating process and initial seed.
Generated with CERN WebMaker