Quantum noise and information
Hans J. Bremermann · Project Euclid (Cornell University) · 1967
Existing computers are too slow, have too little storage and not enough processing capacity to cope with certain tasks. The following are typical of such tasks: inspection of all branches of the of all possible move sequences of a game, such as chess, optimization of (nonlinear) functions of many variables, certain decision and cognition problems. 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 problemsincluding 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 inearly 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 [23]) 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 [18] for checkers, Gelernter [8] for theorem proving, Slagle [21] for evaluating integrals, Raphael [14] 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 [4]. A preliminary announcement of the results of this paper was made in Bremermann [3].