In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information.[1] Any number greater than 1093 is called a transcomputational number. The number 1093, called Bremermann's limit, is, according to Hans-Joachim Bremermann, the total number of bits processed by a hypothetical computer the size of the Earth within a time period equal to the estimated age of the Earth.[1][2] The term transcomputational was coined by Bremermann.[3]
Exhaustively testing all combinations of an integrated circuit with 309 boolean inputs and 1 output requires testing of a total of 2309 combinations of inputs. Since the number 2309 is a transcomputational number (that is, a number greater than 1093), the problem of testing such a system of integrated circuits is a transcomputational problem. This means that there is no way one can verify the correctness of the circuit for all combinations of inputs through brute force alone.[1][4]
Consider a q×q array of the chessboard type, each square of which can have one of k colors. Altogether there are kn color patterns, where n = q2. The problem of determining the best classification of the patterns, according to some chosen criterion, may be solved by a search through all possible color patterns. For two colors, such a search becomes transcomputational when the array is 18×18 or larger. For a 10×10 array, the problem becomes transcomputational when there are 9 or more colors.[1]
This has some relevance in the physiological studies of the retina. The retina contains about a million light-sensitive cells. Even if there were only two possible states for each cell (say, an active state and an inactive state) the processing of the retina as a whole requires processing of more than 10300,000 bits of information. This is far beyond Bremermann's limit.[1]
A system of n variables, each of which can take k different states, can have kn possible system states. To analyze such a system, a minimum of kn bits of information are to be processed. The problem becomes transcomputational when kn > 1093. This happens for the following values of k and n:[1]
k | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
n | 308 | 194 | 154 | 133 | 119 | 110 | 102 | 97 | 93 |
The existence of real-world transcomputational problems implies the limitations of computers as data processing tools. This point is best summarized in Bremermann's own words:[2]