Hi there! Our project relies on ads or donation to keep the site free to use. Please sending a donation . Thanks!
Подождите, пожалуйста, выполняется поиск в заданном разделе

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 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 (0)


avatar

To leave a comment login или register



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

Термины: Highly loaded projects. Theory of parallel computing. Supercomputers. Distributed systems