Ah, I think I can stymy $M$ with 2 nonconstant advisors. Namely, let $A_1\left(n\right)=\frac{1}{2}-\frac{1}{n+3}$ and $A_2\left(n\right)=\frac{1}{2}+\frac{1}{n+3}$. We (setting up an adversarial $E$) precommit to setting $E\left(n\right)=0$ if $p\left(n\right)\ge A_2\left(n\right)$ and $E\left(n\right)=1$ if $p\left(n\right)\le A_1\left(n\right)$; now we can assume that $M$ always chooses $p\left(n\right)\in \left[A_1\right(n),A_2(n\left)\right]$, since this is better for $M$.

Now define $b_i^{\prime }\left(j\right)=\left|A_i\right(j)+E(j)-1|-\left|p\right(j)+E(j)-1|$ and $b_i\left(n\right)={\sum }_{j<n}{b}_i^{\prime }\left(j\right)$. Note that if we also define ${\mathrm{bad}}_i\left(n\right)={\sum }_{j<n}(\log \left|A_i\right(j)+E(j)-1|-\log \left|p\right(j)+E(j)-1|)$ then ${\sum }_{j<n}\left|2b_i\right(j)-{\mathrm{bad}}_i(j\left)\right|\le {\sum }_{j<n}\left(2A_1\right(j)-1-\log (2A_1\left(j\right)\left)\right))={\sum }_{j<n}O\left({(\frac{1}{2}-A_1(j\left)\right)}^2\right)$ is bounded; therefore if we can force $b_1\left(n\right)\to \infty$ or $b_2\left(n\right)\to \infty$ then we win.

Let's reparametrize by writing $\delta \left(n\right)=A_2\left(n\right)-A_1\left(n\right)=\frac{2}{n+3}$ and $q\left(n\right)=\frac{p\left(n\right)-A_1\left(n\right)}{\delta \left(n\right)}$, so that $b_i^{\prime }\left(j\right)=\delta \left(j\right)(|i-2+E(j\left)\right|-\left|q\right(j)-1+E(j\left)\right|)$.

Now, similarly to how $M$ worked for constant advisors, let's look at the problem in rounds: let $s_0=0$, and $s_n=\lfloor \exp (s_{n-1}-1)\rfloor +1$ for $n>0$. When determining $E\left(s_{n-1}\right),\dots ,E(s_n-1)$, we can look at $p\left(s_{n-1}\right),\dots ,p(s_n-1)$. Let $t_n=\lfloor b_2\left(s_n\right)-\frac{1}{n}\rfloor$. Let's set $E\left(s_{n-1}\right),\dots ,E(s_n-1)$ to 1 if ${\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)\ge 1$; otherwise we'll do something more complicated, but maintain the constraint that $b_2\left(s_n\right)\ge b_2\left(s_{n-1}\right)-\frac{1}{n(n-1)}\ge t_{n-1}+\frac{1}{n}$: this guarantees that $t_n$ is nondecreasing and that ${liminf}_{j\to \infty }{b}_2\left(j\right)\ge {lim}_{n\to \infty }{t}_n$.

If $t_n\to \infty$ then $b_2\left(n\right)\to \infty$ and we win. Otherwise, let $t={lim}_{n\to \infty }{t}_n$, and consider $n$ such that $t_{n-1}=t$.

We have ${\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)<1$. Let $J\subseteq \{s_{n-1},\dots ,s_n-1\}$ be a set of indices with $q\left(j\right)\ge q\left(j^{\prime }\right)$ for all $j\in J,j^{\prime }\notin J$, that is maximal under the constraint that ${\sum }_{j\in J}\delta \left(j\right)(1-q(j\left)\right)\le \frac{1}{n(n-1)}$; thus we will still have ${\sum }_{j\in J}\delta \left(j\right)(1-q(j\left)\right)\ge \frac{1}{n(n-1)}-\delta \left(s_{n-1}\right)$. We shall set $E\left(j\right)=0$ for all $j\in J$.

By the definition of $J$: $$\begin{array}{cc}\sum _{j\in J}{b}_1^{\prime }\left(j\right)& =\sum _{j\in J}\delta \left(j\right)q\left(j\right)\\ & \ge \sum _{j\in J}\delta \left(j\right)(1-q(j\left)\right)\frac{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)q\left(j\right)}{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)(1-q(j\left)\right)}\\ & \ge (\frac{1}{n(n-1)}-\delta (s_{n-1}\left)\right)\frac{{\sum }_{j=s_{n-1}}^{s_n-1}\delta \left(j\right)-1}{1}\\ & \ge (\frac{1}{n(n-1)}-\delta (s_{n-1}\left)\right)(2\log \left(\frac{s_n+3}{s_{n-1}+3}\right)-1)\\ & \ge 2\text{if}n\gg 0\end{array}$$

For $j^{\prime }\notin J$, we'll proceed iteratively, greedily minimizing $\left|{\sum }_{j^{\prime }=s_{n-1}}^j{1}_{j^{\prime }\notin J}\left(b_1^{\prime }\right(j^{\prime }),b_2^{\prime }(j^{\prime }\left)\right)\right|$. Then: $$\begin{array}{cc}\underset{s_{n-1}\le j<s_n}{min}\sum _{j^{\prime }=s_{n-1}}^j{1}_{j^{\prime }\notin J}{b}_1^{\prime }\left(j^{\prime }\right)& \ge -\sqrt{\sum _{j=s_{n-1}}^{s_n-1}\delta (j{)}^2}\\ & =-2\sqrt{\sum _{j=s_{n-1}+3}^{s_n-2}\frac{1}{j^2}}\\ & \ge -2\sqrt{\sum _{j=s_{n-1}+3}^{s_n-2}(\frac{1}{j-1}-\frac{1}{j})}\\ & \ge -\frac{2}{\sqrt{s_{n-1}+2}}\\ & \ge -1\text{if}n\gg 0\end{array}$$

Keeping this constraint, we can flip (or not flip) all the $E\left(j^{\prime }\right)$s for $j^{\prime }\notin J$ so that ${\sum }_{j^{\prime }=s_{n-1}}^{s_n-1}{1}_{j^{\prime }\notin J}{b}_2^{\prime }\left(j^{\prime }\right)>0$. Then, we have $b_2\left(s_n\right)\ge b_2\left(s_{n-1}\right)-\frac{1}{n(n-1)}$, $b_1\left(s_n\right)-b_1\left(s_{n-1}\right)={\sum }_{j=s_{n-1}}^{s_n}(1_{j\in J}+1_{j\notin J})b_1^{\prime }\left(j\right)\ge 2-1=1$ if $n\gg 0$, and for $s_{n-1}\le j\le s_n$, $b_1\left(j\right)\ge b_1\left(s_{n-1}\right)+{\sum }_{j^{\prime }=s_{n-1}}^{j-1}{1}_{j^{\prime }\notin J}{b}_1^{\prime }\left(j^{\prime }\right)\ge b_1\left(s_{n-1}\right)-1$ if $n\gg 0$.

Therefore, $b_1\left(j\right)\to \infty$, so we win.

I don't yet know whether I can extend it to two nonconstant advisors, but I do know I can extend it to a countably infinite number of constant-prediction advisors. Let $(P_i{)}_{i=0,\dots }$ be an enumeration of their predictions that contains each one an infinite number of times. Then:

def M(p, E, P):
    prev, this, next = 0, 0, 1
    def bad(i):
        return sum(log(abs((E[k] + P[i] - 1) /
                           (E[k] + p[k] - 1)))
                   for k in xrange(prev))
    for k in xrange(this, next): p[k] = 0.5
    prev, this, next = this, next, floor(exp(next - 1)) + 1

    for i in xrange(0, Inf):
        for k in xrange(this, next): p[k] = P[i]
        prev, this, next = this, next, floor(exp(next - 1)) + 1

bad(i) is now up to date through E[:this], not just E[:prev]

        bound = 2 * bad(i)
        for j in xrange(0, Inf):
            if P[j] == P[i]: continue
            flip = P[j] < P[i]
            p1, p2 = abs(P[i] - flip), abs(P[j] - flip)
            for k in xrange(this, next): p[k] = abs(p1 - flip)
            prev, this, next = this, next, floor(exp(next - 1)) + 1
            
            if bad(i) <= 0: break
            while bad(i) > 0 and bad(j) > 0:
                # won't let bad(i) surpass bound
                eps = (bound - bad(i)) / 2 / abs(1 - p1 - flip) / (next - this)

This is just for early iterations of the inner loop; in the limit, eps should be just enough for bad(i) to go halfway to bound if we let p = abs(p1 + eps - flip):

                while eps >= 1 - p1 or
                      bound <= bad(i) + (next - this) *
                        log((1 - p1) / (1 - p1 - eps)):
                    eps /= 2
                for k in xrange(this, next): p[k] = abs(p1 + eps - flip)
                prev, this, next = this, next, floor(exp(next - 1)) + 1

                for k in xrange(this, next): p[k] = abs(p1 - flip)
                # this is where the P[i] + d * eps affects bad(i)

Consider $q=\frac{\log (1-p1)-\log (1-p2)}{\log (1-p1)-\log (1-p2)+\log \left(p2\right)-\log \left(p1\right)}$. This $q$ is the probability between p1 and p2 such that if E[k] is chosen with probability $|q-flip|$ then that will have an equal impact on bad(i) and bad(j). Now consider some $q^{\prime }$ between p1 and $q$. Every iteration where $\mathrm{mean}\left(\left|E[prev:this]-flip\right|\right)\le q^{\prime }$ will decrease bad(j) by a positive quantity that's at least linear in this-prev, so (at least after the first few such iterations) this will exceed $prev\cdot -\log ({max}_{k:P_k\text{has been reached}}max(P_k,1-P_k\left)\right)>bad\left(j\right)$, so it will turn bad(j) negative. If this happens for all j then M cannot be bad for E. If it doesn't, then let's look at the first j where it doesn't. After a finite number of iterations, every iteration must have $\mathrm{mean}\left(\left|E[prev:this]-flip\right|\right)>q^{\prime }$. However, this will cause bad(i) to decrease by a positive quantity that's at least proportional to bound - bad(i); therefore, after a finite number of such iterations, we must reach $bad\left(i\right)<0$. So if M is bad for E then for each value of i we will eventually make $bad\left(i\right)<0$ and then move on to the next value of i. This implies M is not bad for E.

Emboldened by this, we can also consider the problem of building an $M$ that isn't outperformed by any constant advisor. However, this cannot be done, according to the following handwavy argument:

Let $q$ be some incompressible number, and let $E\left(i\right)\stackrel{iid}{\sim }\mathrm{Bern}\left(q\right)$. When computing $p\left(n\right)$, $M$ can't do appreciably better than Laplace's law of succession, which will give it standard error $\sqrt{\frac{q(1-q)}{\log \left(n\right)}}$, and relative badness $\sim \frac{q(1-q)}{\log \left(n\right)}(\frac{1}{q}+\frac{1}{1-q})=\frac{1}{\log \left(n\right)}$ (relative to the $q$-advisor) on average. For $i\le n$, and $n\gg 0$, the greatest deviation of the badness from the ${\sum }_{j=2}^i\frac{1}{\log \left(j\right)}\ge \frac{i-1}{\log \left(i\right)}$ trend is $\approx \sqrt{2n\log \log \left(n\right)q(1-q)}$ (according to the law of the iterated logarithm), which isn't enough to counteract the expected badness; therefore the badness will converge to infinity.

def M(p, E):
    p1, p2 = 1./3, 2./3
    prev, this, next = 0, 0, 1

bad1 and bad2 compute log-badnesses of M relative to p1 and p2, on E[:prev]; the goal of M is to ensure neither one goes to $\infty$. prev, this, next are set in such a way that M is permitted access to this when computing p[this:next].

    def bad(advisor):
        return lambda:
            sum(log(abs((E[i] + advisor(i) - 1) /
                        (E[i] + p[i] - 1)))
                for i in xrange(prev))
    bad1, bad2 = bad(lambda i: p1), bad(lambda i: p2)
    for i in xrange(this, next): p[i] = 0.5
    prev, this, next = this, next, floor(exp(next - 1)) + 1

    while True:
        for i in xrange(this, next): p[i] = p1
        prev, this, next = this, next, floor(exp(next - 1)) + 1

bad1() is now be up to date through E[:this], not just E[:prev]

        bound = 2 * bad1()
        while bad1() > 0:
            # won't let bad1() surpass bound
            eps = (bound - bad1()) / 2 / (1 - p1) / (next - this)

This is just for early iterations; in the limit, eps should be just enough for bad1 to go halfway to bound:

            while eps >= 1 - p1 or
              bound <= bad1() + (next - this) *
              log((1 - p1) / (1 - p1 - eps)):
                eps /= 2
            for i in xrange(this, next): p[i] = p1 + eps
            prev, this, next = this, next, floor(exp(next - 1)) + 1

            for i in xrange(this, next): p[i] = p1
            # this is where the p1 + eps affects bad1()
            prev, this, next = this, next, floor(exp(next - 1)) + 1

Now every iteration (after the first few) where $\mathrm{mean}\left(E[prev:this]\right)\le \frac{2}{5}$ will decrease bad2() by roughly at least $(this-prev)\left(\log \right(1-p1)-\log (1-p2)+\frac{2}{5}(\log \left(p1\right)-\log \left(p2\right)-\log (1-p1)+\log (1-p2)\left)\right)=(this-prev)\frac{1}{5}\log \left(2\right)\gg prev$, which is large enough to turn bad2() negative. Therefore, if M is bad for E, there can be only finitely many such iterations until the loop exits. However, every iteration where $\mathrm{mean}\left(E[prev:this]\right)\ge \frac{2}{5}$ will cause bound - bad1() to grow exponentially (by a factor of $\frac{11}{10}=1+\frac{1}{2}(-1+\frac{2}{5}\frac{1}{p1})$), so the loop will terminate.

Now we'll perform the same procedure for bad2():

        for i in xrange(this, next): p[i] = p2
        prev, this, next = this, next, floor(exp(next - 1)) + 1

        bound = 2 * bad2()
        while bad2() > 0:
            # won't let bad2() surpass bound
            eps = (bound - bad2()) / 2 / p2 / (next - this)
            while eps >= p2 or
              bound <= bad2() + (next - this) *
              log( p2 / (p2 - eps)):
                eps /= 2
            for i in xrange(this, next): p[i] = p2 - eps
            prev, this, next = this, next, floor(exp(next - 1)) + 1

            for i in xrange(this, next): p[i] = p2
            # this is where the p2 - eps affects bad2()
            prev, this, next = this, next, floor(exp(next - 1)) + 1

For the same reasons as the previous loop, this loop either stops with bad2() < 0 or runs forever with bad2() bounded and bad1 repeatedly falling back below 0.

Therefore, this algorithm either gets trapped in one of the inner while loops (and succeeds) or turns bad1() and bad2() negative, each an infinite number of times, and therefore succeeds.

These results are still a bit unsatisfying.

The first half constructs an invariant measure which is then shown to be unsatisfactory because UTMs can rank arbitrarily high while only being good at encoding variations of themselves. This is mostly the case because the chain is transient; if it was positive recurrent then the measure would be finite, and UTMs ranking high would have to be good at encoding (and being encoded by) the average UTM rather than just a select family of UTMs.

The second half looks at whether we can get better results (ie a probability measure) by restricting our attention to output-free "UTMs" (though I misspoke; these are not actually UTMs but rather universal semidecidable languages (we can call them USDLs)). It concludes that we can't if the measure will be continuous on the given digraph - however, this is an awkward notion of continuity: a low-complexity USDL whose behavior is tweaked very slightly but in a complex way may be very close in the given topology, but should have measure much lower than the starting USDL. So I consider this question unanswered.

There is a lot more to say about the perspective that isn't relaxed to continuous random variables. In particular, the problem of finding the maximum entropy joint distribution that agrees with particular pairwise distributions is closely related to Markov Random Fields and the Ising model. (The relaxation to continuous random variables is a Gaussian Markov Random Field.) It is easily seen that this maximum entropy joint distribution must have the form $\log Pr(1_{{\phi }_1},\dots ,1_{{\phi }_n})={\sum }_{i<j}{\theta }_{ij}{1}_{{\phi }_i\wedge {\phi }_j}+{\sum }_i{\theta }_i{1}_{{\phi }_i}-\log Z$ where $\log Z$ is the normalizing constant, or partition function. This is an appealing distribution to use, and easy to do conditioning on and to add new variables to. Computing relative entropy reduces to finding bivariate marginals and to computing $Z$, and computing marginals reduces to computing $Z$, which is intractable in general[^istrail], though easy if the Markov graph (ie the graph with edges $ij$ for ${\theta }_{i,j}\ne 0$) is a forest.

