Saturday, May 14, 2011

Davy's law

Davy's Law: Computers can't compute/predict themselves.

No physical computer is capable of losslessly determining it's effect on every state in it's state space by means of internal simulation. That is, the only way it can accurately achieve the result of a state is by actually being put into that state.

The limiting factor here is the necessity of storing the entirety of it's state AND its rule set within it's alloted state (with room to spare for performing computation). This would be in violation of the pigeonhole principle's effect on lossless compression. Not to mention that if it were possible, it could simulate it simulating it simulating it... And unless it can solve the halting problem, that's probably just not a good feature for a system to have.

Davy's law does not prohibit computers from computing with isolated portions of it's state. It also does not state that there aren't some global state computations that are possible. That is, some states can be losslessly compressed and manipulated in this form. Rather it postulates that a computer cannot compute the results of every state for it's entire state space.