Transcomputational problem - AbsoluteAstronomy.com

In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 10⁹³ bits of information. Any number greater than 10⁹³ is called a transcomputational number. The number 10⁹³, called Bremermann's limit

Bremermann's limit

Bremermann's Limit, named after Hans-Joachim Bremermann, is the maximum computational speed of a self-contained system in the material universe. It is derived from Einstein's mass-energy equivalency and the Heisenberg uncertainty principle, and is c2/h ≈ 1.36 × 1050 bits per second per...

, is, according to Hans-Joachim Bremermann

Hans-Joachim Bremermann

Hans-Joachim Bremermann was a German-American mathematician and biophysicist. He worked on computer science and evolution, introducing new ideas of how mating generates new gene combinations...

, the total number of bits processed by a hypothetical computer the size of the earth

Earth

Earth is the third planet from the Sun, and the densest and fifth-largest of the eight planets in the Solar System. It is also the largest of the Solar System's four terrestrial planets...

within a time period equal to the estimated age of the earth. The term transcomputational was coined by Bremermann.

Traveling salesman problem

The travelling salesman problem

Travelling salesman problem

The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...

is the problem of finding a tour of given list of cities which minimizes the total cost of the tour. A tour must visit all cities in the list exactly once, and return to the starting city. If there are n cities in the list, the number of possible tours is n!. Since 66! is approximately equal to 5.443449391*10⁹² and 67! to 3.647111092*10⁹⁴, the problem of enumerating all possible tours becomes transcomputational for n > 66.

Testing integrated circuits

Exhaustively testing all combinations of an integrated circuit

Integrated circuit

An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...

with 308 input

Input

Input is the term denoting either an entrance or changes which are inserted into a system and which activate/modify a process. It is an abstract concept, used in the modeling, system design and system exploitation...

s and 1 output

Output

Output is the term denoting either an exit or changes which exit a system and which activate/modify a process. It is an abstract concept, used in the modeling, system design and system exploitation.-In control theory:...

requires testing of a total of 2³⁰⁸ combinations of inputs. Since the number 2³⁰⁸ is a transcomputational number (that is, a number greater than 10⁹³), the problem of testing such a system of integrated circuit

Integrated circuit

s is a transcomputational problem. This means that there is no way one can verify the correctness of the circuit for all combinations of inputs through brute force

Brute-force search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...

alone.

Pattern recognition

Consider a q ×q array of the chessboard

Chessboard

A chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...

type each square of which can have one of k color

Color

Color or colour is the visual perceptual property corresponding in humans to the categories called red, green, blue and others. Color derives from the spectrum of light interacting in the eye with the spectral sensitivities of the light receptors...

s. Altogether there are kⁿ color

Color

pattern

Pattern

A pattern, from the French patron, is a type of theme of recurring events or objects, sometimes referred to as elements of a set of objects.These elements repeat in a predictable manner...

s, where n = q². The problem of determining of the best classification of the patterns, according to some chosen criterion, may be solved by a search through all possible color patterns. For two colors, such a search becomes transcomputational when the array is 18 × 18 or larger. For a 10 ×10 array, the problem becomes transcomputational when there are 9 or more colors.

This has some relevance in the physiological studies of the retina

Retina

The vertebrate retina is a light-sensitive tissue lining the inner surface of the eye. The optics of the eye create an image of the visual world on the retina, which serves much the same function as the film in a camera. Light striking the retina initiates a cascade of chemical and electrical...

. The retina contains about a million light-sensitive

Light sensitivity

Light sensitivity or photosensitivity is an increase in the reactivity of the skin to sunlight. Apart from vision, human beings have many physiological and psychological responses to light. In rare individuals an atypical response may result in serious discomfort, disease, or injury. Some drugs...

cell

Cell (biology)

The cell is the basic structural and functional unit of all known living organisms. It is the smallest unit of life that is classified as a living thing, and is often called the building block of life. The Alberts text discusses how the "cellular building blocks" move to shape developing embryos....

s. Even if there were only two possible states for each cell (say, an active state and an inactive state) the processing of the retina

Retina

as a whole requires processing of more than 10^300,000 bits of information. This is far beyond Bremermann's limit

Bremermann's limit

General systems problems

A system

System

System is a set of interacting or interdependent components forming an integrated whole....

of n variables, each of which can take k different states, can have
kⁿ possible system states. To analyze such a system, a minimum of kⁿ bits of information are to be processed. The problem becomes transcomputational when kⁿ > 10⁹³. This happens for the following values of k and n:

k	2	3	4	5	6	7	8	9	10
n	308	194	154	133	119	110	102	97	93

Implications

The existence of real-world transcomputational problems implies the limitations of computers as data processing tools. This point is best summarized in Bremermann's own words:

"The experiences of various groups who work on problem solving, theorem proving and pattern recognition all seem to point in the same direction: These problems are tough. There does not seem to be a royal road or a simple method which at one stroke will solve all our problems. My discussion of ultimate limitations on the speed and amount of data processing may be summarized like this: Problems involving vast numbers of possibilities will not be solved by sheer data processing quantity. We must look for quality, for refinements, for tricks, for every ingenuity that we can think of. Computers faster than those of today will be a great help. We will need them. However, when we are concerned with problems in principle, present day computers are about as fast as they ever will be.

We may expect that the technology of data processing will proceed step by step – just as ordinary technology has done. There is an unlimited challenge for ingenuity applied to specific problems. There is also an unending need for general notions and theories to organize the myriad details."

In fiction