Transcomputational problem

from Wikipedia, the free encyclopedia

In complexity theory , a transcomputational problem is a problem that requires more than 1093 (about 2,309 ) bits to be processed. Any number greater than 10 93 is called a transcomputational number . The limit 10 93 is called the Bremermann limit , which, according to Hans Joachim Bremermann , corresponds to the total number of bits processed by a hypothetical computer of the size of the earth within the life of the earth. The term transcomputational goes back to Bremermann.

Examples

General systems

A system of n variables, each of which can assume k different states, has k n possible system states. A complete system analysis therefore requires the processing of at least k n information bits. The analysis becomes transcomputational for k n > 10 93 , which is the case for the following values ​​for k and n .

k 2 3 4th 5 6th 7th 8th 9 10
n 308 194 154 133 119 110 102 97 93

Integrated circuit test

The complete test of all combinations of an integrated circuit with 309 inputs and 1 output corresponds to the test of 2,309 input combinations. 2 309 is a transcomputationale number, and the test of this system thus a transcomputational problem, which means that there is no way all inputs using the brute force method to verify itself.

Pattern recognition

Consider a q × q array ( chessboard pattern) where each square can have one of k colors . Together there are therefore k n possible color patterns, where n = q 2 is the number of fields. In order to determine the best classification of the samples according to given criteria, all color samples can be searched systematically. For a given number of 2 colors, this search becomes transcomputational if the array is 18 × 18 or larger. For a given array size of e.g. B. 10 × 10 the problem with 9 or more colors present becomes transcomputational.

This refers practically z. B. on the physiology of the retina . This has around a million light-sensitive cells. Even with only two possible cell states per cell (active and inactive), the retina as a whole would indicate processing of more than 10,300,000 information bits, which is far above the Bremermann limit .

Consequences

The existence of a real transcomputational problem generally implies the limits of computers as data processing machines. This is best summed up by Bremermann's own words:

"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 a great help. We will need them. However, when we are concerned with problems in principle, present day computers are about as fast as they ever will be .
We may expect that the technology of data processing will proceed step by step - just as ordinary technology has done. There is an unlimited challenge for ingenuity applied to specific problems. There is also an unending need for general notions and theories to organize the myriad details. "

In fiction

In Douglas Adams' The Hitchhiker's Guide to the Galaxy , the earth is a supercomputer designed to compute the answer to the "ultimate question about life, the universe and all the rest".

References

  1. ↑ a b c d e f George J. Klir: Facets of systems science . Springer, 1991, ISBN 978-0-306-43959-9 , pp. 121-128.
  2. ↑ a b Bremermann, HJ (1962) Optimization through evolution and recombination In: Self-Organizing systems 1962, edited MC Yovitts et al., Spartan Books, Washington, DC pp. 93-106.
  3. ↑ Heinz Muhlenbein: Algorithms, data and hypotheses: Learning in open worlds. (PDF) German National Research Center for Computer Science, accessed on May 3, 2011 .
  4. ^ William Miles: Bremermann's Limit. Retrieved May 1, 2011 . The number 308 given in the source is incorrect: 2 308 <10 93 .