of short programs, that in general it is impossible for long random strings to have short programs. In other words, they have high Kolmogorov complexity.

An important property of K is that it is nearly independent of the choice of U. To see why, consider what happens if we switch from U, in the above definition of K, to some other universal Turing machine U
′
. Due to the universality property of U
′
, there exists a program q that allows U
′
to simulate U. Thus, if we give U
′ both q and p as inputs, it can simulate U running p and thereby compute U(p). It follows then that switching from U to U
′
in our definition of K above incurs at most an additional cost of l(q) bits in minimal program length. The constant l(q) is independent of which string x we are measuring the complexity of, and for reasonable universal Turing machines, this constant will be small. This invariance property makes K an excellent universal complexity measure. For an extensive treatment of Kolmogorov complexity see [LV97] or [Cal02].

In our current application we need to measure the complexity of the computable measures that describe environments. It can be shown that this set can be enumerated µ1, µ2, µ3**, . . .** (see Theorem 4.3.1 in [LV97]). Using a simple encoding method we can express each index as a binary string, written hii. In a sense this binary string is a description of an environment with respect to our enumeration. This lets us define the complexity of an environment µi to be K(µi) := K(hii). Intuitively, if a short program can be used to describe the program for an environment µi, then this environment will have a low complexity.

This answers our problem of needing to be able to measure the complexity of environments, but we are not done yet. In order to formalise Occam's razor we need to have a way to assign an a priori probability to environments in such a way that complex environments are less likely, and simple environments more likely. If we consider that each environment µiis described by a minimal length program that is a binary string, then the natural way to do this is to consider each additional bit of program length to reduce the environment's probability by one half, reflecting the fact that each bit has two possible states. This gives us what is known as the algorithmic probability distribution over the space of environments, defined 2−K(µ). This distribution has powerful properties that essentially solve long-standing open philosophical, statistical, and computational problems in the area of inductive inference [Hut07a]. Furthermore, the distribution can be used to define powerful universal learning agents that have provably optimal performance [Hut05].

Bringing all these pieces together, we can now define our formal measure of intelligence for arbitrary systems. Let E be the space of all computable reward summable environmental measures with respect to the reference machine U, and let K be the Kolmogorov complexity function. The expected performance of agent π with respect to the universal distribution 2−K(µ) over the space of all environments E is given by,

$$\Upsilon(\pi)\;:=\;\sum_{\mu\in E}\,2^{-K(\mu)}\,V_{\mu}^{\pi}.$$

We call this the universal intelligence of agent π.

Consider how this equation corresponds to our informal definition. We needed a measure of an agent's general ability to achieve goals in a wide range of environments. Clearly present in the equation is the agent π, the environment µ and, implicit in the environment, a goal. The agent's "ability to achieve" is represented by the value function V
π µ
. By a
"wide range of environments" we have taken the space of all well defined reward summable environments, where these environments have been characterised as computable measures