There have been many approaches to this problem (Wainwright and Jordan[^wainwright] is a good survey), but the main ways to extend the applicability from forests have been:

• decompose components of the graph as "junction trees", ie trees whose nodes are overlapping clusters of nodes from the original graph; this permits exact computation with cost exponential in the cluster-sizes, ie in the treewidth[^pearl]

• make use of clever combinatorial work coming out of statistical mechanics to do exact computation on "outerplanar" graphs, or on general graphs with cost exponential in the (outer-)graph genus[^schraudolph]

• find nodes such that conditioning on those nodes greatly simplifies the graph (eg makes it singly connected), and sum over their possible values explicitly (this has cost exponential in the number of nodes being conditioned on)

A newer class of models, called sum-product networks[^poon], generalizes these and other models by writing the total joint probability as a positive polynomial $1={\sum }_{x_1,\dots ,x_n=0}^{1}Pr(1_{{\phi }_1}=x_1,\dots ,1_{{\phi }_n}=x_n)1_{{\phi }_1}^{x_1}{1}_{{\overline{\phi }}_1}^{1-x_1}\dots 1_{{\phi }_n}^{x_n}{1}_{{\overline{\phi }}_n}^{1-x_n}$ in the variables $1_{{\phi }_1},1_{{\overline{\phi }}_1},\dots ,1_{{\phi }_n},1_{{\overline{\phi }}_n}$ and requiring only that this polynomial be simplifiable to an expression requiring a tractable number of additions and multiplications to evaluate. This allows easy computation of marginals, conditionals, and KL divergence, though it will likely be necessary to do some approximate simplification every so often (otherwise the complexity may accumulate, even with a fixed maximum number of sentences being considered at a time).

However, if we want to stay close to the context of the Non-Omniscience paper, we can do approximate calculations of the partition function on the complete graph - in particular, the Bethe partition function[^weller] has been widely used in practice, and while it's not logconvex like $Z$ is, it's often a better approximation to the partition function than well-known convex approximations such as TRW.

[^istrail]: Istrail, Sorin. "Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intractability for the partition function of the Ising model across non-planar surfaces." In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 87-96. ACM, 2000.

[^weller]: Weller, Adrian. "Bethe and Related Pairwise Entropy Approximations."

[^pearl]: Pearl, Judea. "Probabilistic reasoning in intelligent systems: Networks of plausible reasoning." (1988).

[^schraudolph]: Schraudolph, Nicol N., and Dmitry Kamenetsky. "Efficient Exact Inference in Planar Ising Models." arXiv preprint arXiv:0810.4401 (2008).

[^wainwright]: Wainwright, Martin J., and Michael I. Jordan. "Graphical models, exponential families, and variational inference." Foundations and Trends® in Machine Learning 1, no. 1-2 (2008): 1-305.

[^poon]: Poon, Hoifung, and Pedro Domingos. "Sum-product networks: A new deep architecture." In Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on, pp. 689-690. IEEE, 2011.

In order to understand what the measure $\mu$ that was constructed from $d$ will reward, here's the sort of machine that comes close to ${sup}_M\mu \left(M\right)=3$:

Let $M_0$ be an arbitrary UTM. Now consider the function $r\left(n\right)=n-2^{\lfloor \lg n\rfloor }$ (or, really, any function $r:N^{+}\to N^0$ with $r\left(n\right)<n$ that visits every nonnegative integer infinitely many times), and let $L=\{x\in \{0,1{\}}^{\ast }:|x|>2,x_{|x|-1}=x_{r(|x|-1)},x_{|x|-2}=x_{r(|x|-2)}\}$. (The indices here are zero-based.) Choose $x_0\in L$ such that $x_0$ has no proper prefix in $L$. Then, construct the UTM $M$ that does:

repeat:
    s := ""
    while s not in L:
        # if there is no next character, halt
        s := s + readchar()
    if s == x0:
        break
M0()

This $M$ will have $\mu \left(M\right)>3-2^{-|x_0|}+d(M_0,M)2^{-|x_0|-d(M_0,M)}$.

