Twitter user @atroyn claims that recursive self-improvement is impossible because of Kolmogorov complexity. Quoting most of[1] the argument here:
here is an argument against the possibility of recursive self improvement of any 'intelligent' computer program, based on kolmogorov complexity.
intelligence is the ability to make correct predictions about the state of the world given available information.
each program which makes predictions about the world has a kolmogorov complexity corresponding to the length of the shortest string which can express that program
for a given program p call this complexity k.
(unfortunately k(p) is in general uncomputable, the proof reduces to the halting problem, but that's not important here)
more intelligence (in our definition) implies the ability to predict more of the world more accurately, i.e. to express more of the world's complexity - this implies that a more intelligent program p2 necessarily has more complexity than a less intelligent p1
to see that this is necessarily so, note that if we could predict the world equally accurately as p1's prediction with a program p0 with k0 < k1, then we have a contradiction since k1 was supposed to be the minimal expression of intelligence at that level
in order to get recursive self improvement, you need a program p1 which is capable of emitting p2 which is better able to predict the world than p1 - i.e., we need p1 to emit p2 such that k2 > k1
but this is a contradiction.
[...]
The mistake here is the assumption that a program that models the world better necessarily has a higher Kolmogorov complexity. Originally, Kolmogorov complexity measured the complexity of bit strings. But we're talking about predictors here, things that observe the world and spit out probability distributions over observed outcomes. In the context of predictors, Kolmogorov complexity measures the complexity of a function from observations to predictions.
In the case of ideal Bayesian reasoning, we can nail down such a function just by specifying a prior, eg. the Solomonoff prior. (Plus, an approximation scheme to keep things computable, I guess.) This doesn't take a very large program to implement. But a non-ideal reasoner will screw up in many cases, and there's information contained in the exact way it screws up for each set of observations. Such reasoners can have an almost arbitrarily high Kolmogorov complexity, and they're all worse than the ideal Bayesian program.
In other words, the successor program has Kolmogorov complexity less than or equal to that of its predecessor, but so what? That doesn't imply that it's worse.
(Also, Kolmogorov complexity doesn't care about how much time a program takes to run at all, but in the real world it's an important consideration, and a target for self-improvement.)
That concludes this post: without the assumption that higher Kolmogorov complexity is better, the whole argument falls apart.
The rest of the thread briefly touches on the issue of how an AI could know that its successor would necessarily be an improvement. The discussion there is kind of doomed since it's done with the goal of showing that the successor has lower or equal Kolmogorov complexity than the original, which is uninteresting, though we can see right away that it must be true, assuming that the original writes the successor before observing the world at all. But there's an interesting version of the question, which asks about the set of axioms used by the systems to reason about the world, rather than the Kolmogorov complexity. See this paper by Yudkowsky and Herreshoff for details. âŠď¸
(Reaction to the first sentence: "Is this going to be an argument that would imply that humans can't improve their own intelligence?")
Yeah, his first wrong statement in the argument is "a more intelligent program p2 necessarily has more complexity than a less intelligent p1". I would use an example along the lines of "p1 has a hundred data points about the path of a ball thrown over the surface of the Moon, and uses linear interpolation; p2 describes that path using a parabola defined by the initial position and velocity of the projectile and the gravitational pull at the surface of the Moon". Or "rigid projectiles A and B will collide in a vacuum, and the task is to predict their paths; p1 has data down to the atom about projectile A, and no data at all about projectile B; p2 has the mass, position, and velocity of both projectiles". Or, for that matter, "p1 has several megabytes of incorrect data which it incorporates into its predictions".
It seems he may have confused himself into assuming that p1 is the most intelligent possible program of Kolmogorov complexity k1. (He later says "... then we have a contradiction since k1 was supposed to be the minimal expression of intelligence at that level". Wrong; k1 was supposed to be the minimal expression of that particular intelligence p1, not the minimal expression of some set of possible intelligences.) Then it would follow that any more intelligent (i.e. better-predicting, by his definition) program must be more complex.