2 PETER DE BLANC DEPARTMENT OF MATHEMATICS TEMPLE UNIVERSITY
the environment. After n **cycles, the agent has output the string** y n 1
, and the environment has output the string x n 1**. Thus the agent's knowledge is given by the**
equation ΓQ (y n 1
) = x n 1
.

Agents such as AIXI (Hutter, 2007) choose actions by comparing **the expected**
utility of different policies. Thus we will focus, in this paper, on calculating the expected utility of a policy.

3. Assumptions about the Hypothesis Space Here we'll make further assumptions about the hypothesis space (Ω, F, P**). While**
we could succinctly make strong assumptions that would justify our **central claim,**
we will instead try to give somewhat weaker assumptions, even at the loss of some brevity.

Let ΩC **be the set of computable total functions mapping** Y
∗to X**. We will**
assume that Ω ⊇ ΩC and that (∀q ∈ ΩC ) : {q} ∈ F and P ({q}) > **0. Thus we**
assume that the agent assigns a nonzero probability to any computable environment function.

Let ΩP **be the set of computable partial functions from** Y
∗to X**. Then Ω**C ⊂ ΩP .

The computable partial functions ΩP **can be indexed by natural numbers, using**
a surjective computable index function φ : N → ΩP **. Since the codomain of** φ is a set of partial functions, it may be unclear what we mean when we say that φ is computable. We mean that (i, s) → (φ (i)) (s), whose codomain is X**, is a**
computable partial function. We will also use the notation φi = φ (i).

We'll now assume that there exists a computable total function ρ : N → Q **such**
that if φi ∈ ΩC , then 0 < ρ (i) ≤ P ({φ (i)}). Intuitively, we are saying that φ **is a**
way of describing computable functions using some sort of language, and that ρ is a way of specifying lower bounds on probabilities based on these descriptions. Note that we make no assumption about ρ (i**) when** φi ∈/ ΩC .

To see an example of a hypothesis space satisfying all of our assumptions, let Ω = ΩC , let F = 2ΩP , let φ be any programming language, and let ρ (i) = 2−i**. Let**
(2) O =X

$$O=\sum_{i\ni(\phi_{i}\in\Omega_{C})}\rho\left(i\right)$$
(2)  and for any $\omega\in\Omega$, let $\epsilon$
$$\left({\boldsymbol{3}}\right)$$
(3) P ({ω}) = 1OX
$$P\left(\{\omega\}\right)={\frac{1}{O}}\sum_{i\ni\left(\phi_{i}=\omega\right)}\rho\left(i\right)$$

4. Assumptions about the Utility Function Perhaps the most philosophically questionable assumption in this paper has already been made in defining the domain of the utility function U as XN**, the set**
of perception-sequences. This is like assuming that a person cares **not about his** or her family and friends, but about his or her perception of his or her family and friends.

Since the utility function U : XN → R **takes as its argument an infinite sequence,**
we must discuss what it means for such a function to be computable. **Obviously any** computation which terminates can only look at a finite number of terms. Therefore we will try to approximate U (x) using prefixes of x. We say that U **is computable**
if there exist computable functions UL, UU : X∗ → Q ∪ {−∞, +∞} **such that, if**
x ∈ XN and ¯x ∈ X∗ and ¯x ⊑ x, then: