Re: [sl4] A model of RSI

From: Stuart Armstrong (
Date: Wed Sep 17 2008 - 08:30:49 MDT

> I think you are right that we can't distinguish between code and data. If we use the definitions in my paper then there is no difference between RSI (the program rewriting itself) and a simple program with a goal (meaning that the utility of the output would increase if its run time limit were relaxed).
> So how could RSI be defined in a meaningful way?

By engineering, not mathematics. A RSI program with a finite set of
data is mathematically equivalent to a universal Turing machine
running a fixed integer. But this equivalence is virtually never used
in practice, because it's nearly impossible to calculate and nearly
meaningless when you do so!

So a RSI has to be a statement about the actual architecture of a
program, not about the equivalent Turing machine. Your model seems
acceptable as a definition, as far as I can tell (there will be
others). A heuristic definition of RSI could be a program in an
architecture that returns, after some time, to state similar to the
one it started with, except with an improvement. The formal definition
would be given by specifying this architechture. For instance, you
could demand that a program has to start in a certain isolated
computer, with a certain amount of free space, always accepting
certain inputs. Subject to these constraints, a RSI makes sense.

As an aside, the restriction from Kolmogorov complexity in your paper
isn't actually very restrictive. Real programs are hopelessly
inefficient for their length, even more so if you break them down into
machine code. There are vast possibilities for improvement; for
instance, P1 could incoporate the instruction "first, wait ten million
years, then start doing stuff", and each subsequent P knocks one year
off this total. The Kolmogorov complexity of P10 000 000 is slightly
lower than P1, but I know which program I'd want to use...


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