Hutter's AIXI, http://www.idsia.ch/~marcus/ai/paixi.htm makes another
argument for the connection between compression and AI that is more
general than the Turing test.  He proves that the optimal behavior of
an agent (an interactive system that receives a reward signal from an
unknown environment) is to guess that the environement is most likely
computed by the shortest possible program that is consistent with the
behavior observed so far. In other words, the most likely outcome for
any experiment is the one with the simplest explanation, where
"simplest" means the smallest program that could model what you
currently know about the universe.

He gives a formal proof, but it basically says that the only possible
distribution of the infinite set of programs (or strings) with nonzero
probability is one which favors shorter programs over longer ones.
Given any string of length n with probability p > 0, there are an
infinite set of strings longer than n, but only a finite number of
these can have probability higher than p.

-- Matt Mahoney