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