Machine Super Intelligence

Machine Super Intelligence is Shane Legg’s 2008 PhD thesis. It tackles a deceptively simple question — what is intelligence, mathematically? — and answers it with a formal definition, plus a proof that a hypothetical agent called AIXI is as intelligent as any agent can be.

This page leans on two ideas worth meeting first: Kolmogorov Complexity (how “simple” a thing is, measured by the shortest program that produces it) and Reinforcement Learning (agents acting in environments to maximize reward).

Why Students Should Care

This is the closest thing AI theory has to a definition of intelligence — not a vibe, an equation.
Legg went on to co-found DeepMind; these ideas shaped how a generation of researchers thinks about AGI.
The thesis connects compression, prediction, and intelligence — the same connection that helps explain why language models trained to predict text end up looking smart.

The Question, In Plain English

Before the math: Legg’s proposal is that an agent is intelligent if it performs well across many different environments, with a twist — simple environments count more than convoluted ones. A chess engine that only plays chess is narrow; an agent that racks up reward in any world you drop it into is intelligent.

Defining Intelligence

Formally:

\Upsilon(\pi) = \sum_{\mu \in E} 2^{-K(\mu)} V_\mu^\pi

where:

$\pi$ is an agent (policy)
$\mu$ is an environment
$K(\mu)$ is the Kolmogorov complexity of $\mu$
$V_\mu^\pi$ is the expected reward of $\pi$ in $\mu$

You do not need to memorize the formula. It says: intelligence is average performance across all computable environments, where simpler environments get exponentially more weight. The weighting $2^{-K(\mu)}$ is a mathematical version of Occam’s razor.

The AIXI Agent

Given that definition, is there a best possible agent? Yes — AIXI:

a^*_t = \arg\max_{a_t} \sum_{o_t r_t} \sum_{\mu \in E} 2^{-K(\mu)} \mu(o_t r_t | a_t h_{<t})

At each step, AIXI:

Considers all possible environments (weighted by complexity)
Computes expected reward for each action
Chooses the action maximizing expected future reward

In plain English: AIXI hedges across every theory of how the world might work, favors the simple theories, and picks whatever action does best on average.

Interactive Demo

Explore the key concepts from the thesis:

Machine Super Intelligence

Universal Intelligence

Υ(π) = Σμ 2^(-K(μ)) V_μ^π

Performance weighted by environment simplicity

Intelligence Hierarchy

Narrow AI

Human

AGI

AIXI

AIXI is theoretically optimal but incomputable

Key Insight

Intelligence can be formalized as the ability to achieve goals across a wide range of environments.

Practical Limit

AIXI requires solving the halting problem—real systems must approximate.

Solomonoff Induction

How does AIXI predict what happens next? It uses Solomonoff’s universal prior:

P(x) = \sum_{p: U(p) = x*} 2^{-|p|}

The probability of observing $x$ is the sum over all programs that output $x$ , weighted by their brevity. Short programs dominate — again, Occam’s razor made precise. If many short programs produce your observations so far, their shared predictions get high probability.

Key Results

Theorem (Optimality): AIXI is the most intelligent agent:

\Upsilon(\text{AIXI}) \geq \Upsilon(\pi) \quad \forall \pi

No other agent achieves higher expected performance across all environments.

Theorem (Incomputability): AIXI cannot be computed.

The universal prior requires solving the halting problem, so no real machine can run AIXI. Real systems must approximate. This pair of results is the punchline of the thesis: perfect intelligence exists on paper and is provably out of reach in practice.

The Compression-Intelligence Connection

A key insight: compression and prediction are equivalent.

K(x_{1:n}) \approx -\log P(x_{1:n})

A good predictor is a good compressor, and vice versa: if you can predict the next symbol well, you can encode data in few bits, and a short description of data is exactly what a good predictor exploits. This connects AIXI to practical language models, which are trained purely to predict. See Kolmogorov Complexity and the MDL Tutorial for more on this thread.

Practical Approximations

Real AI systems approximate AIXI through:

Bounded computation: limited search depth
Finite environments: specific domain knowledge
Learned priors: neural networks instead of Solomonoff

Modern LLMs can be viewed as crude AIXI approximations trained on text.

Implications

Intelligence can be formalized mathematically
Optimal intelligence requires universal prediction
Real AI must make tractability/optimality tradeoffs
Scaling leads toward AIXI-like behavior

Common Confusion

AIXI vs. AGI: AIXI is a mathematical ideal, not a buildable system. It defines the ceiling, not a blueprint.
“Optimal” does not mean “achievable”: the thesis proves AIXI is best and that it is incomputable. Both theorems matter; quoting only the first is misleading.
Kolmogorov complexity vs. ordinary complexity: $K(\mu)$ is the length of the shortest program describing $\mu$ — a precise quantity (itself uncomputable), not an informal notion of “complicated.”

Where To Go Next

Read Kolmogorov Complexity for the simplicity measure at the heart of the definition.
Read Reinforcement Learning for the agent-environment-reward framing AIXI lives in.
Read the MDL Tutorial for the compression-as-learning idea in a practical setting.
Read Scaling Laws to see how “better prediction with more compute” plays out in real models.

Key Resource

Machine Super Intelligence — Shane Legg (PhD Thesis, 2008)
https://www.vetta.org/documents/Machine_Super_Intelligence.pdf