There is a growing sense among physicists that all physical processes can be thought of in terms of the information they store and process; by some accounts information is the basic unit of existence in our cosmos. That kind of thinking has extraordinary implications: it means that reality is a kind of computation in which the basic processes at work simply chomp their way through a vast bedrock of information.
And yet this is at odds with another of the great challenges facing modern science: understanding the nature of randomness. While information can be defined as an ordered sequence of symbols, randomness is the opposite of order, the absence of pattern. One of the basic features of true randomness is that it cannot be produced by a computer, otherwise it wouldn't be random and that sets up a mouthwatering problem.
If all physical processes in the universe are ongoing computations, how does randomness arise? What kind of process can be responsible for its creation?
Until recently, mathematicians could only study randomness generated by classical physical processes such as coin tosses or computer programs which generate so-called pseudo-randomness. Since physical processes like coin tosses are hard to prove unbiased and difficult to manage, the work horse random number generators are programs such as Mathematica which uses the interesting properties of cellular automata to generate psedorandom sequences of numbers. Another method is simply to choose a sequence of numbers from the digits of an irrational number such as pi.
This stuff looks and feels random but because it can be computed, mathematicians treat it with suspicion.
But in the last few years, scientists have found a new source of randomness that cannot be produced by a computer program. This is called algorithmic randomness and it is the gold standard when it comes to the absence of order. The new source of this randomness is the quantum world and comes from exploiting quantum processes such as whether a photon is transmitted or reflected by a semi-silvered mirror.
This ought to produce sequences that can never be created by a computer. But are these sequences measurably different from those produced by computers?
This question is settled today by Cristian Calude at the University of Auckland in New Zealand and a few mates. These guys have carried out the first experimental comparison of randomness generated in these different ways and they've done it on a huge scale, using sequences 2^32 long.
Calude and co compare several flavours of random sequence generated in different ways.The sequences come from a quantum random number generator called Quantis, another from physicists in Vienna who also exploit quantum processes, they also use conventional sequences generated by computer programs such as Mathematica and Maple as well as a sequence of 2^32 bits from a binary expansion of pi.
The team use four different tests in their comparison, which fall into four categories based on algorithmic information theory, statistical tests involving frequency counts, a test based on Shannon's information theory and finally, a test based on random walks.
The results show that the sequence generated by Quantis is easily distinguishable from the other data sets. This say Calude and co, is evidence that quantum randomness is indeed incomputable. That means that it could not have been be generated by a computer.
Significantly, they leave unanswered the question of how convincing this evidence is that they've gathered and instead go to some length to point out that it is impossible to prove absolute randomness.
Nevertheless, if this evidence is taken at face value, it leaves us with a significant conceptual dilemma. On the one hand, it shows that Quantis produces sequences of random numbers that cannot be generated by a computer. And yet Quantis itself is a machine that must work by manipulating information in the way the laws of physics allow--it must be a computer of sorts.
This contradiction can only mean there is something wrong with the way we think about randomness or information or both (or at least with the way I've set it up here).
Of course, the answer must lie in the nature of information in the quantum world. It's easy enough to define information classically as an ordered sequence of symbols. But that definition falls apart as soon as these symbols become quantum in nature.
If each bit can be both a 1 and a 0 at the same time, what does it mean for such a such a sequence to be in order? Equally, what would the absence of order look like in such a quantum sequence?
It's in the tackling these questions that the nature of our universe is being teased apart.
Ref: arxiv.org/abs/1004.1521: Experimental Evidence of Quantum Randomness Incomputability