Logical inductor limits are dense under pointwise convergence

Logical inductors [1] are very complex objects, and even their limits are hard to get a handle on. In this post, I investigate the topological properties of the set of all limits of logical inductors.

I’ll use the language of universal inductors [2], but everything I say will also hold for general logical inductors by conditioning. Also, the proofs can be made to apply directly to general logical inductors with relatively few changes.

Universal inductors are measures on Cantor space (i.e. the space $2^{ω}$ of infinite bit-strings) at every finite time, as well as in the limit (this is a bit nicer than the analogous situation for general logical inductors, which are measures on the space of completions of a theory only in the limit). There are many topologies on spaces of measures, and we can ask about topological properties under any of these. Interestingly, the set of universal inductor limits is dense in the topology of weak convergence, but not in the topology of strong convergence (or, a fortiori, the total variation metric topology).

It’s not immediately clear how to interpret this - should we think of the space of measures as being full of universal inductor limits, or should we think of universal inductor limits as being relatively few, with big holes where none exist? A relatively close analogy is the relationship between computable sets (or limit computable sets for a closer analogy) and arbitrary subsets of $N$ ; any subset of $N$ can be approximated pointwise by limit computable sets (indeed, even by finite sets), but may be impossible to approximate under the $ℓ^{1}$ norm, i.e. the number of differing bits. Now, on with the proofs!

Theorem 1: The set of limits of universal inductors is dense in the topology of weak convergence on the space of measures $Δ (2^{ω})$ .

Proof outline: We need to find a limit of universal inductors in any neighborhood of any measure $μ$ . That is, for any finite collection of continuous functions, we need a universal inductor that, in the limit, assigns expectations to each such function that is close to the expectation under $μ$ .

We do this with a modification of the standard universal inductor construction (section 5 of [1]), adding one additional trader to $T r a d i n g F i r m$ . This trader can buy and sell shares in events in order to keep these expectations within certain bounds, in a way similar to the Occam traders in the proof of theorem 4.6.4 in [1]. However, we give this trader a much larger budget than the others, allowing its control to be sufficiently tight.

Proof: It suffices to show that for any measure $μ$ on $2^{ω}$ , any finite set of bounded continuous functions $f_{i} : 2^{ω} \to R$ for $i \in {1, \dots, n}$ and any $ε > 0$ , there is a universal inductor limit $ν$ such that $∣ ∣ E_{μ} f - E_{ν} f ∣ ∣ < ε$ for all $1 \leq i \leq n$ .

It's easier to work with prefixes of bit-strings than continuous functions, so we'll pass to such a description. Consider some $f_{i}$ . For each world $W \in 2^{ω}$ , there is some clopen set $A \subseteq 2^{ω}$ such that $∣ ∣ f_{i} (W) - f_{i} (˜ W) ∣ ∣ < \frac{ε}{3}$ for all $˜ W \in A$ . By compactness, we can pick a finite cover $(A_{i, j})_{j = 1}^{m_{i}}$ . Letting $B_{i, j} = A_{i, j} ∖ ⋃_{k = 1}^{j - 1} A_{i, k}$ , we get a disjoint open cover. By construction, for each $1 \leq j \leq m_{i}$ , there is some $W_{i, j}$ such that for all $˜ W \in B_{i, j}$ , we have $∣ ∣ f_{i} (W_{i, j}) - f_{i} (˜ W) ∣ ∣ < \frac{ε}{3}$ , and we can define a simple function $g_{i}$ that takes the locally constant value $f_{i} (W_{i, j})$ on each set $B_{i, j}$ . Then, $\begin{matrix} ∣ ∣ E_{μ} (f_{i}) - E_{ν} (f_{i}) ∣ ∣ & \leq ∣ ∣ E_{μ} (f_{i} - g_{i}) ∣ ∣ + ∣ ∣ E_{μ} (g_{i}) - E_{ν} (g_{i}) ∣ ∣ + | E_{ν} (g_{i} - f_{i}) | \leq ∣ ∣ E_{μ} (g_{i}) - E_{ν} (g_{i}) ∣ ∣ + \frac{2}{3} ε, \end{matrix}$ so we need only control what our universal inductor limit $ν$ thinks of the clopen sets $B_{i, j}$ .

Pass to a single disjoint cover $(C_{k})_{k = 1}^{p}$ of $2^{ω}$ by clopen sets such that for each $1 \leq i \leq n$ and $1 \leq j \leq m_{i}$ , the set $B_{i, j}$ is a union of sets $C_{k}$ . Further, take $M \in R^{+}$ such that $| g_{i} | \leq M$ for all $i$ , and pick rational numbers $(a_{k})_{k = 1}^{p}$ in $(0, 1) \cap Q$ such that $\sum_{k = 1}^{p} a_{k} = 1$ and $| μ (C_{k}) - a_{k} | < \frac{ε}{3 p M}$ ; note we can do this since $\sum_{k = 1}^{p} μ (C_{k}) = 1$ . If we can arrange $ν$ so that $ν (C_{k}) = a_{k}$ for all $k$ , we can conclude $\begin{matrix} ∣ ∣ E_{μ} (g_{i}) - E_{ν} (g_{i}) ∣ ∣ & \leq p \sum k = 1 ∣ ∣ ∣ \int_{C_{k}} g_{i} d μ - \int_{C_{k}} g_{i} d ν ∣ ∣ ∣ = p \sum k = 1 | g_{i} (C_{k}) \cdot (μ (C_{k}) - ν (C_{k})) | \leq p \sum k = 1 M | μ (C_{k}) - a_{k} | < ε / 3 \end{matrix}$ as desired.

We now need only find a universal inductor limit $ν$ such that $ν (C_{k}) = a_{k}$ for all $1 \leq k \leq p$ . As mentioned above, we modify $T r a d i n g F i r m$ by adding a trader. For each $C_{k}$ , take a sentence $ϕ_{k}$ that holds exactly on $C_{k}$ , and define the trader ${V i c e}_{n} = p \sum k = 1 [{I n d}_{1} (ϕ_{k}^{* n} < a_{k}) - {I n d}_{1} (ϕ_{k}^{* n} > a_{k})] \cdot (ϕ_{k} - ϕ_{k}^{* n}) .$ Then, with $S_{n}^{k}$ and $B u d g e t e r$ as in section 5 of [1], we can define ${T r a d i n g F i r m}_{n} (P_{\leq n - 1}) = {V i c e}_{n} + \sum ℓ \in N^{+} \sum b \in N^{+} 2^{- ℓ - b} {B u d g e t e r}_{n} (b, S_{\leq n}^{k}, P_{\leq n - 1}),$ analogous to (5.3.2) in [1]. This is an $n$ -strategy by an extension of the argument in [1] so, like in the construction of $L I A$ there, we can define a belief sequence $ν_{n} = {M a r k e t M a k e r}_{n} ({T r a d i n g F i r m}_{n} (ν_{\leq n - 1}), ν_{\leq n - 1}),$ and this will not be exploitable by $T r a d i n g F i r m$ .

Next, we will use the fact that $T r a d i n g F i r m$ does not exploit $¯ ¯ ¯ ν$ to investigate how $\mathrm{Vice} $'s holdings behave over time when trading on the market $¯ ¯ ¯ ν$ . As in lemma 5.3.3 in [1], letting $F_{n} = {T r a d i n g F i r m}_{n} (ν_{\leq n - 1})$ , $V_{n} = {V i c e}_{n} (ν_{\leq n - 1})$ and $B_{n}^{b, ℓ} = {B u d g e t e r}_{n} (b, S_{\leq n}^{ℓ}, ν_{\leq n - 1})$ , we have that in any world $W \in 2^{ω}$ and at any step $n \in N^{+}$ , $\begin{matrix} W (\sum i \leq n F_{n}) & = W (\sum i \leq n V_{n}) + W ⎛ ⎝ \sum i \leq n \sum ℓ \in N^{+} \sum b \in N^{+} 2^{- ℓ - b} B_{n}^{b, ℓ} ⎞ ⎠ \geq W (\sum i \leq n V_{n}) - 2, \end{matrix}$ so since $T r a d i n g F i r m$ cannot exploit $¯ ¯ ¯ ν$ by construction, $V i c e$ cannot as well.

Now, notice that, for fixed $n \in N^{+}$ , the value $W (V_{n})$ is constant by construction as $W$ varies within any one set $C_{k}$ , so, regarding $(a_{k})_{k = 1}^{p}$ as a measure on the finite $σ$ -algebra generated by $(C_{k})_{k = 1}^{p}$ , it makes sense to integrate $W (V_{n})$ with respect to that measure. For each $n$ , we have that this integral is $\begin{matrix} p \sum k = 1 C_{k} (V_{n}) a_{k} & = p \sum k = 1 p \sum k^{'} = 1 C_{k} [({I n d}_{1} (ν_{n} (ϕ_{k^{'}}) < a_{k^{'}}) - {I n d}_{1} (ν_{n} (ϕ_{k^{'}}) > a_{k^{'}})) \cdot (ϕ_{k^{'}} - ν_{n} (ϕ_{k^{'}}))] \cdot a_{k} = p \sum k^{'} = 1 ({I n d}_{1} (ν_{n} (ϕ_{k^{'}}) < a_{k^{'}}) - {I n d}_{1} (ν_{n} (ϕ_{k^{'}}) > a_{k^{'}})) p \sum k = 1 [C_{k} (ϕ_{k^{'}}) \cdot a_{k} - ν_{n} (ϕ_{k^{'}}) \cdot a_{k}] = p \sum k^{'} = 1 ({I n d}_{1} (ν_{n} (ϕ_{k^{'}}) < a_{k^{'}}) - {I n d}_{1} (ν_{n} (ϕ_{k^{'}}) > a_{k^{'}})) \cdot (a_{k^{'}} - ν_{n} (ϕ_{k^{'}})) \geq 0, \end{matrix}$ since for each $k^{'}$ the two factors are either both positive, both negative, or both zero. This is to say, the value of $V i c e$ 's holdings according to the measure given by the numbers $a_{k}$ is nondecreasing over time. Since $a_{k} > 0$ for all $k$ , we can use our upper bound on $W (V_{n})$ to derive a lower bound; if $L \in R$ is such that $˜ W (\sum_{i = 1}^{n} V_{i}) \leq L$ for all $˜ W \in 2^{ω}$ and $n \in N^{+}$ , then for any $W$ , say, in $C_{k}$ , $\begin{matrix} W (n \sum i = 1 V_{i}) & = n \sum i = 1 W (V_{i}) \geq n \sum i = 1 - \frac{1}{a_{k}} \sum k^{'} \neq k C_{k^{'}} (V_{i}) a_{k^{'}} \geq - \frac{1}{a_{k}} \sum k^{'} \neq k L \cdot a_{k^{'}} . \end{matrix}$

We can conclude two things from this, which will finish the argument. First, we get an analogue of lemma 5.3.3 from [1], from which it follows that $¯ ¯ ¯ ν$ is a universal inductor (ignoring minor differences between the definitions of universal and logical inductors; see [2]). This is since for any of the budgeters $B^{b, ℓ}$ defined above, $\begin{matrix} W (n \sum i = 1 F_{i}) & = 2^{- b - ℓ} W (n \sum i = 1 B_{i}^{b, ℓ}) + W (n \sum i = 1 V_{i}) + W ⎛ ⎝ n \sum i = 1 \sum (b^{'}, ℓ^{'}) \neq (b, ℓ) 2^{- b^{'} - ℓ^{'}} B_{i}^{b^{'}, ℓ^{'}} ⎞ ⎠ \geq 2^{- b - ℓ} W (n \sum i = 1 B_{i}^{b, ℓ}) + W (n \sum i = 1 V_{i}) - 2, \end{matrix}$ so $B^{b, ℓ}$ has its holdings bounded uniformly in $W$ and $n$ .

Second, defining $ν = {lim}_{n \to \infty} ν_{n}$ , we get the desired property that $ν (C_{k}) = a_{k}$ for all $k$ . Suppose for contradiction that $ν (C_{k}) < a_{k}$ . Taking $δ > 0$ with $ν (C_{k}) + δ < a_{k}$ , there is some $N \in N^{+}$ such that if $n \geq N$ , then $| ν_{n} (C_{k}) - ν (C_{k}) | < \frac{δ}{2}$ . Then, for all such $n$ , it follows that $ν_{n} ({I n d}_{1} (ϕ_{k}^{* n} < a_{k})) > \frac{δ}{2},$ and $ν_{n} ({I n d}_{1} (ϕ_{k}^{* n} > a_{k})) = 0,$ so in any world $W \in C_{k}$ , $W (V_{n}) \geq \frac{δ}{2} (1 - ν_{n} (ϕ_{k})) \geq \frac{δ}{2} (1 - a_{k}),$ and so $V i c e$ 's holdings go to infinity in this world, giving the desired contradiction. By a symmetrical argument, we can't have $ν (C_{k}) > a_{k}$ , so $ν (C_{k}) = a_{k}$ as desired. $□$

One thing I want to note about the above proof is that, to my knowledge, it is the first construction of a logical inductor for which the limiting probability of a particular independent sentence is known.

Theorem 2: The set of universal inductor limits is not dense in the topology of strong convergence of measures or the total variation distance topology on $Δ (2^{ω})$ .

Proof: The total variation distance induces a finer topology than the topology of strong convergence, so it suffices to show that this set is not dense under strong convergence. Take any world $W \in 2^{ω}$ that is not $Δ_{2}$ , and let $μ \in Δ (2^{ω})$ be a point mass on $W$ . The singleton ${W}$ is a measurable set, so it suffices to show that for any universal inductor limit $ν$ , we have $μ ({W}) = 1$ but $ν ({W}) = 0$ .

Suppose for contradiction that there was some universal inductor limit $ν$ for which this failed. By the Lebesgue density theorem, there is some clopen set $A$ such that $W \in A$ and $\frac{ν ({W})}{ν (A)} > \frac{1}{2} .$ Then, it is possible to compute $W$ from $ν$ as follows. Each $k \in N$ corresponds to some clopen subbase element $U_{k}$ for the topology on $2^{ω}$ . In order to determin whether $k \in W$ , we can improve our estimates of $ν (U_{k} \cap A)$ and $ν (A)$ until we've determined either $ν (U_{k} \cap A) / ν (A) > 1 / 2$ or $ν (U_{k} \cap A) / ν (A) < 1 / 2$ . One of these must be the case, and we will eventually determine it since these are both open conditions. Thus, since $ν$ is $Δ_{2}$ , the set $W$ is as well, contradicting the hypothesis. $□$

[1] Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, and Jessica Taylor. 2016. “Logical induction.” arXiv: 1609.03543 [cs.AI].

[2] Scott Garrabrant. 2016. “Universal inductors.” https://agentfoundations.org/item?id=941.

LESSWRONG
LW

LESSWRONG
LW

5

Logical inductor limits are dense under pointwise convergence

5

Ω 4

5

Ω 4