exactly what, and what not, to test for. Thus we consider Psychometric AI, at least as it is currently formulated, to only partially address this central question.

C-Test. One perspective among psychologists who support the g-factor view of intelligence, is that intelligence is "the ability to deal with complexity"[Got97b]. Thus, in a test of intelligence, the most difficult questions are the ones that are the most complex because these will, by definition, require the most intelligence to solve. It follows then that if we could formally define and measure the complexity of test problems using complexity theory we could construct a formal test of intelligence. The possibility of doing this was perhaps first suggested by Chaitin [Cha82]. While this path requires numerous difficulties to be dealt with, we believe that it is the most natural and offers many advantages: It is formally motivated, precisely defined and potentially could be used to measure the performance of both computers and biological systems on the same scale without the problem of bias towards any particular species or culture.

Essentially this is the approach that we have taken. Universal intelligence is based our the universally optimal AIXI agent for active environments, which in turn is based on Kolmogorov complexity and Solomonoff's universal model of sequence prediction. A relative of universal intelligence is the C-Test of Hern´andez-Orallo which was also inspired by Solomonoff induction and Kolmogorov complexity [HO00b, HOMC98]. If we gloss over some technicalities, the essential relationships look like this:

| Universal agent     | Universal test       |                        |
|---------------------|----------------------|------------------------|
| Passive environment | Solomonoff induction | C-Test                 |
| Active environment  | AIXI                 | Universal intelligence |

The C-Test consists of a number of sequence prediction and abduction problems similar to those that appear in many standard IQ tests. The test has been successfully applied to humans with intuitively reasonable results [HOMC98, HO00a]. Similar to standard IQ tests, the C-Test always ensures that each question has an unambiguous answer in the sense that there is always one hypothesis that is consistent with the observed pattern that has significantly lower complexity than the alternatives. Other than making the test easier to score, it has the added advantage of reducing the test's sensitivity to changes in the reference machine.

The key difference to sequence problems that appear in standard intelligence tests is that the questions are based on a formally expressed measure of complexity. To overcome the problem of Kolmogorov complexity not being computable, the C-Test instead uses Levin's Kt complexity [Lev73]. In order to retain the invariance property of Kolmogorov complexity, Levin complexity requires the additional assumption that the universal Turing machines are able to simulate each other in linear time. As far as we know, this is the only formal definition of intelligence that has so far produced a usable test of intelligence.

To illustrate the C-Test, below are some example problems taken from [HOMC98].

Beside each question is its complexity, naturally more complex patterns are also more difficult: