[Attention Conservation Notice: This just recaps an old result and patches a hole in it, it doesn't contain substantially new ideas.]
Universal Inductors can be thought of as logical inductors over bitstrings, which are notable because they can act as a logical inductor over any theory you want (PA, ZFC, 2nd order arithmetic), by fixing some efficiently computable function from bits to sentences in the language of your theory, conditioning the universal inductor (which is a probability distribution over infinite bitstrings) on the bits which correspond to proven theorems, and reading out the probability of other bits/sentences from the resulting conditional distribution. This trick works by Theorem 4.7.2 in the logical induction paper, "Closure Under Conditioning", which shows that conditioning the probabilities of a logical inductor on a sequence of non-inconsistent sentences, yields a logical inductor over a deductive process where all the conditionals are true.
Also, since they are a probability distribution over infinite bitstrings, it makes sense to think about them as having a probability measure over worlds (assignments of statements to true or false, for all statements) at all finite stages, instead of just in the limit.
Note that a Universal Inductor corresponds to a Logical Inductor, but the associated Logical Inductor will not have finite support, and so will be different from the one constructed in the paper. Never the less, Universal Inductors can be shown to exist using a similar construction.
This post will give that construction. To begin with, a Universal Inductor must fulfill the following two properties:
First, it must be a distribution over infinite bitstrings, such that Pn(σ) is computable for all n and all σ which are finite bitstrings. This gives the probability that an infinite bitstring starts with σ as a prefix.
Second, the theory is one where the nth atomic statement is of the form "the nth bit in this infinite bitstring is a 1", and Pn induces a function from these statements to probabilities, and the sequence of probability assignments must form a logical inductor over the empty deductive process. (ie, the inductor never sees any evidence of the form "this bit is a 1", it just runs forever without getting any feedback.)
To begin with, the supertrader construction from Section 5 of the logical induction paper is the exact same. Traders look at the prices of boolean combinations of atomic statements, and use them in continuous functions to buy or sell shares in boolean combinations of atomic statements.
The interesting part is the construction of the space that we'll be finding a fixed-point in. At timestep n, there is a most-distant bit that has ever appeared in a boolean combination of bits that a trader has bought/sold shares in, or looked at the price of. This is bit f(n). If we assign prices to all bitstrings of length f(n), then the probability of any finite bitstring that is longer can be given by just using the uniform distribution on bits after that point. This corresponds to assigning 50/50 probability to all statements which are too large to have thought about them yet. Therefore, our space of interest is the 2f(n)−1 dimensional simplex of probability distributions over all bitstrings of length f(n).
Given a point in this space, it is possible to read out the probability of any particular boolean combination of bits by just summing up the probability on all f(n)-length bitstrings that fit that constraint, so we can determine the prices that the supertrader sees.
We can also assign all bitstrings but one to a basis vector for the space, by letting the basis vector for a bitstring be the vector pointing to the corresponding vertex of the simplex from its center. A purchase of one share in a boolean combination corresponds to the vector comprised of the sum of basis vectors that correspond to the bitstrings fulfilling the conditions of the boolean. Note that a purchase of the one bitstring we left out can be re-expressed as a purchase of 1 dollar and selling a share of all other bitstrings.
As a simple case of this re-expression, when f(n)=2, P(00)=1−P(01)−P(10)−P(11) (because it has to be a probability distribution), so the price of the purchase is the same. And as for the purchase, both purchases have the feature that they are worth 1 dollar if the world is 00 and 0 dollars if the world is something different.
Therefore, given a point →x in the simplex, the net purchase and selling of a bunch of different boolean combinations of bits can be broken down into a whole bunch of vectors, which sum up to give a net trade vector →t, and finding the point in the simplex that's closest to →x+→t is the output of the continuous function that we can then find the fixed-point of.
Now, given a fixed-point in the interior of the simplex, →t=0, so there is no net trade. Given a fixed-point on the boundary of the simplex, →t can be interpreted as being composed entirely of selling shares with a price of 0, which obviously has 0 or negative value, although this is quite nontrivial to show. Once this is proved, it then immediately follows that this process described above is a Universal Inductor.
From here on, we will simply take care of this last theorem to be shown.
Theorem 1:
For all price vectors →x′ on the boundary of the simplex that are a fixed-point, the vector →v representing the net trade can be interpreted as being composed entirely of 0's for all components in which →x′ has a nonzero entry, and nonpositive for all components in which →x′ has a 0 entry.
First, some notation will be laid out.
k:=2f(n)−1, and it is the dimension of the space the simplex is in. →x denotes the vector of length k that is the fixed-point, and →x′ denotes the unique "canonical interpretation" of this vector as a vector of length k+1 with nonnegative coordinates that sum to 1, which gives the probabilities of the various bitstrings. Similarly, →t denotes the vector of length k which corresponds to the net trade. Given a constant c, →c will denote a vector with all coordinates being c, with the length clear from context. Given a vector →z and coordinate a, with za being the value of the a'th coordinate of →z, →za is the vector that is 0 in all coordinates except for a, and za at the a'th coordinate.
To begin, note that, given →t, there are multiple possible vectors →t′ of length k+1 which give the net purchase of shares. As an example of this, when k=1, [0,1] and [−1,0] both correspond to the same trade, because buying a share 0f σ=1 is equivalent to selling a share of σ=0. We will show that →t has an interpretation as a vector →t′ which is 0 everywhere →x′ is positive, and nonpositive everywhere →x′ is 0, because this corresponds to the net trade being interpretable as buying no shares, and only selling shares of bitstrings with a price of 0, which cannot lead to any gain no matter which bitstring is the true one.
Now, we will fix our basis vectors for the space. Because →x is on the boundary of the simplex, →x′ must have at least one 0 entry. Fix that vertex that corresponds to that bitstring as the origin of the coordinate system, and let the basis be comprised of the set of unit vectors that point from the center of the simplex to the vertices that correspond to all the other bitstrings. This spans the space that the simplex is embedded in. Annoyingly, this is not an orthonormal basis, so computing the dot product will be more complicated. The dot product between any two different basis vectors is −1k+1 (hat tip to Vanessa from MIRIxDiscord)
We can start by asking the question "In this basis, what condition on a vector →z corresponds to being inside the simplex?" The condition is that there exist a c∈[0,1] s.t. [0,→z]+→c has all entries in [0,1] and the entries sum up to 1. Note that for →x specifically, by the way we have defined the basis, c=0.
Also, the coordinates for →x can be broken down into coordinates where →x has 0 entries, and coordinates where →x has positive entries. Therefore, given an arbitrary vector →z, it can be expressed as [→z0,→z+], where →z0 is the vector of coordinates where →xis 0, and →x+ is the vector of coordinates where →x is positive.
The proof strategy that will be used is dividing into cases, and showing that for all cases besides the ones that prove the theorem, there is an "allowable perturbation vector" →ϵ s.t. →x+→ϵ lies in the simplex, and →x+→t is closer to →x+→ϵ than it is to →x. This implies that →x is not a fixed-point, because it isn't the point closest to →x+→t, but →x is a fixed-point, so we have a contradiction. Note that →x+→t being closer to →x+→ϵ than to →x is equivalent to ||→t||>||→t−→ϵ||, which can be rewritten as ⟨→t,→t⟩>⟨→t,→t⟩−2⟨→t,→ϵ⟩+⟨→ϵ,→ϵ⟩ which can be rewritten as 2⟨→t,→ϵ⟩>⟨→ϵ,→ϵ⟩. This last statement will be the proof target in the following cases.
Case 1:There is some pair of coordinates a, b, s.t xb>0, and ta>tb.
Let →ϵ be s.t. ϵa=ϵ, ϵb=−ϵ, and all other coordinates are 0. Note that since xa<1 (because xb>0 and →x adds up to 1), and →ϵ adds up to 0, then for sufficiently small ϵ, [0,→x+→ϵ] has all entries lie in [0,1] and sums up to 1. Then c can be taken as 0, to yield that →x+→ϵ lies in the simplex.
Define →t∗ as →t=→ta+→tb+→t∗. Note that →t∗ is 0 at coordinates a and b.
Rewriting ⟨→t∗,→ϵa⟩+⟨→t∗,→ϵb⟩ as ∑i≠a,b(⟨→ti,→ϵa⟩+⟨→ti,→ϵb⟩) , and using the fact that the dot product between any two different basis vectors of our space is −1k+1, ⟨→ti,→ϵa⟩+⟨→ti,→ϵb⟩=−1k+1(ϵti−ϵti)=0, so ⟨→t∗,→ϵa⟩+⟨→t∗,→ϵb⟩=0.
=2ϵ(1+1k+1)(ta−tb) and because ta>tb, 2⟨→t,→ϵ⟩=cϵ for some positive c.
A similar analysis applies to show ⟨→ϵ,→ϵ⟩=4ϵ2(1+1k+1)=dϵ2 for some positive d, and for sufficiently small ϵ, we get our desired result that 2⟨→t,→ϵ⟩>⟨→ϵ,→ϵ⟩.
Now, the elimination of this case shows that →t+ must have all entries equal some constant c, while →t0 must have all entries ≤c if it is nonempty. This produces three more exhaustive cases.
Case 2:→t+=→c, cis positive.
In this case, note that a purchase of all shares but one can be reinterpreted as buying 0 of all shares but one, and selling the remaining share. Therefore, this trade is equivalent to selling c shares in the probability-zero bitstring that we took as the origin, buying 0 of all shares with positive probability, and selling a non-negative amount of all shares with 0 probability (because →t0 has all entries ≤c). Theorem 1 follows.
Case 3:→t+=→c, cis0.
This case immediately proves Theorem 1, because →t+=0, and →t0 is 0 or negative on all entries.
Case 4:→t+=→c, cis negative.
If we can show that this case is impossible, we will be done. Let a be some coordinate where →x is positive.
Let →ϵ be s.t. →ϵa=−2ϵ, and all other coordinates are −ϵ. Let c=ϵ. [0,→x+→ϵ]+→c has all terms lie in [0,1] for sufficiently small ϵ, because the −ϵ is canceled out when →c is added, and the −2ϵ is taken out of a positive term. Because →c has k+1 entries, →c sums up to (k+1)ϵ. →x sums up to 1, and →ϵ sums up to −(k+1)ϵ, so the resulting vector sums up to 1, and →x+→ϵ lies in the simplex.
For some positive constant d. Therefore, for sufficiently small ϵ, 2⟨→t,→ϵ⟩>⟨→ϵ,→ϵ⟩ and Case 4 is impossible, and the theorem follows because only Case 2 and 3 are left.
[Attention Conservation Notice: This just recaps an old result and patches a hole in it, it doesn't contain substantially new ideas.]
Universal Inductors can be thought of as logical inductors over bitstrings, which are notable because they can act as a logical inductor over any theory you want (PA, ZFC, 2nd order arithmetic), by fixing some efficiently computable function from bits to sentences in the language of your theory, conditioning the universal inductor (which is a probability distribution over infinite bitstrings) on the bits which correspond to proven theorems, and reading out the probability of other bits/sentences from the resulting conditional distribution. This trick works by Theorem 4.7.2 in the logical induction paper, "Closure Under Conditioning", which shows that conditioning the probabilities of a logical inductor on a sequence of non-inconsistent sentences, yields a logical inductor over a deductive process where all the conditionals are true.
Also, since they are a probability distribution over infinite bitstrings, it makes sense to think about them as having a probability measure over worlds (assignments of statements to true or false, for all statements) at all finite stages, instead of just in the limit.
However, in Scott's old post about universal inductors, their construction was never described.
This post will give that construction. To begin with, a Universal Inductor must fulfill the following two properties:
First, it must be a distribution over infinite bitstrings, such that Pn(σ) is computable for all n and all σ which are finite bitstrings. This gives the probability that an infinite bitstring starts with σ as a prefix.
Second, the theory is one where the nth atomic statement is of the form "the nth bit in this infinite bitstring is a 1", and Pn induces a function from these statements to probabilities, and the sequence of probability assignments must form a logical inductor over the empty deductive process. (ie, the inductor never sees any evidence of the form "this bit is a 1", it just runs forever without getting any feedback.)
To begin with, the supertrader construction from Section 5 of the logical induction paper is the exact same. Traders look at the prices of boolean combinations of atomic statements, and use them in continuous functions to buy or sell shares in boolean combinations of atomic statements.
The interesting part is the construction of the space that we'll be finding a fixed-point in. At timestep n, there is a most-distant bit that has ever appeared in a boolean combination of bits that a trader has bought/sold shares in, or looked at the price of. This is bit f(n). If we assign prices to all bitstrings of length f(n), then the probability of any finite bitstring that is longer can be given by just using the uniform distribution on bits after that point. This corresponds to assigning 50/50 probability to all statements which are too large to have thought about them yet. Therefore, our space of interest is the 2f(n)−1 dimensional simplex of probability distributions over all bitstrings of length f(n).
Given a point in this space, it is possible to read out the probability of any particular boolean combination of bits by just summing up the probability on all f(n)-length bitstrings that fit that constraint, so we can determine the prices that the supertrader sees.
We can also assign all bitstrings but one to a basis vector for the space, by letting the basis vector for a bitstring be the vector pointing to the corresponding vertex of the simplex from its center. A purchase of one share in a boolean combination corresponds to the vector comprised of the sum of basis vectors that correspond to the bitstrings fulfilling the conditions of the boolean. Note that a purchase of the one bitstring we left out can be re-expressed as a purchase of 1 dollar and selling a share of all other bitstrings.
As a simple case of this re-expression, when f(n)=2, P(00)=1−P(01)−P(10)−P(11) (because it has to be a probability distribution), so the price of the purchase is the same. And as for the purchase, both purchases have the feature that they are worth 1 dollar if the world is 00 and 0 dollars if the world is something different.
Therefore, given a point →x in the simplex, the net purchase and selling of a bunch of different boolean combinations of bits can be broken down into a whole bunch of vectors, which sum up to give a net trade vector →t, and finding the point in the simplex that's closest to →x+→t is the output of the continuous function that we can then find the fixed-point of.
Now, given a fixed-point in the interior of the simplex, →t=0, so there is no net trade. Given a fixed-point on the boundary of the simplex, →t can be interpreted as being composed entirely of selling shares with a price of 0, which obviously has 0 or negative value, although this is quite nontrivial to show. Once this is proved, it then immediately follows that this process described above is a Universal Inductor.
From here on, we will simply take care of this last theorem to be shown.
Theorem 1:
For all price vectors →x′ on the boundary of the simplex that are a fixed-point, the vector →v representing the net trade can be interpreted as being composed entirely of 0's for all components in which →x′ has a nonzero entry, and nonpositive for all components in which →x′ has a 0 entry.
First, some notation will be laid out.
k:=2f(n)−1, and it is the dimension of the space the simplex is in. →x denotes the vector of length k that is the fixed-point, and →x′ denotes the unique "canonical interpretation" of this vector as a vector of length k+1 with nonnegative coordinates that sum to 1, which gives the probabilities of the various bitstrings. Similarly, →t denotes the vector of length k which corresponds to the net trade. Given a constant c, →c will denote a vector with all coordinates being c, with the length clear from context. Given a vector →z and coordinate a, with za being the value of the a'th coordinate of →z, →za is the vector that is 0 in all coordinates except for a, and za at the a'th coordinate.
To begin, note that, given →t, there are multiple possible vectors →t′ of length k+1 which give the net purchase of shares. As an example of this, when k=1, [0,1] and [−1,0] both correspond to the same trade, because buying a share 0f σ=1 is equivalent to selling a share of σ=0. We will show that →t has an interpretation as a vector →t′ which is 0 everywhere →x′ is positive, and nonpositive everywhere →x′ is 0, because this corresponds to the net trade being interpretable as buying no shares, and only selling shares of bitstrings with a price of 0, which cannot lead to any gain no matter which bitstring is the true one.
Now, we will fix our basis vectors for the space. Because →x is on the boundary of the simplex, →x′ must have at least one 0 entry. Fix that vertex that corresponds to that bitstring as the origin of the coordinate system, and let the basis be comprised of the set of unit vectors that point from the center of the simplex to the vertices that correspond to all the other bitstrings. This spans the space that the simplex is embedded in. Annoyingly, this is not an orthonormal basis, so computing the dot product will be more complicated. The dot product between any two different basis vectors is −1k+1 (hat tip to Vanessa from MIRIxDiscord)
We can start by asking the question "In this basis, what condition on a vector →z corresponds to being inside the simplex?" The condition is that there exist a c∈[0,1] s.t. [0,→z]+→c has all entries in [0,1] and the entries sum up to 1. Note that for →x specifically, by the way we have defined the basis, c=0.
Also, the coordinates for →x can be broken down into coordinates where →x has 0 entries, and coordinates where →x has positive entries. Therefore, given an arbitrary vector →z, it can be expressed as [→z0,→z+], where →z0 is the vector of coordinates where →xis 0, and →x+ is the vector of coordinates where →x is positive.
The proof strategy that will be used is dividing into cases, and showing that for all cases besides the ones that prove the theorem, there is an "allowable perturbation vector" →ϵ s.t. →x+→ϵ lies in the simplex, and →x+→t is closer to →x+→ϵ than it is to →x. This implies that →x is not a fixed-point, because it isn't the point closest to →x+→t, but →x is a fixed-point, so we have a contradiction. Note that →x+→t being closer to →x+→ϵ than to →x is equivalent to ||→t||>||→t−→ϵ||, which can be rewritten as ⟨→t,→t⟩>⟨→t,→t⟩−2⟨→t,→ϵ⟩+⟨→ϵ,→ϵ⟩ which can be rewritten as 2⟨→t,→ϵ⟩>⟨→ϵ,→ϵ⟩. This last statement will be the proof target in the following cases.
Case 1: There is some pair of coordinates a, b, s.t xb>0, and ta>tb.
Let →ϵ be s.t. ϵa=ϵ, ϵb=−ϵ, and all other coordinates are 0. Note that since xa<1 (because xb>0 and →x adds up to 1), and →ϵ adds up to 0, then for sufficiently small ϵ, [0,→x+→ϵ] has all entries lie in [0,1] and sums up to 1. Then c can be taken as 0, to yield that →x+→ϵ lies in the simplex.
Define →t∗ as →t=→ta+→tb+→t∗. Note that →t∗ is 0 at coordinates a and b.
2⟨→t,→ϵ⟩=2(⟨→ta,→ϵa⟩+⟨→ta,→ϵb⟩+⟨→tb,→ϵa⟩+⟨→tb,→ϵb⟩+⟨→t∗,→ϵa⟩+⟨→t∗,→ϵb⟩)
Rewriting ⟨→t∗,→ϵa⟩+⟨→t∗,→ϵb⟩ as ∑i≠a,b(⟨→ti,→ϵa⟩+⟨→ti,→ϵb⟩) , and using the fact that the dot product between any two different basis vectors of our space is −1k+1, ⟨→ti,→ϵa⟩+⟨→ti,→ϵb⟩=−1k+1(ϵti−ϵti)=0, so ⟨→t∗,→ϵa⟩+⟨→t∗,→ϵb⟩=0.
Now, 2(⟨→ta,→ϵa⟩+⟨→ta,→ϵb⟩+⟨→tb,→ϵa⟩+⟨→tb,→ϵb⟩)=2(ϵta−−1k+1ϵta+−1k+1ϵtb−ϵtb)
=2ϵ(1+1k+1)(ta−tb) and because ta>tb, 2⟨→t,→ϵ⟩=cϵ for some positive c.
A similar analysis applies to show ⟨→ϵ,→ϵ⟩=4ϵ2(1+1k+1)=dϵ2 for some positive d, and for sufficiently small ϵ, we get our desired result that 2⟨→t,→ϵ⟩>⟨→ϵ,→ϵ⟩.
Now, the elimination of this case shows that →t+ must have all entries equal some constant c, while →t0 must have all entries ≤c if it is nonempty. This produces three more exhaustive cases.
Case 2: →t+=→c, c is positive.
In this case, note that a purchase of all shares but one can be reinterpreted as buying 0 of all shares but one, and selling the remaining share. Therefore, this trade is equivalent to selling c shares in the probability-zero bitstring that we took as the origin, buying 0 of all shares with positive probability, and selling a non-negative amount of all shares with 0 probability (because →t0 has all entries ≤c). Theorem 1 follows.
Case 3: →t+=→c, c is 0.
This case immediately proves Theorem 1, because →t+=0, and →t0 is 0 or negative on all entries.
Case 4: →t+=→c, c is negative.
If we can show that this case is impossible, we will be done. Let a be some coordinate where →x is positive.
Let →ϵ be s.t. →ϵa=−2ϵ, and all other coordinates are −ϵ. Let c=ϵ. [0,→x+→ϵ]+→c has all terms lie in [0,1] for sufficiently small ϵ, because the −ϵ is canceled out when →c is added, and the −2ϵ is taken out of a positive term. Because →c has k+1 entries, →c sums up to (k+1)ϵ. →x sums up to 1, and →ϵ sums up to −(k+1)ϵ, so the resulting vector sums up to 1, and →x+→ϵ lies in the simplex.
2⟨→t,→ϵ⟩=2(⟨→ta,→ϵa⟩+⟨→ta,→ϵ∗⟩+⟨→t∗,→ϵa⟩+⟨→t∗,→ϵ∗⟩)
Now we will break down the dot products.
⟨→t∗,→ϵ∗⟩=∑i,j≠a⟨→ti,→ϵj⟩=∑i≠a(⟨→ti,→ϵi⟩+∑j≠i,a⟨→ti,→ϵj⟩)
=∑i≠a(−ϵvi+∑j≠i,a(−ϵvi−1k+1))=−ϵ∑i≠a(vi−k−2k+1vi)=−ϵ(1−k−2k+1)∑i≠avi
=−3ϵk+1∑i≠avi
And for the next pair,
⟨→ta,→ϵ∗⟩+⟨→t∗,→ϵa⟩=∑i≠a⟨→ta,→ϵi⟩+∑i≠a⟨→ti,→ϵa⟩=∑i≠a(−ϵ−1k+1ta)+∑i≠a(−2ϵ−1k+1ti)
=ϵk+1(k−1)ta+2ϵk+1∑i≠ati
Note that the second term combines with the term from the first dot product we looked at to yield the following equation
⟨→ta,→ϵ∗⟩+⟨→t∗,→ϵa⟩+⟨→t∗,→ϵ∗⟩=ϵk+1(k−1)ta−ϵk+1∑i≠ati
Finally, because ⟨→ta,→ϵa⟩=−2ϵva, by grouping terms and factoring out ϵk+1, we get
2⟨→t,→ϵ⟩=2ϵk+1(−2(k+1)ta+(k−1)ta−∑i≠ati)=2ϵk+1(−(k+3)ta−∑i≠ati)
and, because all coordinates in →t are negative, this equals cϵ for some positive constant c. By the same proof path,
⟨→ϵ,→ϵ⟩=ϵk+1(−(k+3)(−2ϵ)−(k−1)(−ϵ))=ϵ2k+1(3k+5)=dϵ2
For some positive constant d. Therefore, for sufficiently small ϵ, 2⟨→t,→ϵ⟩>⟨→ϵ,→ϵ⟩ and Case 4 is impossible, and the theorem follows because only Case 2 and 3 are left.