Mathematikern, Physikern und Ingenieuren traut man allgemein die Fähigkeit zu, auch schwierige Probleme durch Berechnungen zu lösen. Häufig müssen sie jedoch ihr Scheitern eingestehen. Das kann – wie im täglichen Leben – daran liegen, daß wesentliche Größen unbekannt sind: Ob man zur Finanzierung seines Hauses eine Hypothek mit 15 oder mit 30 Jahren Laufzeit aufnehmen soll, hängt von Zinssätzen, Steuervorschriften und dem eigenen Einkommen in der Zukunft ab. Bei einer großen Klasse wissenschaftlicher Fragen scheitert die Berechenbarkeit jedoch an einer anderen Ursache: der schieren Größe des Problems.

In der computerunterstützten Entwicklung von Medikamenten etwa geht es darum, wie fest ein hypothetischer Wirkstoff sich an einen biologischen Rezeptor bindet (Spektrum der Wissenschaft, März 1994, Seite 30). Bei typischerweise etwa 8000 Atomen in Wirkstoffmolekül, Lösungsmittel und biologischer Zielsubstanz läuft das auf ein Gleichungssystem mit 24000 Unbekannten hinaus, denn die Position jedes Atoms ist durch drei Koordinaten bestimmt. Je mehr Variable – oder, geometrisch gesprochen, Dimensionen – zu berücksichtigen sind, desto schwieriger wird in aller Regel die numerische Lösung. Häufig erfordern doppelt soviel Unbekannte nicht einfach die doppelte Rechenzeit, sondern unverhältnismäßig viel mehr: Die Komplexität des Problems wächst exponentiell mit der Zahl der Variablen. Sie kann so groß werden, daß selbst die besten Supercomputer der Zukunft nicht in angemessener Zeit zu einer Lösung kommen würden.

Sind solche praktisch unlösbaren Probleme nicht doch irgendwie lösbar? Glücklicherweise ist das manchmal der Fall. Man muß allerdings auf eine Garantie für Korrektheit verzichten und sich damit zufriedengeben, daß die berechnete Lösung nur meistens (aber nicht immer) eine vorgeschriebene Fehlertoleranz einhält. Zumindest für zwei Klassen sehr gängiger Probleme konnte einer von uns (Wo´zniakowski) dies auch formal beweisen: für die Integration, eine der fundamentalen Operationen der Differential- und Integralrechnung, und die Oberflächenrekonstruktion, mit der man ein Bild eines Objekts, zum Beispiel eines menschlichen Organs, aus unvollständigen Informationen – zum Beipiel computertomographischen Daten – aufzubauen sucht (Spektrum der Wissenschaft, Juli 1993, Seite 56).

Von diesen Resultaten können auch andere Bereiche profitieren. Häufig muß eine Bank ihren Bestand an Hypotheken bewerten unter der Unsicherheit, daß die Kunden die Schuld vorzeitig durch einen anderen Kredit ablösen können. Wenn bei 30 Jahren Laufzeit diese Möglichkeit an jedem Monatsersten besteht, gibt es so viele Unbekannte (die Gesamt-Darlehensbestände) wie Kündigungstermine, nämlich 12×30=360, und in die Schätzung gehen noch die ohnehin unbekannten Zinssätze der nächsten 30 Jahre ein.

Wir beschreiben im folgenden Hindernisse, die mitunter einer numerischen Lösung entgegenstehen, und Methoden, die es in manchen Fällen ermöglichen, sie zu umgehen. Dies gehört zu der neuen Theorie der Informationskomplexität. Möglicherweise kann man mit ihrer Hilfe sogar beweisen, daß bestimmte wissenschaftliche Fragen nie beantwortet werden können, weil es nicht genug Atome im Weltall gibt, um die erforderliche Rechnerleistung bereitzustellen. Das wäre eine neue prinzipielle Grenze wissenschaftlicher Erkenntnis.

Probleme mit unendlich vielen Unbekannten

