Re: [sl4] A model of RSI

From: Denis (
Date: Sun Oct 12 2008 - 17:27:52 MDT

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.


--- On Tue, 9/16/08, Matt Mahoney <> wrote:

> From: Matt Mahoney <>
> Subject: Re: [sl4] A model of RSI
> To:
> 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,
> --- On Mon, 9/15/08, Denis <> wrote:
> > From: Denis <>
> > Subject: Re: [sl4] A model of RSI
> > To:
> > 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
> > <> wrote:
> >
> > > From: Matt Mahoney <>
> > > Subject: [sl4] A model of RSI
> > > To: "sl4" <>
> > > 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
> > comments are
> > > appreciated.
> > >
> > >
> > >
> > > -- Matt Mahoney,


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