the impossibility of infallible computation

King_Anarchist

King_Anarchist

Chrono Cadet
On the computational capabilities of physical systems part I: the impossibility of infallible computation

http://arxiv.org/abs/physics/0005058

In this first of two papers, strong limits on the accuracy of physical computation are established. First it is proven that there cannot be a physical computer C to which one can pose any and all computational tasks concerning the physical universe. Next it is proven that no physical computer C can correctly carry out any computational task in the subset of such tasks that can be posed to C. As a particular example, this means that there cannot be a physical computer that can, for any physical system external to that computer, take the specification of that external system's state as input and then correctly predict its future state before that future state actually occurs. The results also mean that there cannot exist an infallible, general-purpose observation apparatus, and that there cannot be an infallible, general-purpose control apparatus. These results do not rely on systems that are infinite, and/or non-classical, and/or obey chaotic dynamics. They also hold even if one uses an infinitely fast, infinitely dense computer, with computational powers greater than that of a Turing Machine.
 
True in that presented context the ultimate result may be construed as 100% equals false.
However, I'd take 99.9999991% or the like anyday which is possible /ttiforum/images/graemlins/yum.gif
 
However, I'd take 99.9999991% or the like anyday which is possible
Click to expand...

There's a practical question here.

Recounts in political elections show that it is very difficult to accurately count a large number, one-bye-one. If there are 10,000 voters, is it reasonable to expect an accuracy of one part in ten thousand (.9999)? Usually one part in a thousand is doing good.
In other words what kind of accuracy can one obtain in an actual count? /ttiforum/images/graemlins/mad.gif
 
There's an interesting point.

Packer, you do know where I metaphorically drew that specific percentile?

Reminds me of a very old convo with RMT about decimal and dimensions.

The subjects are not directly related, but it's interesting in both scenerios when dealing with cause and effect (or an after product of effect, being precision?).
 
First it is proven that there cannot be a physical computer C to which one can pose any and all computational tasks concerning the physical universe.
Click to expand...

So you can't predict the future, but the past is fair game.... Eeeehxcellent. /tents fingers
 
First it is proven that there cannot be a physical computer C to which one can pose any and all computational tasks concerning the physical universe. Next it is proven that no physical computer C can correctly carry out any computational task in the subset of such tasks that can be posed to C. As a particular example, this means that there cannot be a physical computer that can, for any physical system external to that computer, take the specification of that external system's state as input and then correctly predict its future state before that future state actually occurs.
Click to expand...


It depends very much on what the computational task is. When it comes to getting the Cassini spacecraft a billion miles to Saturn, the actual discrepancy was just one second ( or about 6 miles ) after 7 years. Most of the discrepancy being due to solar wind flux....which cannot be predicted.

Some purely mechanical systems are easy to predict the behaviour of. That is precisely why missions such as Cassini are possible......the calculations are complex but the basic rules are invariant and a given input will always lead to a given output.

Where prediction breaks down is with 'chaotic systems'. These are systems for which the tiniest variation in the input can lead to huge difference in the output. One such very simple system is the double pendulum ( one pendulum attached to the end of another )......where for certain begining states the behaviour is totally chaotic and the smallest of changes can give a wildly differing result.

So, given that we cannot always predict behaviour in the real world, it is thus highly unlikely that even the most powerful computer could do so in any model. And even in cases where the maths is exact and concise, such as a mission to Saturn, there are always unknown external variables that can simply never be fully accounted for.
 
Back
Top