A Model for Recursively Self Improving Programs
Matt B. Mahoney · 2010
We formally define recursively self improving programs and show that such programs exist, but that their algorithmic complexity cannot grow faster than O(log n) given fixed goals. Background Vinge [1] predicted that if humans could produce artificial intelligence (AI) systems with greater than human intelligence, then so could those systems, only faster. The resulting positive feedback cycle would result in an intelligence explosion or singularity. The Singularity Institute for Artificial Intelligence [2] is investigating the threat of runaway AI, but the problem is poorly understood; lacking any precedent. Of central importance is an understanding of the limits of recursive self improvement (RSI). If RSI is possible, then it is critical that the initial goals of the first iteration of agents (seed AI) are friendly to humans and that the goals not drift through successive iterations, assuming we cannot control the goals of subsequent generations appearing in rapid succession. This is an extremely difficult problem in itself, because friendliness is not well defined, although attempts have been made [3]. On the other hand, if RSI is not possible, then we are possibly left with an evolutionary process in which self modifying and reproducing agents compete for computing resources with the most successful of