
## 5. Results

Let R be the set of all computable partial functions mapping N to N**, and let**
θ : N → R **be a computable index (analogous to our other index function** φ).

Let Lemma 2. Let f ∈ R *be a total function. Then* B(n) > f(n) *infinitely often.*
Proof. Suppose not. Then B(n) > f(n**) only finitely many times, so there exists**
some c ∈ N such that (∀n ∈ N) : f(n) + **c > B**(n).

Let C(n, m) = f(n) + c**. By a corollary of the Recursion Theorem, there exists**
m ∈ N such that (∀n ∈ N) : θm(n) = C(m, n) = f(m) + c.

By definition, B(m) ≥ θm(0) = C(m, 0) = f(m) + c > B(m). So B(m) > B(m),
which is a contradiction. 

Now suppose that at time n **+ 1, the agent has already taken actions** y n 1 and made observations x n 1
, and is considering the expected utility of policy p**. Let**
D = {s ∈ XN : s n 1 = x n 1 }.

Theorem 1. If U is computably unbounded from above on D*, then* E (U (x n 1Ψ (**Q, p, y**n 1, xn 1))|ΓQ(y n 1) = x n 1) *is either undefined or* +∞.

Proof. Let UL : Dp → Z **be as in definition 1. Then by Lemma 1, there exists** H : Z → Dpsuch that (∀m ∈ Z) : UL(H(m)) > m.

H here is intended to be used to construct sequences with high utility. **Since**
H **outputs a string rather than a sequence, we will pad it to get a sequence. Let**
c ∈ X **be some arbitrary word in the perception alphabet. Then let** H¯ : Z → D, where H¯ (n) is a sequence beginning with H(n), followed by **c, c, c, . . .** .

For brevity, let Wp (q) = x n 1 Ψ (**q, p, y**n 1, xn 1). Wp (q) represents the complete sequence of perceptions received by the agent, assuming that it continues to implement policy p **in environment** q.

We will now break up the expected utility into two terms, depending on **whether**
or not Q ∈ ΩC .

E (U (Wp (Q))|ΓQ(y n 1
) = x n 1
)
= P(Q ∈ ΩC )E (U (Wp (Q))|ΓQ(y n 1) = x n 1, Q ∈ ΩC)
+P(Q /∈ ΩC )E (U (Wp (Q))|ΓQ(y n 1
) = x n 1
, Q /∈ ΩC)
=X
q∈ΩC
U (Wp (q)) P ({q}|ΓQ(y n 1
) = x n 1
)
+P(Q /∈ ΩC )E (U (Wp (Q))|ΓQ(y n 1) = x n 1**, Q /**∈ ΩC )
We will show that the series:
q∈ΩC
U (Wp (q)) P ({q}|ΓQ(y n 1
) = x n 1
)
X
has infinitely many terms ≥ **1. We will do this by finding a sequence of environments whose utilities grows very quickly - more quickly than their probabilities**
can shrink.

(4) B(n**) = max**
k≤n θk (0)