Transcomputational task

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 ⁹³ bits of information ^[1] . The number 10 ⁹³ , 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] .

Examples of transcomputational problems

Traveling salesman task

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 ⁹² , and 67! ≈ 3,647111092 × 10 ⁹⁴ , the task of checking all possible paths becomes trans-computational for n > 66.

Integrated Circuit Testing

Full testing of all combinations of integrated circuit with 308 inputs and 1 output requires verification of 2 ³⁰⁸ combinations of input data. Since the number 2 ³⁰⁸ 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]} .

Pattern Recognition

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 ⁿ , where n = q ² . 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] .

System analysis problem

A system of n variables, each of which can take k possible states, can have k ⁿ possible states. Analysis of such a system requires processing at least k ⁿ bits of information. The task becomes transcomputational if k ⁿ > 10 ⁹³ . This happens with the following values ​​of k and n ^[1] :

Consequences

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] .

see also

• The brain-matryoshka is a theoretical computing megastructure having dimensions comparable to the size of the planetary system.
• Calculation Limits
• Bremermann Limit