computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, 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, named after Hans-Joachim Bremermann, is a limit on the maximum rate of computation that can be achieved in a self-contained system in the material universe. It is derived from Einstein's mass-energy equivalency and the Heisenb ...

, is, according to

Hans-Joachim Bremermann Hans-Joachim Bremermann (1926–1996) was a German-American mathematician and biophysicist. He worked on computer science and evolution, introducing ideas of how mating generates new gene combinations. Bremermann's limit, named after him, is the m ...

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

Earth Earth is the third planet from the Sun and the only astronomical object known to harbor life. While large volumes of water can be found throughout the Solar System, only Earth sustains liquid surface water. About 71% of Earth's surfa ...

within a time period equal to the estimated age of the Earth.Bremermann, H.J. (1962
''Optimization through evolution and recombination''
In: Self-Organizing systems 1962, edited M.C. Yovitts et al., Spartan Books, Washington, D.C. pp. 93–106. The term ''transcomputational'' was coined by Bremermann.

Examples

Testing integrated circuits

Exhaustively testing all combinations of an

integrated circuit An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...

with 309 boolean inputs and 1

output Output may refer to: * The information produced by a computer, see Input/output * An output state of a system, see state (computer science) * Output (economics), the amount of goods and services produced ** Gross output in economics, the value of ...

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

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

Pattern recognition

Consider a ''q''×''q'' array of the

chessboard A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the bo ...

type, each square of which can have one of ''k''

color Color (American English) or colour (British English) is the visual perceptual property deriving from the spectrum of light interacting with the photoreceptor cells of the eyes. Color categories and physical specifications of color are associ ...

s. Altogether there are ''k''^''n''

pattern A pattern is a regularity in the world, in human-made design, or in abstract ideas. As such, the elements of a pattern repeat in a predictable manner. A geometric pattern is a kind of pattern formed of geometric shapes and typically repeated l ...

s, where ''n'' = ''q''². The problem of determining 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 The retina (from la, rete "net") is the innermost, light-sensitive layer of tissue of the eye of most vertebrates and some molluscs. The optics of the eye create a focused two-dimensional image of the visual world on the retina, which then ...

. The retina contains about a million light-sensitive

cell Cell most often refers to: * Cell (biology), the functional basic unit of life Cell may also refer to: Locations * Monastic cell, a small room, hut, or cave in which a religious recluse lives, alternatively the small precursor of a monastery ...

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

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

General systems problems

system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its environment (systems), environment, is described by its boundaries, ...

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

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 Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphi ...

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

In Douglas Adams's ''

The Hitchhiker's Guide to the Galaxy ''The Hitchhiker's Guide to the Galaxy'' (sometimes referred to as ''HG2G'', ''HHGTTG'', ''H2G2'', or ''tHGttG'') is a comic science fiction, comedy science fiction franchise created by Douglas Adams. Originally The Hitchhiker's Guide to th ...

'', Earth is a supercomputer, designed to calculate the question known as the "Ultimate Question of Life, The Universe and Everything" (the answer to which is known to be 42).See Places in The Hitchhiker's Guide to the Galaxy

References

{{DEFAULTSORT:Transcomputational Problem Theory of computation Computational complexity theory Limits of computation