Lecture
The transcomputational problem (English Transcomputation problem ) is a problem in the theory of computational complexity, the solution of which requires the processing of more than 10 93 bits of information [1] . The number 10 93 , called the “Bremermann limit,” according to Hans-Joachim Bremermann, is the total number of bits processed by a hypothetical Earth-sized computer over a period of time equal to the total Earth lifetime [1] [2] . The term “transcomputation” was proposed by Bremermann [3] .
The task of the traveling salesman is to find a way around the specified list of cities with the lowest cost. The detour must visit all cities exactly once and return to the source city. If there are n cities in the list, then the number of possible ways to get around is n !. Since 66! approximately equal to 5.443449391 × 10 92 , and 67! ≈ 3,647111092 × 10 94 , the task of checking all possible paths becomes trans-computational for n > 66.
Full testing of all combinations of integrated circuit with 308 inputs and 1 output requires verification of 2 308 combinations of input data. Since the number 2 308 is transcomputational, the task of testing such an integrated circuit system is a transcomputational problem. This means that there is no way to check the schema for all input data using brute force [1] [4] .
Consider an array of size q × q , representing a pattern similar to a chessboard, in which each square can be of one of k colors. The total number of possible patterns is k n , where n = q 2 . The task of determining the best classification of patterns according to any chosen criterion can be solved by enumerating all possible color patterns. For 2 colors, such a search becomes transcomputation with an array size of 18 × 18 or more. For a 10 × 10 array, the task becomes trans-computational when there are 9 or more colors [1] .
This task is related to the study of the physiology of the retina. The retina consists of about a million photosensitive cells. Even if the cell has only 2 possible states, processing the state of the retina as a whole requires processing more than 10,300,000 bits of information. This far exceeds the Bremermann limit [1] .
A system of n variables, each of which can take k possible states, can have k n possible states. Analysis of such a system requires processing at least k n bits of information. The task becomes transcomputational if k n > 10 93 . This happens with the following values of k and n [1] :
k | 2 | 3 | four | five | 6 | 7 | eight | 9 | ten |
n | 308 | 194 | 154 | 133 | 119 | 110 | 102 | 97 | 93 |
The existence of real trans-computing tasks has the effect of limiting computers as data processing tools. A simple increase in computing power will not solve problems that require processing a huge number of possible situations [2] .
Comments
To leave a comment
Highly loaded projects. Theory of parallel computing. Supercomputers. Distributed systems
Terms: Highly loaded projects. Theory of parallel computing. Supercomputers. Distributed systems