March 2012
« Feb   Apr »




Information Uncertainty Principle

Through Denning’s Presentation Great Principles of Computing I heard of this fascinating tale regarding Buridan’s ass.

It refers to a hypothetical situation wherein an ass is placed precisely midway between a stack of hay and a pail of water. Since the paradox assumes the ass will always go to whichever is closer, it will die of both hunger and thirst since it cannot make any rational decision to choose one over the other.

What’s more interesting than the philosophy behind the donkey’s dilemma, are the actual applications:

Leslie Lamport calls this result Buridan’s principle, and states it as: A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time.

A version of Buridan’s principle actually occurs in electrical engineering. Specifically, the input to a digital logic gate must convert a continuous voltage value into either a 0 or a 1 which is typically sampled and then processed. If the input is changing and at an intermediate value when sampled, the input stage acts like a comparator. The voltage value can then be likened to the position of the ass, and the values 0 and 1 represent the bales of hay. Like the situation of the starving ass, there exists an input on which the converter cannot make a proper decision, resulting in a metastable state. Having the converter make an arbitrary choice in ambiguous situations does not solve the problem, as the boundary between ambiguous values and unambiguous values introduces another binary decision with its own metastable state.

I think that it might be possible to turn this into an Information uncertainty principle, analogous to that of the physicist’s quantum uncertainty principle.

Specifically, an observer of a Turing machine calculation can only be in one of two scenarios:

  1. uncertain about the decision a computation will take within a given (determined) time, or
  2. certain about the decision, but uncertain about the time it takes to decide.

If the knowledge trade-off between two extremes can be quantified, in the same way that ħ quantifies the quantum uncertainty trade-off between position and momentum, we might really have something substantial!

Leave a Reply