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].
Examples of transcomputational problems
Testing integrated circuits
Exhaustively testing all combinations of an integrated circuit with 308 inputs and 1 output requires testing of a total of 2308 combinations of inputs. Since the number 2308 is a transcomputational number, 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.[1][3]
Pattern recognition
Consider a q ×q array of the chessboard type each square of which can have one of k colors. Altogether there are kn, wher n = q2 color patterns. A determination of the best classification of the patterns, according to some chosen criterion, requires a search through all possible color patterns. For two colors, the problem 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 there are only two possible states for each cell, 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.
General systems problems
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 |
References
- ↑ a b c d e George J. Klir: Facets of systems science. Springer, 1991, ISBN 978-0-306-43959-9, S. 121 - 128.
- ↑ Bremermann, H.J. (1962) Optimization through evolution and recombination In: Self-Organizing systems 1962, edited M.C. Yovitts et al., Spartan Books, Washington, D.C. pp. 93–106.
- ↑ William Miles: Bremermann's Limit. Abgerufen am 1. Mai 2011.