by Jonathan Lee 985 days ago | Jessica Taylor and Patrick LaVictoire like this | link | parent 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(\Gamma) p_{\Gamma(C)\Gamma(D)}$$. 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', \mu')$$). In such a model, $$\mu$$ constraints the transition probabilities, $$p'$$ is stationary; it’s not clear how one might formalise a derivation of $$\mu'$$ from $$p'$$ but it seems plausible that there is a canonical way to do it.

### NEW DISCUSSION POSTS

[Delegative Reinforcement
 by Vadim Kosoy on Stable Pointers to Value II: Environmental Goals | 1 like

Intermediate update: The
 by Alex Appel on Further Progress on a Bayesian Version of Logical ... | 0 likes

Since Briggs [1] shows that
 by 258 on In memoryless Cartesian environments, every UDT po... | 2 likes

This doesn't quite work. The
 by Nisan Stiennon on Logical counterfactuals and differential privacy | 0 likes

I at first didn't understand
 by Sam Eisenstat on An Untrollable Mathematician | 1 like

This is somewhat related to
 by Vadim Kosoy on The set of Logical Inductors is not Convex | 0 likes

This uses logical inductors
 by Abram Demski on The set of Logical Inductors is not Convex | 0 likes

Nice writeup. Is one-boxing
 by Tom Everitt on Smoking Lesion Steelman II | 0 likes

Hi Alex! The definition of
 by Vadim Kosoy on Delegative Inverse Reinforcement Learning | 0 likes

A summary that might be
 by Alex Appel on Delegative Inverse Reinforcement Learning | 1 like

I don't believe that
 by Alex Appel on Delegative Inverse Reinforcement Learning | 0 likes

This is exactly the sort of
 by Stuart Armstrong on Being legible to other agents by committing to usi... | 0 likes

When considering an embedder
 by Jack Gallagher on Where does ADT Go Wrong? | 0 likes

The differences between this
 by Abram Demski on Policy Selection Solves Most Problems | 1 like

Looking "at the very
 by Abram Demski on Policy Selection Solves Most Problems | 0 likes