Re: [sl4] Is there a model for RSI?

From: Thomas McCabe (
Date: Tue Jun 24 2008 - 21:43:22 MDT

On Sun, Jun 22, 2008 at 9:23 PM, Peter de Blanc <> wrote:
> Mark Nuzzolilo wrote:
>> I'll take a swing at this.
>> Let's start with the assumption that a machine cannot output a machine of
>> greater algorithmic complexity.
> This assumption turns out to be incorrect.
> Suppose you have a machine that outputs a copy of itself, except that
> somewhere in its memory it contains a model number, and each time it
> makes a copy, it increments the model number on the copy.
> This machine and all of its descendants comprise an infinite set of
> distinct machines. Call the set S. Let K be the complexity of machine 1.
> Since there are only finitely many machines of complexity K or less, S
> must contain some machine with complexity greater than K. So let N be
> the smallest number such that machine N has complexity greater than K.
> Then machine N-1 has complexity less than or equal to K, so machine N-1
> is a machine that outputs a machine of greater algorithmic complexity
> than itself.
> - Peter de Blanc

Although correct, this isn't really the point. There is, in fact, a
theorem (
which shows that the K complexity of any computable function's output
must be less than the complexity of the function + the complexity of
the input + a small constant. But this isn't of any great significance
to AGI, as K complexity isn't really what we care about. A billion
PCs, for instance, probably have K complexity within a few orders of
magnitude of a single PC. This doesn't mean that the utility of a
billion PCs is within a few OOM of a single PC, or that the potential
thinking capacity of a billion PCs is within a few OOM of a single PC.

As an aside, the input to any real-world device will have a huge
complexity anyway, so the whole issue is moot.

 - Tom

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT