Transcomputationales Problem

In der Komplexitätstheorie ist ein transcomputationales Problem ein Problem, das die Verarbeitung von mehr als 10⁹³ (circa 2³⁰⁹) Bits erfordert. Jede Zahl größer als 10⁹³ wird als transcomputationale Zahl bezeichnet. Die Grenze 10⁹³ wird Bremermann-Grenze genannt, was nach Hans Joachim Bremermann der Gesamtanzahl der von einem hypothetischen Computer der Größe der Erde innerhalb der Lebenszeit der Erde verarbeiteten Bits entspricht. Der Begriff transcomputational geht auf Bremermann zurück.

Beispiele

Allgemeine Systeme

Ein System von n Variablen, die jeweils k verschiedene Zustände annehmen können, hat kⁿ mögliche Systemzustände. Eine vollständige Systemanalyse erfordert daher die Verarbeitung von mindestens kⁿ Informationsbits. Transcomputational wird die Analyse für kⁿ > 10⁹³, was für folgende Werte für k und n der Fall ist.

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

Test integrierter Schaltkreise

Der komplette Test aller Kombinationen eines Integrierten Schaltkreises mit 309 Inputs und 1 Output entspricht dem Test von 2³⁰⁹ Input-Kombinationen. 2³⁰⁹ ist eine transcomputationale Zahl, und der Test dieses Systems somit ein transcomputationales Problem, was bedeutet, dass es keine Möglichkeit gibt, alle Inputs mittels der Brute-Force-Methode alleine zu verifizieren.

Mustererkennung

Man betrachte ein q × q array (Schachbrett-Muster), wobei jedes Quadrat eine von k Farben haben kann. Zusammen gibt es damit kⁿ mögliche Farbmuster, wobei n = q² die Anzahl der Felder ist. Um die beste Klassifizierung der Muster nach vorgegebenen Kriterien zu bestimmen, können alle Farbmuster systematisch durchsucht werden. Für eine vorgegebene Anzahl von 2 Farben wird diese Suche transcomputational, wenn das array 18 × 18 oder größer ist. Für eine vorgegebene array-Größe von z. B. 10 ×10 wird das Problem bei 9 oder mehr vorhandenen Farben transcomputational.

Das bezieht sich praktisch z. B. auf die Physiologie der Netzhaut. Diese hat etwa eine Million lichtsensitive Zellen. Selbst bei nur zwei möglichen Zellzuständen pro Zelle (aktiv und inaktiv) würde die Netzhaut als ganzes betrachtet auf eine Prozessierung von mehr als 10^300,000 Informationsbits hindeuten, was weit über der Bremermann-Grenze liegt.

Konsequenzen

Die Existenz eines realen transcomputationellen Problems impliziert generell die Grenzen von Computern als Datenverarbeitungsmaschinen. Das wird am besten durch Bremermanns eigene Worte zusammengefasst:

"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 der Fiktion

In Douglas Adams’ Per Anhalter durch die Galaxis ist die Erde ein Supercomputer, designed um die Antwort auf die „Ultimative Frage nach dem Leben, dem Universum und dem ganzen Rest“ zu berechnen.