It is the contention of this paper that speed, memory, and processing capacity of any possible future computer equipment are limited by certain physical barriers: the light barrier, the quantum barrier, and the thermodynamical barrier. These limitations imply, for example, that no computer, however constructed, will ever be able to examine the entire tree of possible move sequences of the game of chess.
Some mathematicians (for example, the intuitionist school) object to certain kinds of "existence proofs" and favor "constructive proofs." Finite problems including problems such as examination of the chess tree–are considered as trivial in this context. In view of the physical barriers to computation, however, many finite problems are transcomputational.
In order to have a computer play a perfect or nearly perfect game (chess, go, and so forth) it will be necessary either to analyze the game completely (as, for example, "Nim" has been analyzed cf. Wang ) or to analyze the game in an approximate way and combine this with a limited amount of tree searching. Such an approach has been pioneered, for example, by Samuel  for checkers, Gelernter  for theorem. proving, Slagle  for evaluating integrals, Raphael  for question answering. A theoretical understanding of such heuristic programming, however, is still very much wanting.
Some further aspects of the physical limits of computation have been discussed in Bremermann . A preliminary announcement of the results of this paper was made in Bremermann .
- PROPOSITION. The capacity of any closed information transmission or processing system does not exceed mc2/h bits per second, where m is the mass of the system, c the light velocity, h Planck's constant.
Note that the system is assumed to be closed. Its mass consists of the mass of the particles making up its structure plus the mass equivalent of energy employed in signals, and so forth. No matter how the total mass is distributed, the mass equivalent of the signals is bounded by m and the signaling energy by mc2.
According to quantum mechanics, electromagnetic oscillations are quantized
and so are all other signals. With every moving particle a wave is associated
which is quantized such that the energy E
of one quantum is E = hn,
where n is the
frequency of the wave. In order that a signal with which a frequency
is associated can be observed, at least one quantum of the signal is required.
This condition limits the frequency band that can be used for signaling
The capacity C of a band limited channel is given by a formula due to Shannon 
To compute the noise energy we assume that our signal is represented by a time varying complex valued function f(t). (If the physical signal is a vector, spinor or other nonscalar quantity, then we choose a suitable representation and consider each scalar component as a separate channel.) Suppose f(t) is observed for a time interval DT. In this interval we represent f(t) by means of a Fourier series
If the spectrum of f(t)
is band limited, then an
= 0 for
The mass of a hydrogen atom is about 1.67 ×10-24 gm, while c2/h = 1.35 ×1047 gm-1 sec-1. Thus our proposition implies that per mass of a hydrogen atom no more than 2.3 ×1023 bits can be transmitted per second. It appears that our limit is quite a generous one.
On the other hand, the number of protons in the universe is estimated as about 1073. Thus, if the whole universe were dedicated to data processing, and not counting other factors that tend to restrict data processing, no more than 2.3 ×1096 bits per second, or 7 ×10103 bits per year could be processed. Note that this figure falls short of the number of 10120possible move sequences of the game of chess (compare Bremermann ).
Another way of looking at the quantum barrier is the following. The
size of the nucleus of the hydrogen atom is about 10-12 cm.
Light travels one centimeter in
The quantum barrier was announced in the form of a conjecture in Bremermann . W. W. Bledsoe  derived from it an absolute bound for the speed of serial machines. The notion of quantum noise apparently was coined by Gabor , . Quantum effects in communication channels have also been studied by Bolgiano and Gottschalk , Lasher , and Gordon , . The latter gives a formula for quantum noise in a transmission line that operates at a fundamental frequency n. For small noise power (from other sources) the quantum effect amounts to an equivalent noise power of hnB, where B is the number of modes (harmonies) that are excited. Kompfner  has pointed out that Gordon's results imply that quantum noise constitutes a problem in optical communications, for example, if a laser beam is used as carrier. Gordon's results imply that for a frequency of 6 ×1014 cycles per second (that is, one half micron wavelength, in the visible spectrum) quantum noise is about 100 times as large as thermal noise at room temperature (~300° K). Thermal noise, in general, will be discussed in the following sections. For a further bibliography on quantum noise effects, see Gordon . Note that quantum effects discussed in the literature are mostly concerned with special cases. In contrast, our quantum barrier is an upper bound on data transmission that for most any specific case. could be substantially improved, which, however, has the advantage of being universal.
The second law of thermodynamics asserts that the state of an isolated system changes in such a way that the entropy increases. According to Boltzmann-Planck the entropy change of a system is equal to k ln (P1/P2), where P1 and P2 are the probabilities of the initial and final states.
Brillouin  distinguishes between free and bound information. Information theory is an abstract theory; the symbols and their probabilities are abstract quantities. When they are represented by physical states or events the information becomes bound. We are concerned with bound information.
If a quantity I (bits) of information is encoded in terms of physical markers, the probability of the state of the system is decreased by a factor of 2-I and thus the entropy is decreased by k ln 2I = Ik ln 2. If the system is isolated, there must be a compensating increase in entropy to offset the decrease.
If the total system is composed of an information system in contact with a thermostat, then if there are no other entropy changes (for example, chemical), then the thermostat absorbs DQ = TDS units of heat, that is kT ln 2 units per bit of information (compare Brillouin , J. Rothstein , ,  and Setlow-Pollard ). This calculation applies only to processes where quantum effects are negligible. Brillouin (, p. 185) has shown that in the special case where the physical marker is a harmonic oscillator of frequency n the amount of heat generated is kT ln 2 in the thermal range, that is, for hn < kT but hn when hn > kT. Thus when the rate of information processing is rapid, we may expect quantum effects that increase the amount of heat generated above kT ln 2 per bit. Here, obviously, are open problems. There also remains the problem whether and under what conditions the receiver of bound information can utilize the negentropy conveyed.
In Bremermann  it was shown that microorganisms (E. Coli) produce bound information as they grow and do so about as efficiently as the kT ln 2 per bit rule will permit.
NOTE ADDED IN PROOF. The author has become only recently aware of the work of D. S. Lebedev and L. B. Levitin which is concerned with closely related questions , , , .
This work was supported in part by the Office of Naval Research under contracts NONR 222(85) and NONR 3656(08).