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

From: Matt Mahoney (
Date: Fri Jun 20 2008 - 11:26:53 MDT

--- On Fri, 6/20/08, Stuart Armstrong <> wrote:

> > I think this violates the criterion Matt gave originally "It would
> > also not include simulations where agents receiving external
> > information on how to improve themselves. They have to
> > figure it out for themselves."
> I admit it wasn't a proper solution, just a crude
> simplistic model. "Figuring out for themselves" isn't clearly
> defined, though; I'm
> pretty sure we could migrate the model to something more
> along the lines Matt intended.
> But the main weakness is that we are much, much smarter
> than these models. I've argued that we have:
> 1) non-evolutionary RSI for dumb models
> 2) approximate ways of measuring intelligence for above
> human entities
> The big hole is the connection between the two: is human-level or
> higher than human level non-evolutionary RSI possible? The proof of
> that is only in the pudding; in the meantimes, do we have many
> non-evolutionary RSI at a higher level than my dumb models?
> (maybe even useful one ;-)

By "figuring out for themselves", I mean that the parent has sole authority to make fitness decisions for its children. This may not be achievable in practice because a child may be killed by events beyond the parent's control.

Nevertheless, there ought to be at least a mathematical model of (non-evolutionary) RSI. The model of artificially crippled agents self-improving is not RSI unless it can be demonstrated that the crippled agents are able to decide whether the limitation has been removed in its offspring. Also, the model is bounded to the intelligence level that existed in the original uncrippled agents.

Also, most of the tests for above-human intelligence mentioned earlier, like winning an election or producing a blockbuster movie require judgment by a large group of people (voters or movie goers), which is collectively more intelligent than any individual. How do you collectively test for intelligence greater than the collective intelligence of all humanity?

One possible RSI model is to use tests that are hard to solve but easy to check. Some examples: factoring a product of two randomly chosen 1000 digit prime numbers, finding a subset of integers that add to 0, finding a smaller program that outputs a particular snapshot of Wikipedia, proving theorems (which can be mechanically checked), or winning at chess.

For example, an agent could produce a randomly modified copy of itself and the two would play chess. The two agents agree that the loser dies. After many iterations, you should have an agent that plays chess very well. However, there are a couple of flaws. First, because the change is random, the child might not agree to the rules, for example, it may kill its opponent after losing its queen. But even if we eliminate cheating in our model, there remains the problem that at some point the agents completely solve the problem of chess, perhaps proving that the game always ends in a draw if the players play optimally (or white always wins). Then no more improvement is possible.

We might overcome this problem by using a scalable test such as factoring successively larger numbers. But there is a more fundamental problem. There are no provably hard problems. We only know that a problem is hard if lots of people try and fail to solve it. So solving a problem only means you are slightly more intelligent than the group that has failed at it. That's not RSI unless you can improve beyond that group.

We strongly suspect that subset-sum is hard because it is NP-complete, but we have not proved P != NP. We suspect NP-complete problems are hard only because lots of people have failed to solve any of them. Likewise, we suspect factoring is hard because lots of people have tried and failed to crack RSA public key encryption (or like Shor, found a polynomial time algorithm but don't have a quantum computer).

One could proceed without proof, i.e. if P != NP then an RSI model exists. Not so fast! Even if that is true, there are still many NP-complete problems that are easily decided for large n (e.g. subset-sum for {1,2,...,n} or {-1,1,2,...,n}). Likewise, even when you have a proof, like the halting problem, there are still many programs that can be proven to halt or not halt. Choosing a set of hard problems still requires as much intelligence as solving them.

One could argue that the following is RSI: An agent makes up problems that are easy to check, and may or may not be hard to solve (e.g. find x such that A + x = B for random A and B). The parent makes a modified copy of itself (including memories). Then they play to the death. Arguably the winner must be at least a little more intelligent than the loser on average. Perhaps this model is simple enough to test in software. The flaw, I believe, is that the child is less intelligent on average than the parent, and the fitness test does not detect intelligence well enough to compensate.

Any other ideas?

-- Matt Mahoney,

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