Stationary algorithmic probability

It looks like Theorem 1 can be improved slightly, by dropping the "only if" condition on $p_{CD}>0$. We can then code up something like Kolmogorov complexity by adding a probability $\frac{1}{2}$ transition from every site to our chosen UTM.

If you only want the weaker statement that there is no stationary distribution, it looks like there's a cheaper argument: Since $\Phi$ is aperiodic and irreducible the hypothetical stationary distribution $\pi$ is unique. $\Phi$ is closed under the action of $\Delta$, and (2) implies that for any $g\in \Delta$, the map ${\Gamma }_g$ is an automorphism of the Markov chain. If the (infinite) transition matrix is $T$, then ${\Gamma }_g$ can be considered as a permutation matrix with (abusing notation) ${\Gamma }_g^{-1}T{\Gamma }_g=T$. Then $T{\Gamma }_g\pi ={\Gamma }_g\pi$ and so ${\Gamma }_g\pi =\pi$ by uniqueness. So $\pi$ is constant on orbits of ${\Gamma }_{\Delta }$, which are all countably infinite. Hence $\pi$ is everywhere $0$, a contradiction.

The above still holds if (2) is restricted to only hold for a group $G<\Delta$ such that every orbit under ${\Gamma }_G$ is infinite.

I think the above argument shows why (2) is too strong; we shouldn't expect the world to look the same if you pick a "wrong" (ie. complicated) UTM to start off with. Weakening (2) might mean saying something like asserting only $p_{CD}=\sum \mu \left(\Gamma \right)p_{\Gamma \left(C\right)\Gamma \left(D\right)}$. To do this, we might define the measures $\mu$ and $p$ together (ie. finding a fixed point of a map from pairs $(p,\mu )$ to $(p^{\prime },{\mu }^{\prime })$). In such a model, $\mu$ constraints the transition probabilities, $p^{\prime }$ is stationary; it's not clear how one might formalise a derivation of ${\mu }^{\prime }$ from $p^{\prime }$ but it seems plausible that there is a canonical way to do it.

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".

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

This is a follow-up note to a nice paper of Markus Mueller on the possibility of a machine-invariant notion of Kolmogorov complexity, available here: http://www.sciencedirect.com/science/article/pii/S0304397509006550

Context: At this weekend's MIRI workshop on logical uncertainty, we were talking about Markus Mueller's paper on priors over Turing machines and bitstrings (as those seem analogous to priors over logical statements).

Mueller's original result examined a directed graph structure over prefix computers, where an edge is given by a prefix that causes one computer to simulate another. This gave rise to a Markov chain structure, but Mueller showed in two different ways that this Markov chain was not positive recurrent, and thus that it would not give rise to a non-arbitrary prior.

However, I noted that the Markov chain structure was set up to punish computers that were difficult to simulate, but not to punish computers that were bad at simulating others. Some natural ways to modify the transition probabilities defeated Mueller's more direct counterexample.

However, in this draft Jacob and Janos showed that no stationary transition matrix (with nonzero coefficients) on that digraph of universal prefix computers could be positive recurrent, or even null recurrent (going beyond Mueller's result).