# Re: [sl4] A model of RSI

From: Matt Mahoney (matmahoney@yahoo.com)
Date: Mon Oct 13 2008 - 21:57:49 MDT

Denis,
If I understand your proposal, an example of a partial definition of a program might be a finite prefix of an infinite string output by an unknown program. The problem is to guess the rest of the string. A solution would be to guess the shortest program that could have output the given string, and then run the program to predict the rest of the string.

An example of self improvement would be if the program could rewrite itself so that the new version could solve the same problem faster, or find a better solution that made fewer prediction errors.

The problem is I want to distinguish between self improvement and learning. Suppose the program rewrote itself to include the solution it already found. I consider that learning, not self improvement.

That is why I defined self improvement for a closed system with no input. One can have a parent program create copies of itself with random variations and then give its children a fitness test based on some problem that is hard to solve but easy to check. The test could involve guessing the output of unknown programs under time constraints. But I argue that nontrivial unbounded RSI is not possible, regardless of the test, because algorithmic complexity cannot increase in a closed system faster than O(log n) after n generations.

-- Matt Mahoney, matmahoney@yahoo.com

--- On Sun, 10/12/08, Denis <dnsflex@yahoo.com> wrote:

> From: Denis <dnsflex@yahoo.com>
> Subject: Re: [sl4] A model of RSI
> To: sl4@sl4.org
> Date: Sunday, October 12, 2008, 7:27 PM
> To explain my point of view I need to define what is a
> problem.
>
> I think a problem can be defined by a partial definition of
> a program.
> We can cathegorize the problems in 3 different level of
> difficulties.
> 1) The problem is defined by an algorithm (program) with a
> low complexity , the solution is its implmentation.
> 2) The problem is totally defined by an algorithm/program
> with high complexity . This is what happen in the major part
> of cases , this program is called "specifications"
> of the problem , an example of this problem can be a list of
> costraints , all the NP-complete or others NP groups where
> we can write down simply a small program to give the
> solution but it take not feasible space-time complexity.
> This is also the most frequent programmer's problems ,
> converting high space-time complexity in a small space-time
> complexity.
> 3) The problem is defined partially by a program . This is
> the worst case , here we know only partially the solution,
> this case is about number sequence predictions , cathegory
> problems ...
> Here we need to find the best program ( the function )
> representing the partial definition, and then
> approximate/converting such program into a program limited
> by the available resources.
>
> So my idea to solve a problem is
> 1) Find the Kolmogorov complexity PK program of the problem
> 2) Find the program PR using the available resource with
> the same function of PK
> 3) Run PR
>
> (Yes, this is a very concise explanation with also
> different levels of uncomputability but this is the way)
>
> So what about Self improvement? If I call these 3 steps GS
> I can define a self improvements as the problem to find
> better solution to implement GS.
> Better solution can be defined by an usage of less
> space-time resources, so this mean to reduce the space-time
> complexity to solve point 1 , point 2 and point 3 .
> So the self improvement is strictly related to the solution
> of well known problems.
> You can do it directly or you can use GS to solve GS , but
> I don't think the last is a good idea becouse the
> complexity of GS(GS) is something outside from computers
> possibility.
> The biggest problem is the point 1 and you can not reduce
> its complexity without loss generality .
> I think this is the main problem : GS is too much general ,
> useless general .
> GS is a beautifull mathematical solution but unfeasible by
> its complexity.
> The way to speed up it , to improve it, is to specify a
> "context" .
> Specify a "context" don't mean lose
> generality for examples we can specify context adding
> knowledgement about universal distribution giving more
> information about K function but also we can restrict the
> domain using information about K only for real existing
> problems.
> I think the real existing problems are very very smaller
> than mathematical theoretical problems (the real space is
> not exponential), so we can use auxiliary information to
> reduce a lot the context without loss real generality.
>
> Denis.
>
>
>
> --- On Tue, 9/16/08, Matt Mahoney
> <matmahoney@yahoo.com> wrote:
>
> > From: Matt Mahoney <matmahoney@yahoo.com>
> > Subject: Re: [sl4] A model of RSI
> > To: sl4@sl4.org
> > Date: Tuesday, September 16, 2008, 11:31 AM
> > 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?
> >
> > Some examples I might consider to be self improvement:
> >
> > - Accumulating knowledge on how to better accumulate
> and
> > use knowledge.
> > - Books on how to write books.
> > - Computer aided software engineering.
> > - Computer aided hardware design of faster computers.
> > - Genetically engineering humans for larger brains.
> >
> > Some examples I would NOT consider RSI:
> >
> > - Machine learning.
> > - Human education.
> > - Evolution.
> > - Development of language and culture.
> > - Economic development.
> >
> > The distinction I want to make is that RSI does not
> make
> > use of external information not available at the
> start.
> > Specifically, the agents who execute the improvement
> > algorithm must know what the goal is, how to compute
> it, and
> > how to test themselves and/or their offspring as to
> whether
> > they are making progress toward this goal. In my
> examples of
> > non-RSI, the agents and the systems have different
> goals.
> > The teacher has different goals than the student.
> Evolution
> > has the "goal" of increasing competitive
> fitness,
> > which is at odds with the goals of agents that want to
> eat,
> > have sex, and not die. The economy has a
> "goal" of
> > producing a complex organization that can support a
> large
> > population efficiently, as opposed to the goals of
> > individuals to acquire money.
> >
> > So how can this idea be expressed formally as a
> property of
> > Turing machines?
> >
> >
> > -- Matt Mahoney, matmahoney@yahoo.com
> >
> >
> > --- On Mon, 9/15/08, Denis <dnsflex@yahoo.com>
> wrote:
> >
> > > From: Denis <dnsflex@yahoo.com>
> > > Subject: Re: [sl4] A model of RSI
> > > To: sl4@sl4.org
> > > Date: Monday, September 15, 2008, 4:09 PM
> > > I think if "RSI" mean a program
> searching to
> > > improve its behaviour without using others data
> can be
> > a
> > > good idea but it is very different to a
> > "rewriting
> > > itself" program.
> > > The "rewriting itsef" is a
> ill-definition
> > and the
> > > only thing is possible to achieve in this way is
> a
> > reduction
> > > on a costant C.
> > > For example given an universal Turing machine
> > accepting in
> > > input a program ( program without parameters)
> this
> > turing
> > > machine executing the program can use new empty
> cells
> > or
> > > rewrite a part or all the cells of the starting
> > program.
> > > If this program rewrite itself partially or
> totally by
> > C
> > > cells the only advantage you can have is to use
> also
> > this C
> > > cells in the elaboration.
> > > There is not substantially difference from
> program and
> > > data.
> > > The trick is that you can move the program in the
> > costant C
> > > and this disappear asymptotically.
> > > "Rewiting itself" is only an illusion.
> > > A nice example is the Hanoy tower . In the
> recursive
> > > program solving this problem you can watch at the
> > stack and
> > > you can think to it as a program with the
> istructions
> > to
> > > move the stones and this programs change! The
> trick is
> > that
> > > you are watching the wrong program!
> > >
> > > Denis.
> > >
> > > --- On Sun, 9/14/08, Matt Mahoney
> > > <matmahoney@yahoo.com> wrote:
> > >
> > > > From: Matt Mahoney
> <matmahoney@yahoo.com>
> > > > Subject: [sl4] A model of RSI
> > > > To: "sl4" <sl4@sl4.org>
> > > > Date: Sunday, September 14, 2008, 7:16 PM
> > > > I have written a (rather trivial)
> recursively
> > self
> > > improving
> > > > program, along with a draft of a paper that
> tries
> > to
> > > give a
> > > > reasonable but rigorous definition of RSI.
> Any