$M$ here is optimized for building up internal states (that are then UTMs that are efficiently encoded), while also being very easy to reset from these internal states; in other words being easy to "encode" from the UTMs it efficiently encodes, using at most 2 bits (an average of $\frac{1+\sqrt{5}}{2}$). This is somewhat interesting, but clearly doesn't capture the kind of computational expressivity we're primarily interested in.

Consider the function $a(M_1,M_2)=2^{-d(M_1,M_2)-d(M_2,M_1)}$ where $d(M_1,M_2)=min\left(|x|\right|x\in \{0,1{\}}^{\ast }:\forall y\in \{0,1{\}}^{\ast }:M_1\left(xy\right)=M_2\left(y\right)\text{unless neither of these halts})$. The reversible Markov chain with transition probabilities $p(M_1,M_2)=\frac{a(M_1,M_2)}{{\sum }_{M_2^{\prime }}a(M_1,M_2^{\prime })}$ has a bounded positive invariant measure $\mu \left(M\right)={\sum }_{M^{\prime }}a(M,M^{\prime })$. Of course, as the post showed, the total measure is infinite. Also, because the chain is reversible and transient, the invariant measure is far from unique - indeed, for any machine $M_0$, the measure $\mu \left(M\right)=p^{\left(0\right)}(M,M_0)+2{\sum }_{n=1}^{\infty }{p}^{\left(n\right)}(M,M_0)$ will be a bounded positive invariant measure.

It seems tempting (to me) to try to get a probability measure by modding out the output-permutations (that the post uses to show this isn't possible for the full set of UTMs). To this end, consider the set of UTMs that have no output. (These will be unaffected by the output-permutations.) We can try to use the induced sub-digraph on these to build a probability measure $\mu$. The measure of each UTM should be a function of the rooted edge-labeled digraph $G_M$ rooted at that UTM.

The most natural topology on rooted edge-labeled infinite digraphs is the one generated by the sets $\{G:G^{\prime }\text{is isomorphic to an induced rooted edge-labeled subgraph of G}\}$ where $G^{\prime }$ ranges over finite rooted edge-labeled digraphs - we could hope that $\mu$ is continuous according to this topology. Unfortunately, this can't work: if $\mu \left(M\right)>0$ then ${\mu }^{-1}\left(\right(\frac{1}{2}\mu \left(M\right),\infty \left)\right)$ must be open, and so it must contain some finite intersection of the generating sets; however, every such intersection that's nonempty (as this one is) contains infinitely many UTMs, so the total measure must be infinite as well.

Actually, on further thought, I think the best thing to use here is a log-bilinear distribution over the space of truth-assignments. For these, it is easy to efficiently compute exact normalizing constants, conditional distributions, marginal distributions, and KL divergences; there is no impedance mismatch. KL divergence minimization here is still a convex minimization (in the natural parametrization of the exponential family).

The only shortcoming is that 0 is not a probability, so it won't let you eg say that $Pr({\phi }_1\to {\phi }_2)=1$; but this can be remedied using a real or hyperreal approximation.

An easy way to get rid of the probabilities-outside-[0,1] problem in the continuous relaxation is to constrain the "conditional"/updated distribution to have $\mathrm{Var}\left(1_{{\phi }_i}\right|\dots )\le E\left(1_{{\phi }_i}\right|\dots )(1-E\left(1_{{\phi }_i}\right|\dots ))$ (which is a convex constraint; it's equivalent to $\mathrm{Var}\left(1_{{\phi }_i}\right|\dots )+{(E\left(1_{{\phi }_i}\right|\dots )-\frac{1}{2})}^2$), and then minimize KL-divergence accordingly.

The two obvious flaws are that the result of updating becomes ordering-dependent (though this may not be a problem in practice), and that the updated distribution will sometimes have $\mathrm{Var}\left(1_{{\phi }_i}\right|\dots )<E\left(1_{{\phi }_i}\right|\dots )(1-E\left(1_{{\phi }_i}\right|\dots ))$, and it's not clear how to interpret that.

It may still be possible to get a unique (up to scaling) invariant measure (with infinite sum) over the UTMs by invoking something like the Krein-Rutman theorem and applying it to the transition operator. I haven't yet verified that all the conditions hold.

This measure would then be an encoding-invariant way to compare UTMs' "intrinsic complexity" in the sense of "number of bits needed to simulate".