Intelligent Agent Foundations Forumsign up / log in
by Janos Kramar 824 days ago | Patrick LaVictoire likes this | link | parent

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|\middle|x\in\{0,1\}^*:\forall y\in\{0,1\}^*: M_1(xy)=M_2(y)\mbox{ unless neither of these halts}\right)\). The reversible Markov chain with transition probabilities \(p(M_1,M_2)=\frac{a(M_1,M_2)}{\sum_{M'_2}a(M_1,M'_2)}\) has a bounded positive invariant measure \(\mu(M)=\sum_{M'}a(M,M')\). 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(M)=p^{(0)}(M,M_0)+2\sum_{n=1}^\infty p^{(n)}(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'\mbox{ is isomorphic to an induced rooted edge-labeled subgraph of G}\}\) where \(G'\) 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(M)>0\) then \(\mu^{-1}((\frac{1}{2}\mu(M),\infty))\) 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.



by Janos Kramar 824 days ago | Patrick LaVictoire likes this | link

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(M)=3\):

Let \(M_0\) be an arbitrary UTM. Now consider the function \(r(n)=n-2^{\lfloor \lg n \rfloor}\) (or, really, any function \(r:\mathbb{N}^+\rightarrow\mathbb{N}^0\) with \(r(n)<n\) that visits every nonnegative integer infinitely many times), and let \(L=\{x\in\{0,1\}^*:|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(M)>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.

reply

by Janos Kramar 821 days ago | Patrick LaVictoire likes this | link

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.

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

Note that the problem with
by Vadim Kosoy on Open Problems Regarding Counterfactuals: An Introd... | 0 likes

Typos on page 5: *
by Vadim Kosoy on Open Problems Regarding Counterfactuals: An Introd... | 0 likes

Ah, you're right. So gain
by Abram Demski on Smoking Lesion Steelman | 0 likes

> Do you have ideas for how
by Jessica Taylor on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

I think I understand what
by Wei Dai on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

>You don’t have to solve
by Wei Dai on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

Your confusion is because you
by Vadim Kosoy on Delegative Inverse Reinforcement Learning | 0 likes

My confusion is the
by Tom Everitt on Delegative Inverse Reinforcement Learning | 0 likes

> First of all, it seems to
by Abram Demski on Smoking Lesion Steelman | 0 likes

> figure out what my values
by Vladimir Slepnev on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

I agree that selection bias
by Jessica Taylor on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

>It seems quite plausible
by Wei Dai on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

> defending against this type
by Paul Christiano on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

2. I think that we can avoid
by Paul Christiano on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

I hope you stay engaged with
by Wei Dai on Autopoietic systems and difficulty of AGI alignmen... | 0 likes

RSS

Privacy & Terms