It's time for another issue of “Intractable Problems,” a column designed to challenge and stimulate your thinking skills. As I promised you last issue, we will examine what limits, if any, exist on the amount of information we can hope to process in a given interval of time.
A limit, you say? How can there be a limit for something like information, which is not real? Well, whether it is real or not, information needs to be moved around. We interpret the 'processing of x bits' to be the transmission of that many bits over one or many communication channels within the computing system. To do this, it's obvious that the information in the computer system has to be physically encoded in some form.
In 1962, Hans Bremermann assumed that we would encode the information in terms of an energy level. [1] Of course, Heisenberg's Uncertainty Principle showed that we can only measure the energy to a certain accuracy. The measurement accuracy limits the number of markers into which the energy level can accurately be divided. Now, Hartley's information measure relates the information content of N markers to the logarithm of N. Using this, we can calculate the maximum amount of information that can be represented within our energy level.
So, a given energy level has a maximum amount of information it can carry. Now, using Heisenberg's uncertainty principle, Planck's constant, and Einstein's famous E = mc2 formula, we can easily show Bremermann's conjecture that “no data processing system, whether artificial or living, can process more than 2 × 1047 bits per second per gram of its mass.”
Oh my goodness! What does this mean? Well, hypothetically, let's assume that we have a computer the size of the Earth and a time period equal to the estimated age of the Earth. Then this imaginary computer would not be able to process more than about 1093 bits. This number, 1093, is called Bremermann's limit, and problems that require processing more than 1093 bits of information are called transcomputational problems.
The funny thing is, these types of problems do exist in the real world. For example, exhaustively testing all combinations of an integrated circuit with 308 inputs and 1 output is a transcomputational problem. Such circuits exist in today's computer processors.
Bremermann, in the conclusion of his paper, wrote the following:
“The experiences of various groups who work on problem solving, theorem proving and pattern recognition all seem to point in the same direction: These problems are tough. There does not seem to be a royal road or a simple method which at one stroke will solve all our problems. My discussion of ultimate limitations on the speed and amount of data processing may be summarized like this: Problems involving vast numbers of possibilities will not be solved by sheer data processing quantity. We must look for quality, for refinements, for tricks, for every ingenuity that we can think of. Computers faster than those of today will be of great help. We will need them. However, when we are concerned with problems in principle, present day computers are about as fast as they will ever be.”
Ah well, that's life. If nothing else, at least it helps support my conjecture that cats must be dumber than dogs. On average, cat's brains are not as massive as dog's brains and therefore cannot hold as much information. On the other hand, cats are all known to be tricky and devious, so it is possible that they have ingeniously discovered ways to work around their limitations.
Next issue, we will take a critical look at the serious problems involved in systems engineering.
Bremermann, H.J. “Optimization through evolution and recombination.” In: Self-Organizing Systems, edited by M.C. Yovits et al., Spartan Books, 1962, pp. 93-106
Copyright © 1995-2004 WSM Information Systems Inc.