From: Benja Fallenstein (benja.fallenstein@gmail.com)
Date: Mon Jan 12 2009 - 10:00:25 MST
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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT