„Transcomputationales Problem“ – Versionsunterschied
| [ungesichtete Version] | [ungesichtete Version] |
K r2.7.1) (Robot: Adding pt:Problema transcomputacional |
K →In fiction: -- moved period |
||
| Zeile 31: | Zeile 31: | ||
== In fiction == |
== In fiction == |
||
In Douglas Adams's ''[[Hitchhiker's Guide to the Galaxy|The Hitchhiker's Guide to the Galaxy]]'', Earth '''is''' a supercomputer, designed to calculate the "Ultimate Question of Life, The Universe and Everything"<ref>See [[Places_in_The_Hitchhiker's_Guide_to_the_Galaxy#Earth]]</ref> |
In Douglas Adams's ''[[Hitchhiker's Guide to the Galaxy|The Hitchhiker's Guide to the Galaxy]]'', Earth '''is''' a supercomputer, designed to calculate the "Ultimate Question of Life, The Universe and Everything".<ref>See [[Places_in_The_Hitchhiker's_Guide_to_the_Galaxy#Earth]]</ref> |
||
== See also == |
== See also == |
||
Version vom 5. September 2012, 08:19 Uhr
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]
Examples of transcomputational problems
Traveling salesman problem
The travelling salesman problem is the problem of finding a tour of given list of cities which minimizes the total cost of the tour. A tour must visit all cities in the list exactly once, and return to the starting city. If there are n cities in the list, the number of possible tours is n!. Since 66! is approximately equal to 5.443449391*1092 and 67! to 3.647111092*1094, the problem of enumerating all possible tours becomes transcomputational for n > 66.
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 (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]
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 color patterns, where n = q2. The problem of determining of 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]
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 |
Implications
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]:
- "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's The Hitchhiker's Guide to the Galaxy, Earth is a supercomputer, designed to calculate the "Ultimate Question of Life, The Universe and Everything".[5]
See also
- Jupiter brain is a theoretical computing megastructure the size of a planet
References
- ↑ a b c d e f George J. Klir: Facets of systems science. Springer, 1991, ISBN 978-0-306-43959-9, S. 121–128.
- ↑ a b 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.
- ↑ Heinz Muhlenbein: Algorithms, data and hypotheses : Learning in open worlds. German National Research Center for Computer Science, abgerufen am 3. Mai 2011.
- ↑ William Miles: Bremermann's Limit. Abgerufen am 1. Mai 2011.
- ↑ See Places_in_The_Hitchhiker's_Guide_to_the_Galaxy#Earth