
| Sequence Prediction Test   |                               |                        |    |
|----------------------------|-------------------------------|------------------------|----|
| Complexity                 | Sequence                      | Answer                 |    |
| 9                          | a, d, g, j,                   | , . . .                | m  |
| 12                         | a, a, z, c, y, e, x,          | , . . .                | g  |
| 14                         | c, a, b, d, b, c, c, e, c, d, | , . . .                | d  |
| Sequence Abduction Test    |                               |                        |    |
| Complexity                 | Sequence                      | Answer                 |    |
| 8                          | a,                            | , a, z, a, y, a, . . . | a  |
| 10                         | a, x,                         | , v, w, t, u, . . .    | y  |
| 13                         | a, y, w,                      | , w, u, w, u, s, . . . | y  |

Our main criticism of the C-Test is that it is a static test limited to passive environments. As we have argued earlier, we believe that a better approach is to use dynamic intelligence tests where the agent must interact with an environment in order to solve problems. As AIXI is a generalisation of Solomonoff induction from passive to active environments, universal intelligence could be viewed as generalising the C-Test from passive to active environments. Smith's Test. Another complexity based formal definition of intelligence that appeared recently in an unpublished report is due to W. D. Smith [Smi06]. His approach has a number of connections to our work, indeed Smith states that his work is largely a
". . . rediscovery of recent work by Marcus Hutter". Perhaps this is over stating the similarities because while there are some connections, there are also many important differences.

The basic structure of Smith's definition is that an agent faces a series of problems that are generated by an algorithm. In each iteration the agent must try to produce the correct response to the problem that it has been given. The problem generator then responds with a score of how good the agent's answer was. If the agent so desires it can submit another answer to the same problem. At some point the agent requests to the problem generator to move onto the next problem and the score that the agent received for its last answer to the current problem is then added to its cumulative score. Each interaction cycle counts as one time step and the agent's intelligence is then its total cumulative score considered as a function of time. In order to keep things feasible, the problems must all be in the complexity class P, that is, decision problems which can be solved by a deterministic Turing machine in polynomial time.

We have three main criticisms of Smith's definition. Firstly, while for practical reasons it might make sense to restrict problems to be in P, we do not see why this practical restriction should be a part of the very definition of intelligence. If some breakthrough meant that agents could solve difficult problems in not just P but sometimes in NP as well, then surely these new agents would be more intelligent? We had similar objections to informal definitions of machine intelligence that included efficiency requirements in Subsection 4.1.

Our second criticism is that the way intelligence is measured is essentially static, that is, the environments are passive. As we have argued before, we believe that dynamic testing in active environments is a better measure of a system's intelligence. To put this