Re: [sl4] JAGI submission

From: Matt Mahoney (
Date: Wed Nov 26 2008 - 10:48:48 MST

--- On Tue, 11/25/08, Nick Tarleton <> wrote:

> Why do you identify intelligence with algorithmic complexity, again?

Eliezer pointed this out to me too. With unlimited computing power, the initial algorithmic complexity is irrelevant. You could prove anything that could be proven by running a simple program that enumerated all proofs. You could solve any problem that future humans could solve by simulating the universe with a 407 bit program for 2^407 steps, or even better, simulate all possible laws of physics with an even simpler program running for 2^814 steps.

Of course we don't have unlimited computing power, so prior knowledge of the environment does help, as in greater expected utility. Perhaps Legg's proof of the absence of an elegant theory of learning is not the best argument, however. I should just say that greater intelligence by most definitions is correlated with faster learning, which means more accumulated knowledge over a fixed time period.

> > The information gain for evolution is O(t), or 1 bit per population
> > doubling and selection.
> Really? Evolution isn't magic, and the suggestion that it can provably beat
> all forms of intelligence is extremely suspicious.

I never claimed that, only that evolution would beat RSI.

> I can run an evolving population in a closed simulation, where all the bits not
> describing the evolving agents and their environment start as 0, or
> something similarly low-complexity, and then apply your proof. This is for the
> whole population, and picking out a random individual would require
> individual information growing at O(a^t), but picking out the maximal
> individual(s) according to some utility function would only add a constant factor
> (complexity of the function).

For any algorithm with unlimited computing power (RSI or evolution), the distinction between O(t) and O(log t) growth of complexity is irrelevant. For real computers, it is important.

-- Matt Mahoney,

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