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

From: Peter de Blanc (peter@spaceandgames.com)
Date: Sun Jun 22 2008 - 19:23:38 MDT


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



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