Tuesday, November 13, 2007

The Universe in Four Easy Operations

In this post I would like to explain some examples of physical systems performing computation. Any possible logical expression can be formed from four basic operation: AND, OR, NOT, and COPY, a discovery due to George Boole. AND takes a string of input bits and outputs a 1 if and only if all the bits are 1s and outputs 0 otherwise. OR outputs a 0 if and only if all the input bits are 0s and outputs a 1 otherwise. NOT simply transforms the 0s in the input string to 1s and the 1s to 0s, and COPY just reproduces the input string. In principle, any possible computational process could be carried out by these four operations, though creating computer programs in this way would be very impractical.

Entropy and Energy



Entropy is a measure of the amount of energy in a system that can not do work, while free energy, or Gibbs energy, is a measure of the amount of useful energy in a system. Entropy can also be defined as the amount of information required to describe the states of atoms in a system. In other words physical systems register information. States of the system where entropy is high and free energy is low are very unorganized or random. A great deal of information is required to describe these states. States of a system where free energy is high and entropy is low are organized. Therefore less information is required to describe them. Entropy tends to increase over time (in fact, this is the physical quantity which gives directionality to the "arrow of time"). Seth Lloyd described the unorganized uncertainty of entropy as "infectious." However, the total energy and total information in a closed system is conserved. This same phenomenon can be observed with bits and logical operations. Consider a string of two bits. The value of the first bit is unknown and the value of the second bit is 0. This system has two possible states: 00 and 10. Now suppose that value of second bit is flipped to 1 if and only if the value of the first bit is 1, and is left alone otherwise. After the operation is applied, the string still has two possible values, either 00 or 11. We cannot predict which state the system will be in before the operation is applied. Although the values of both the first and second bits are now uncertain, the total number of possible system states is conserved. Thus entropy has increased while the total information contained in the system is conserved. I will discuss a quantum system registering information in my next post, "Information Ex Nihilo."

No comments: