CONVERGENCE OF EXPECTED UTILITIES WITH ALGORITHMIC PROBABILITY DISTRIBUTIONS1

## 1. Abstract

We consider an agent interacting with an unknown environment. The **environment is a function which maps natural numbers to natural numbers; the agent's** set of hypotheses about the environment contains all such functions which are computable and compatible with a finite set of known input-output pairs, **and the agent**
assigns a positive probability to each such hypothesis (Probability distributions over all computable functions are used in theoretical AI systems such as AIXI (Hutter, 2007)). We do not require that this probability distribution be computable, but it must be bounded below by a positive computable function.

The agent has a utility function on outputs from the environment. We show that if this utility function is bounded below in absolute value by an unbounded computable function, then the expected utility of any input is undefined.

This implies that a computable utility function will have convergent expected utilities iff that function is bounded.

## 2. Notation

Here we set up our notation.

Let R be the set of partial µ**-recursive functions, and let** S = R ∩ N
N**; that is,**
S is the set of total µ**-recursive functions on a single argument. We will use an**
index R = {φn}∞
n=0, where our index φ **is a G¨odel numbering of the computable**
functions.

Let h ∈ N
N **be the true function that describes the environment. The agent has**
some finite set of tested inputs I, so the agent knows the value of h(i**) for all** i ∈ I.

Let SI = {f ∈ S : (∀i ∈ I), f(i) = h(i)}. That is, SI **is the set of hypotheses which**
agree with the agent's knowledge of tested inputs.

Let H **be our set of hypotheses about the environment, with** SI ⊆ H ⊆ N
N.

Let p : H → R **be our probability distribution on the hypothesis set. We require**
that there exist some computable function ¯p : N → Q **such that (**∀φn ∈ SI ), 0 <
p¯(n) ≤ p(φn).

Let U : N → R be the agent's utility function. We suppose that U **is unbounded,**
and that there exists an unbounded computable function U¯ : N → Q : (∀n ∈ N), |U¯ (n)**| ≤ |**U(n)|.

3. Proof of Divergence of Expected Utilities Fix k ∈ (N − I**), an input whose expected utility we will consider. Then define**
B : N → N**, with**

## (1) (∀X ∈ N), B(X) = Max {Φn(K) : N ∈ N, N ≤ X}

The sequence {B(j)}
∞

j=0 **can be thought of as an analog of the Busy Beaver**
numbers (Rad´o, 1962). This sequence will be used in proving our main result. Note that B **is not a computable function, as we are about to show.**
Lemma 1. Let f ∈ S. Then B(x) > f(x) **infinitely often.**
Proof. Suppose not. Then B(x) > f(x) only finitely many times, so let F(x) =
1 + f(x) + max {B(x) − f(x) : x ∈ N}. Then F ∈ S, and (∀x ∈ N), F(x) > B(x).

Let Q : N
2 → N, Q(i, x) = F(i**). By a corollary of the recursion theorem (Kleene,**
1938), there exists p ∈ N such that (∀x ∈ N), φp(x) = Q(p, x) = F(p).