Intelligent Agent Foundations Forumsign up / log in

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.

reply

NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

[Note: This comment is three
by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

RSS

Privacy & Terms