Die Theorie der Informationskomplexität befaßt sich vornehmlich mit den numerischen Schwierigkeiten sogenannter kontinuierlicher Probleme. Ein Beispiel bietet die Bewegung der Planeten. Sie wird durch gewöhnliche Differentialgleichungen beschrieben; diese setzen die Änderung der Geschwindigkeit der bewegten Körper zu deren jeweils aktueller Position in Beziehung. Gesucht ist diese Position zu beliebigen Daten. Weil die Zeit jeden reellen Zahlenwert annehmen kann, wird dieses mathematische Modell als kontinuierlich bezeichnet. Diskret heißen hingegen solche Modelle, etwa Differenzengleichungen, in denen die unabhängige Variable nur ganzzahlige Werte annehmen kann; sie sind für Phänomene geeignet, die ohnehin in festen Zeitabständen auftreten wie zum Beispiel das Schlüpfen der Maikäfer, oder dienen zur approximativen Beschreibung kontinuierlicher Vorgänge. Die große Mehrheit der wissenschaftlichen und technischen Probleme ist ihrer Natur nach kontinuierlich und die Zahl der Variablen häufig sehr groß. So sind in der Chemie, der Medikamentenforschung oder der Metallurgie oftmals die Positionen und Geschwindigkeiten einiger tausend Teilchen zu bestimmen. Besonders aufwendig wird die Berechnung, wenn die Unbekannten oder die Daten ihrerseits Funktionen sind, die nicht nur – wie bei der Planetenbewegung – von der Zeit, sondern beispielsweise noch von drei Ortskoordinaten abhängen; das ist etwa bei komplizierten Strömungsvorgängen der Fall. Zu diesen mehrdimensionalen Problemen zählen partielle Differentialgleichungen, Integralgleichungen, manche Typen linearer und nichtlinearer Optimierungsaufgaben, Mehrfachintegrale und die Oberflächenrekonstruktion. Die Komplexität kann dann sehr heftig – exponentiell – mit der Anzahl der Variablen anwachsen, so daß eine Lösung in angemessener Zeit selbst bei relativ bescheidenen Variablenzahlen nicht mehr zu garantieren ist. Zur Präzisierung betrachten wir die Berechnung eines bestimmten Integrals, das heißt der Fläche unter einer Kurve. Im Mathematikuntericht lernt man Regeln für die Umformung und – für manche Funktionen – die exakte Berechnung bestimmter Integrale. Allerdings stellen sich in der Praxis weitaus kompliziertere Aufgaben, so daß man die Integrale nur näherungsweise berechnen kann. Dazu läßt man den Computer zunächst den Wert des Integranden – der Funktion, deren Graph die zu bestimmende Fläche begrenzt – an endlich vielen Punkten im Integrationsintervall ermitteln und dann diese Werte zum Endergebnis zusammenfassen. Entsprechend teilt man die Tätigkeiten des Computers in Informations- und Kombinationsoperationen auf. Weil man den Integranden nicht an unendlich vielen Stellen auswerten kann, ist die Kenntnis über ihn stets unvollständig und das Integral bestenfalls angenähert berechenbar. Man begnügt sich deshalb mit der Forderung, daß die Abweichung zwischen Näherungs- und exakter Lösung eine gewisse Schranke (üblicherweise mit dem griechischen Buchstaben – epsilon – bezeichnet) nicht überschreiten darf. Selbst dieses bescheidenere Ziel ist ohne weitere Bedingungen nicht zu erreichen. Die Kenntnis des Integranden an zwei speziellen Punkten sagt ja nichts darüber aus, wie sich die Funktion dazwischen verhält. Die Kurve kann dort jede erdenkliche Form annehmen, also auch jede beliebige Fläche begrenzen. Um einen Fehler von höchstens e garantieren zu können, muß man zusätzlich globale Information über den Integranden einbringen. Es hilft zum Beispiel zu wissen, daß die Funktion nie steiler als mit 45 Grad steigt oder fällt.

Komplexität

