Transcomputationales Problem

In der Komplexitätstheorie ist ein transcomputationales Problem ein Problem, das die Verarbeitung von mehr als 1093 (circa 2309) Bits erfordert.[1] Jede Zahl größer als 1093 wird als transcomputationale Zahl bezeichnet. Die Grenze 1093 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.[1][2] Der Begriff transcomputational geht auf Bremermann zurück.[3]

Beispiele

Allgemeine Systeme

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

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 2309 Input-Kombinationen. 2309 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.[1][4]

Mustererkennung

Man betrachte ein q × q array (Schachbrett-Muster), wobei jedes Quadrat eine von k Farben haben kann. Zusammen gibt es damit kn mögliche Farbmuster, wobei n = q2 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.[1]

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 10300,000 Informationsbits hindeuten, was weit über der Bremermann-Grenze liegt.[1]

Konsequenzen

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

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

Verweise

  1. a b c d e f George J. Klir: Facets of systems science. Springer, 1991, ISBN 978-0-306-43959-9, S. 121–128.
  2. a b 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.
  3. Heinz Muhlenbein: Algorithms, data and hypotheses : Learning in open worlds. (PDF) German National Research Center for Computer Science, abgerufen am 3. Mai 2011.
  4. William Miles: Bremermann's Limit. Abgerufen am 1. Mai 2011. Die in der Quelle angegebene Zahl 308 is falsch: 2308 < 1093.