On Sun, Mar 28, 1999 at 06:22:44PM -0800, hal@rain.org wrote:
> I don't fully understand the issue here. Suppose I flip a coin but don't
> look at how it lands yet. I can assume a uniform distribution. But I
> can expend some effort, say, leaning over and looking at the floor, and
> learn what the coin is. At the cost of expending that effort I learn
> whether the coin fell heads or tails.
In the coin toss and similar experiments where uncertainty is caused by lack of complete information, there are commonly accepted principles for computing a probability distribution on the outcome and for updating the distribution as new information arises. I am looking for similar principles for cases where uncertainty is caused by lack of computational resources (or better yet a combination of both), and arguments that these principles are reasonable. I was hoping a systematic treatment of this subject already exists, but since nobody referenced one it probably doesn't exist yet.
Most people seem to assume that probability theory is sufficient to handle computational uncertainty. I don't really disagree, but would like to see some kind of formal argument that the approach is consistent and won't lead to subtle paradoxes.