Am Beispiel der Integration läßt sich nun der entscheidende Begriff der numerischen Komplexität erläutern. Sie beschreibt, wie schwer das jeweilige Problem im Prinzip ist – unabhängig von speziellen Computern oder Näherungsverfahren. Wir nehmen an, daß die Informations- und Kombinationsoperationen – das sind in der Regel Additionen, Multiplikationen und Vergleichsoperationen – gewisse Kosten verursachen. Als Maßeinheit dafür dient zum Beispiel die Zeit, die ein Computer für die jeweilige Operation braucht. Die numerische Komplexität des Integrationsproblems ist nun definiert als die Kosten, die zum Erreichen der geforderten Genauigkeit mindestens erforderlich sind. Ein Algorithmus, der damit tatsächlich auskommt, wird als optimal bezeichnet. Obgleich die numerische Komplexität einen Rechenaufwand beschreibt, ist es nicht sinnvoll, sie in Sekunden Rechenzeit anzugeben. Denn dann hinge eine solche Angabe nicht nur von dem Problem, sondern auch von dem gerade verwendeten Computer ab. Statt dessen begnügt man sich mit Aussagen darüber, wie der Aufwand von gewissen Parametern des Problems abhängt. Beispielsweise kann man beweisen, daß die numerische Komplexität des besprochenen Integrationsproblems von der Ordnung ist, das heißt ungefähr proportional dem Kehrwert der Fehlerschranke . Wenn man den Wert eines Integrals auf ein Millionstel (sechs Dezimalstellen) genau wissen will, genügt es, ungefähr eine Million Funktionswerte auszurechnen und zu einem Ergebnis zu kombinieren. Es gibt – im allgemeinen Fall – keinen effektiveren Weg. Bei nur einer unabhängigen Variablen (einer Dimension) ist der Anstieg der Komplexität noch relativ bescheiden. Wer eine Dezimalstelle mehr Genauigkeit haben – auf ein Zehntel verkleinern – will, muß auch nur zehnmal so lange rechnen. (Auf diesem Wege kommt man schließlich auch zu Abschätzungen für die Rechenzeit in Sekunden: Man läßt den Computer ein kleines Testproblem – etwa eines mit geringer Genauigkeitsforderung – lösen und rechnet mit der Formel für die Ordnung hoch.) Ist jedoch über mehrere Dimensionen zu integrieren – entsprechend der Aufgabe, das Volumen eines Gebirges über einer Grundfläche zu finden, oder Verallgemeinerungen für höhere Dimensio- nen –, steigt die numerische Komplexität exponentiell mit der Zahl d der Variablen an: Sie ist von der Ordnung . Wer ein Integral über drei Variable auf acht Stellen genau berechnen will, muß somit eine Komplexität von ungefähr bewältigen. Selbst der noch nicht existierende Teraflop-Computer mit einer Billion Operationen pro Sekunde wäre eine Billion Sekunden oder mehr als 30000 Jahre damit beschäftigt.

Differenzierbarkeit

Für die weitere Diskussion müssen wir einen zusätzlichen (ganzzahligen) Parameter r einführen. Je größer r ist, desto glatter ist die Funktion; das heißt, ihre Werte ändern sich nicht allzu plötzlich oder dramatisch. Ihr Verhalten ist deshalb bereits aus der Kenntnis relativ weniger Punkte einigermaßen kalkulierbar, weswegen man mit weniger Funktionsauswertungen auskommt. (Mathematisch ausgedrückt: Alle partiellen Ableitungen der Funktion bis zur Ordnung r einschließlich sind beschränkt.) Funktionen mit r=0 sind lediglich stetig – das können recht wilde Zackengebilde sein, aber ihr Graph ist immerhin zusammenhängend und hat keine Löcher. Solche Objekte sind keineswegs exotisch. So treten bei der mathematischen Modellierung der Brownschen Molekularbewegung an entscheidender Stelle Funktionen auf, die stetig sind (ein Teilchen springt nicht ohne Zeitverbrauch von einem Ort zum anderen), aber nirgends differenzierbar (es gibt kein noch so kleines Zeitintervall, in dem das Teilchen nicht in seiner Bahn gestört würde). Glattheit mildert ein Problem. In zahlreichen Fällen – darunter den angeführten mehrdimensionalen – hat die Komplexität die Ordnung . Gleichwohl hängt sie noch exponentiell von der Zahl der Dimensionen ab. Ist diese groß, sind derartige Probleme also schwer lösbar – oder überhaupt nicht: Zu endlichen Kosten ist noch nicht einmal eine Näherungslösung zu haben. Dieser Fall gilt beispielsweise für stetige, aber nirgends differenzierbare Funktionen. Der Glattheitsparameter r wird dann null und die numerische Komplexität unendlich. Die soeben beschriebenen Ergebnisse beziehen sich auf den schlimmsten denkbaren Fall mit deterministischen Verfahren (worst-case deterministic setting): Selbst unter den ungünstigsten Umständen – beispielsweise den wildesten Integranden – will man garantieren, daß die berechnete Lösung die vorgegebene Fehlerschranke einhält. Deterministisch bedeutet, daß die Punkte, an denen der Integrand ausgewertet wird, nicht durch Zufall, sondern nach einer festen Regel bestimmt werden. Diese wenig ermutigenden Abschätzungen beschreiben nicht den Stand der Rechentechnik, sondern die Schwierigkeit, die im Problem selbst begründet liegt. Deswegen ist es aussichtslos, sie durch Erfinden neuer Rechenmethoden umgehen zu wollen.

Stochastische Verfahren

Ein möglicher Ausweg liegt in der Einführung des Zufalls. Wir erläutern dies wieder anhand der numerischen Integration über mehrere Variable. Statt die Punkte, an denen der Integrand ausgewertet wird, nach einer starren Regel oder auf raffinierte Weise optimal auszuwählen, wirft man zu diesem Zweck – salopp gesprochen – eine Münze. Dahinter steckt die Idee, die zu integrierende Funktion als unbekanntes Wesen aufzufassen, dem man sich durch eine Anzahl von Beobachtungen nähern kann. Anstelle der Sisyphusarbeit, sich mit Messungen an den Punkten eines feinen Gitters ein vollständiges Bild verschaffen zu wollen, begnügt man sich mit Stichproben. Hochrechnungen bei Wahlen folgen demselben Prinzip. In jedem Falle ist es wichtig, bei der Auswahl der Stichproben keinem System zu folgen, welches das Ergebnis verfälschen könnte. Man kann zeigen, daß bei zufälliger Auswahl der Auswertungspunkte die numerische Komplexität des Integrationsproblems höchstens von der Ordnung 1/e2 ist. Insbesondere ist es stets berechenbar, selbst wenn der Glattheitsparameter gleich null ist. Das Standardverfahren dafür, mit dem Zufall sein Glück zu versuchen, heißt Monte-Carlo-Integration nach dem Standort der traditionsreichen Spielbank. Nicholas C. Metropolis und Stanislaw M. Ulam haben es in den vierziger Jahren eingeführt. Bei der klassischen Form des Verfahrens tastet man den Integranden an zufällig ausgewählten Punkten ab, wobei jeder Teil des Integrationsgebiets mit gleicher Wahrscheinlichkeit getroffen wird. Das arithmetische Mittel der so gewonnenen Werte dient als Approximation des Integrals. Erstaunlicherweise wird durch Einführen des Zufalls die numerische Komplexität von der Zahl der Variablen unabhängig. Mehrdimensionale Integrationsaufgaben und andere Probleme, die selbst bei optimaler deterministischer Wahl der Datenpunkte nicht oder praktisch nicht lösbar sind, werden dadurch berechenbar, daß man gerade nicht die beste, sondern irgendeine unsystematische Wahl trifft (allerdings ist für r größer als 0 die klassische Monte-Carlo-Methode nicht das optimale Verfahren; siehe Kasten auf Seite 66). Soviel Gutes bekommt man nicht umsonst - wer sich ans Roulette begibt, muß ein Risiko eingehen. In diesem Falle verliert man die absolute Garantie für das Einhalten der Fehlerschranke. Man kann nur noch sagen, daß der Fehler wahrscheinlich nicht größer als e sein wird. Das ist ähnlich einer Wahlprognose, die ja in der Regel korrekt ist, aber ab und zu dem falschen Kandidaten den Sieg vorhersagt. Auch unter den so reduzierten Genauigkeitsansprüchen ist das Zufallsprinzip kein Universalhilfsmittel. Beispielsweise zeigte 1987 Greg W. Wasilkowski an der Universität von Kentucky in Lexington, daß der Aufwand für die Oberflächenrekonstruktion dadurch nicht in erträgliche Größenordnungen absinkt. Es gibt jedoch für dieses Problem – und viele weitere – noch einen anderen Ansatz. Bei diesem neuen Prinzip muß man sich ebenfalls damit zufriedengeben, daß nur der Erwartungswert des Fehlers, aber nicht unbedingt der Fehler selbst kleiner als ist. Aber im Gegensatz zum Monte-Carlo-Verfahren faßt man nicht mehr die an zufälligen Punkten berechneten Funktionsauswertungen als Stichproben auf; vielmehr gilt die ganze Funktion – allgemeiner: der Input des Problems – als Stichprobe aus einer Grundgesamtheit. Wie in der Statistik üblich, gewinnt man Aussagen der Form, daß bei sehr vielen Stichproben – das heißt hier Lösungen desselben Problems mit verschiedenen Daten – der Fehler im Mittel kleiner ist als und einer gewissen Wahrscheinlichkeitsverteilung folgt. Daraus läßt sich auch ableiten, mit welcher Wahrscheinlichkeit die im konkreten Fall vorliegende Funktion zu den wenigen widerspenstigen gehört, bei denen das Verfahren die Fehlerschranke nicht einhält. Dieses Szenario des typischen Falles (average-case setting) setzt voraus, daß man über die Gutartigkeit der Eingabedaten zumindest im Durchschnitt gewisse Aussagen machen kann. Man muß angeben können, welche Arten von Eingabefunktionen typischerweise auftreten. Das mathematische Hilfsmittel dafür sind Wahrscheinlichkeitsverteilungen. Die gebräuchlichsten sind die glockenförmige Gauß-Verteilung und speziell Wiener-Verteilungen; das sind Verallgemeinerungen der Gauß-Verteilung auf Räume von Funktionen, die insbesondere die erwähnten Darstellungen der Brownschen Bewegung enthalten. Man weiß zwar seit den sechziger Jahren, daß mehrdimensionale Integrale in diesem Sinne berechenbar sind, aber der Beweis war nicht konstruktiv: Er lieferte weder eine Anweisung für die optimale Wahl der Auswertungspunkte noch ei-nen optimalen Kombinationsalgorithmus oder auch nur eine Abschätzung für die mittlere numerische Komplexität. Versuche, mit Konzepten aus anderen Bereichen der Numerik diese Unbekannten zu bestimmen, schlugen fehl. Die naheliegende und häufig angewandte Idee, die Auswertungspunkte schachbrettförmig über das Integrationsgebiet zu legen, ist nämlich eine denkbar schlechte Wahl für den typischen Fall. Das hat Donald Ylvisaker von der Universität von Kalifornien in Los Angeles 1975 bewiesen; Wasilkowski und Anargyros Papageorgiou, damals Doktorand an der Columbia-Universität in New York, konnten 1990 das Resultat noch verallgemeinern. Die Lösung des Problems fand schließlich einer von uns (Wo´zniakowski) im Jahre 1991. Ein entscheidender Hinweis kam, wie es häufiger geschieht, von einer weit entfernten Disziplin der Mathematik: der Zahlentheorie. Dabei lieferten die Arbeiten von Klaus Roth vom Imperial College in London einen Teil des Schlüssels. Ein weiterer Teil stammt von Wasilkowski.

Komplexität im Durchschnitt

Schauen wir uns die Resultate etwas genauer an. Nehmen wir an, der Glattheitsparameter sei null – wir untersuchen also ein Problem, für das eine garantiert korrekte Lösung nicht berechenbar ist – und der Integrand entstamme einer Grundgesamtheit mit Wiener-Verteilung. Unter diesen Voraussetzungen ist die mittlere numerische Komplexität im wesentlichen umgekehrt proportional zur Fehlerschranke (also von der Ordnung ; genaue Angaben finden sich im Kasten unten). Dies ist bei kleinem - hoher Genauigkeitsforderung – eine deutliche Verbesserung gegenüber der klassischen Monte-Carlo-Methode, bei der die Kosten von der Ordnung sind. Bei dem zugehörigen Verfahren sind die Auswertungspunkte für den Integranden nach einer deterministischen Regel zu wählen. Am besten geeignet sind die sogenannten Hammersley- oder die hyperbolischen Kreuzungspunkte (Bild 2). Ist auch die Rekonstruktion von Oberflächen im typischen Falle durchführbar? Die Antwort ist besonders interessant, weil – wie erwähnt – Monte-Carlo-Methoden hier nicht weiterhelfen. Unter denselben Voraussetzungen wie oben konnten wir zeigen, daß die mittlere numerische Komplexität der Oberflächenrekonstruktion von der Ordnung ist, und damit die Frage positiv beantworten. Abermals stellen sich hyperbolische Kreuzungspunkte als optimal heraus. Gegenwärtig untersuchen wir, ob diese bisher theoretischen Ergebnisse sich in die Praxis umsetzen lassen. Spassimir Paskov, Doktorand an der Columbia-Universität, entwickelt Software, um die neuen deterministischen Methoden mit Monte-Carlo-Methoden zu vergleichen. Erste Befunde zu Problemen der Wirtschaftswissenschaften sind ermutigend. Damit ist es uns gelungen, das Anwachsen der Komplexität mit verschärfter Genauigkeitsforderung auf ein erträgliches Maß zu mildern. Es bleibt die Abhängigkeit von der Anzahl d der Variablen; sie wird durch die Vorfaktoren und (Kasten unten) beschrieben. Diese Zahlen können für große d ebenfalls sehr groß werden. Bislang sind gute theoretische Abschätzungen dafür nicht bekannt und wahrscheinlich auch sehr schwer zu finden. Man würde sich wünschen, daß die Zahl der zur Lösung des Problems benötigten Funktionsauswertungen unabhängig von der Zahl der Variablen wäre, also nur von einer Potenz von abhinge. Solche Probleme bezeichnet man als stark berechenbar. Eigentlich war gar nicht zu hoffen, daß es so etwas Angenehmes überhaupt gibt; aber im vergangenen Jahr konnte einer von uns (Wo´zniakowski) zeigen, daß sowohl mehrdimensionale Integrale als auch die Oberflächenrekonstruktion im typischen Falle stark berechenbar sind. Damit wissen wir zwar, daß es Abtastpunkte und einen Kombinationsalgorithmus geben muß, mittels deren die Integration und die Oberflächenrekonstruktion im Mittel stark berechenbar werden; doch gibt uns der dazugehörige Beweis die Punkte und Algorithmen nicht an. Hier gibt es noch viel zu tun.

Grenzen der Berechenbarkeit

Fassen wir zusammen. Im Szenario des schlimmsten denkbaren Falles wächst die numerische Komplexität vieler Probleme mit kontinuierlichen Variablen exponentiell mit der Zahl dieser Variablen. Man vermutet, daß das im wesentlichen auch für diskrete Probleme gilt (Kasten Seite 69). Zwar bieten Monte-Carlo-Methoden oder die gemilderte Forderung nach Korrektheit im Mittel häufig Abhilfe; andere Aufgaben bleiben jedoch nachweislich hartnäckig.

Wahrscheinlich laufen einige Grundlagenprobleme der Physik und andere, die man Supercomputern anzuvertrauen pflegt, auf Probleme dieses Typs hinaus. Typischerweise enthalten sie eine große Zahl von Variablen. Außerdem kommen in manchen physikalischen Problemen Berechnungen von sogenannten Pfadintegralen vor. Das sind Integrale mit unendlich vielen Dimensionen; will man sie näherungsweise berechnen, muß man zumindest über viele Dimensionen integrieren. Trotz unserer Ergebnisse kann einen das Gesamtbild also nicht besonders optimistisch stimmen.

Es gibt noch andere Grenzen der Berechenbarkeit, von denen hier nicht die Rede sein soll. Sie liegen in der empfindlichen Abhängigkeit eines Systemverhaltens von den Anfangsdaten und werden üblicherweise mit dem Stichwort "Chaos" gekennzeichnet (Spektrum der Wissenschaft, November 1993, Seite 46, und Januar 1994, Seite 72).

Die genannten Ergebnisse veranlaßten einen von uns (Traub) zum Weiterdenken. Es könnte sein, daß es auf bestimmte wissenschaftliche Fragen zwar eine Antwort gibt, daß es jedoch absolut unmöglich ist, sie zu finden. Möglicherweise kann man nämlich beweisen, daß die dafür erforderlichen Ressourcen an Zeit, Speicherkapazität und Energie im Prinzip nicht verfügbar sind – selbst wenn man das ganze Weltall in einen Computer verwandeln könnte.

Die mathematische Forschung der letzten 60 Jahre hat die wichtige Erkenntnis erbracht, daß gewisse Probleme unentscheidbar, unberechenbar oder zumindest praktisch unberechenbar sein können. Der österreichische Logiker Kurt Gödel (1906 bis 1978) bewies die erste dieser drei Aussagen: Ein hinreichend reichhaltiges mathematisches System, etwa die Arithmetik, enthält wahre Aussagen, die innerhalb des Systems nicht bewiesen werden können. Nach unserer Überzeugung ist es nun an der Zeit, ein physikalisches Äquivalent des Gödelschen Satzes zu formulieren.

Die mathematischen Ergebnisse, die wir bislang umrissen haben, reichen dafür noch nicht aus. Denn naturwissenschaftliche Fragen – ob das Universum irgendwann aufhören wird zu expandieren, oder wie hoch im Jahr 2010 die mittlere Erdtemperatur sein wird – werden nicht automatisch mit einer mathematischen Formulierung geliefert: Zu ein und demselben Gegenstand der Forschung kann es zahlreiche mathematische Modelle geben, die alle das Wesentliche wiedergeben. Weil nun Aussagen zur Berechenbareit sich stets nur auf ein solches Modell beziehen können, ist es denkbar, daß man für eine vermeintlich unbeantwortbare physikalische Frage nur ein ungeschicktes Modell gewählt hat und ein anderes durchaus eine Antwort liefern würde. Will man also zeigen, daß eine physikalische Frage im Prinzip unbeantwortbar ist, müßte man beweisen, daß jede mathematische Formulierung, die das Wesentliche der Fragestellung erfaßt, auf ein nichtberechenbares Problem hinauslaufen muß. Das wäre ein physikalisches Äquivalent des Gödelschen Satzes.

Die Grenzen der Erkenntnis beschäftigen uns Menschen seit jeher. Aktuelle mathematische Forschung hat diese zwar an einer Stelle ein wenig hinausgeschoben; gleichzeitig sind jedoch Grenzen ins Blickfeld geraten, die sich aller Voraussicht nach als unüberwindlich herausstellen werden.

Joseph F. Traub und Henryk Wo´zniakowski arbeiten seit 1973 zusammen. Traub, der früher die Informatik-Abteilung der Carnegie-Mellon-Universität in Pittsburgh (Pennsylvania) leitete, ist gegenwärtig Professor im Fachbereich Informatik der Columbia-Universiät in New York. Er war Gründungsvorsitzender der Klasse für Computerwissenschaften und Telekommunikation der amerikanischen Nationalen Akademie der Wissenschaften. Seine grundlegenden Forschungen über Informationskomplexität begann er 1959. Er bedankt sich bei Forschern des Santa-Fe-Instituts für zahlreiche anregende Diskussionen über die Grenzen wissenschaftlicher Erkenntnis. Wo´zniakowski ist Professor sowohl an der Universität von Warschau als auch an der Columbia-Universität. In Warschau leitete er den Fachbereich für Mathematik, Informatik und Mechanik und war örtlicher Vorsitzender der Gewerkschaft Solidarno´s´c. Die Autoren danken der amerikanischen Forschungsgemeinschaft National Science Foundation und dem Büro für wissenschaftliche Forschung der amerikanischen Luftwaffe für Forschungsförderung.

Literaturhinweise

- Information-Based Complexity. Von E. W. Packel und J. F. Traub in: Nature, Band 328, Heft 6125, Seiten 29 bis 33, 2. Juli 1987. – Information-Based Complexity. Von J. F. Traub, G. W. Wasilkowski und H. Wo´zniakowski. Academic Press, 1988. – Average Case Complexity of Multivariate Integration. Von H. Wo´zniakowski in: Bulletin of the American Mathematical Society, Band 24, Heft 1, Seiten 185 bis 194, Januar 1991. – The Computational Complexity of Differential and Integral Equations: An Information-Based Approach. Von Arthur G. Werschulz. Oxford University Press, 1991. – Theory and Applications of Information-Based Complexity. Von J. F. Traub und H. Wo´zniakowski in: 1990 Lectures in Complex Systems, Santa Fe Institute. Herausgegeben von Lynn Nadel und Daniel K. Stein. Addison-Wesley, 1991. – What Is Scientifically Knowable? Von J. F. Traub in: Carnegie Mellon University Computer Science: A 25th Anniversary Commemorative. Herausgegeben von Richard F. Rashid. Addison-Wesley, 1991. –


Aus: Spektrum der Wissenschaft 4 / 1994, Seite 64
© Spektrum der Wissenschaft Verlagsgesellschaft mbH