You get a bonus - 1 coin for daily activity. Now you have 1 coin

Transcomputational task

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

Content

  • 1Examples of transcomputational problems
    • 1.1 Target traveling salesman
    • 1.2 Testing of integrated circuits
    • 1.3 Pattern Recognition
    • 1.4 System Analysis Problem
  • 2The consequences
  • 3SM. also
  • 4Notes

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 92 , and 67! ≈ 3,647111092 × 10 94 , 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 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] .

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

System analysis problem

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

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

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Highly loaded projects. Theory of parallel computing. Supercomputers. Distributed systems

Terms: Highly loaded projects. Theory of parallel computing. Supercomputers. Distributed systems