Intelligent Agent Foundations Forumsign up / log in
by Jonathan Lee 1106 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 LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

I found an improved version
by Alex Appel on A Loophole for Self-Applicative Soundness | 0 likes

I misunderstood your
by Sam Eisenstat on A Loophole for Self-Applicative Soundness | 0 likes

Caught a flaw with this
by Alex Appel on A Loophole for Self-Applicative Soundness | 0 likes

As you say, this isn't a
by Sam Eisenstat on A Loophole for Self-Applicative Soundness | 1 like

Note: I currently think that
by Jessica Taylor on Predicting HCH using expert advice | 0 likes

Counterfactual mugging
by Jessica Taylor on Doubts about Updatelessness | 0 likes

What do you mean by "in full
by David Krueger on Doubts about Updatelessness | 0 likes

It seems relatively plausible
by Paul Christiano on Maximally efficient agents will probably have an a... | 1 like

I think that in that case,
by Alex Appel on Smoking Lesion Steelman | 1 like

Two minor comments. First,
by Sam Eisenstat on No Constant Distribution Can be a Logical Inductor | 1 like

A: While that is a really
by Alex Appel on Musings on Exploration | 0 likes

> The true reason to do
by Jessica Taylor on Musings on Exploration | 0 likes

A few comments. Traps are
by Vadim Kosoy on Musings on Exploration | 1 like

I'm not convinced exploration
by Abram Demski on Musings on Exploration | 0 likes

Update: This isn't really an
by Alex Appel on A Difficulty With Density-Zero Exploration | 0 likes

RSS

Privacy & Terms