From: Thomas McCabe (pphysics141@gmail.com)
Date: Tue Jun 24 2008 - 21:43:22 MDT
On Sun, Jun 22, 2008 at 9:23 PM, Peter de Blanc <peter@spaceandgames.com> 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 (http://www.scholarpedia.org/article/Algorithmic_information_theory#Algorithmic_.22Kolmogorov.22_Complexity_.28AC.29)
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 http://www.acceleratingfuture.com/tom
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT