Hi there! Our project relies on ads or donation to keep the site free to use. Please
sending a donation . Thanks!

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

- 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

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

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

Comments (0)

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