**From:** Benja Fallenstein (*benja.fallenstein@gmail.com*)

**Date:** Mon Jan 12 2009 - 10:00:25 MST

**Next message:**Matt Mahoney: "Re: [sl4] Rolf's gambit revisited"**Previous message:**Benja Fallenstein: "Re: [sl4] Rolf's gambit revisited"**In reply to:**Peter de Blanc: "Re: [sl4] Rolf's gambit revisited"**Next in thread:**Norman Noman: "Re: [sl4] Rolf's gambit revisited"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Hi Peter,

sorry for the delayed reply.

Peter de Blanc wrote:

*> Benja Fallenstein wrote:
*

*>>
*

*>> Question: Can a Turing
*

*>> machine X, based on any criteria at all, form a computable probability
*

*>> distribution that assigns probability >1/n to a specific hypothesis Y
*

*>> such that K(Y) > K(X) + K(n)? The answer isn't clear to me, although
*

*>> my intuition is that it is "no."
*

*>
*

*> That's an interesting question! The answer is yes. (...)
*

*> To get an answer of "no," I think you should ask: Can a Turing machine X
*

*> form a computable probability distribution that assigns probability >p
*

*> to a specific hypothesis Y such that K(Y) > K(X) - log(p) + C?
*

Yikes! You're right, of course, and an interesting mistake on my part

that was :-]

*> Then if you choose the right constant C, the answer is "no."
*

*>
*

*> This is because, using entropy coding, we can specify Y with -log(p) bits
*

*> given X. We need K(X) bits to specify X, and C bits to specify an entropy
*

*> decoder.
*

Hm; am I right in thinking that you understood my question as the case

where X itself represents a computable function that computes the

probability distribution? That is actually not quite what I had in

mind; I was thinking about the case where X computes the probability

distribution internally, and then uses it to do something else based

on it.

Of course, the answer is "yes" in the sense that a Turing machine can

enumerate *all* computable probability distributions, but that's not

what I meant; to make this specific, narrow this down to the case I

had in mind: can a Turing machine X perform an expected utility

computation and write out the action with the highest expected

utility, according to a computable probability distribution that

assins probability >p to a hypothesis Y such that K(Y) > K(X) - log(p)

+ C?

It's not clear to me whether such a machine can in general be used to

create an entropy decoder for the probability distribution, but it

still seems likely that it's not possible for a machine to perform

such a computation.

Thanks,

- Benja

**Next message:**Matt Mahoney: "Re: [sl4] Rolf's gambit revisited"**Previous message:**Benja Fallenstein: "Re: [sl4] Rolf's gambit revisited"**In reply to:**Peter de Blanc: "Re: [sl4] Rolf's gambit revisited"**Next in thread:**Norman Noman: "Re: [sl4] Rolf's gambit revisited"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:01:03 MDT
*