Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

Der Rechner kann Amok laufen, bevor es überhaupt jemand merkt:


31.03.1989 - 

Mathematische Probleme machen dem Computer zu schaffen

Der gewiefte Computeranwender durchforstet seine Formeln nach heiklen Operationen, bevor er eine einzige Zeile Code schreibt. Dann legt er das Programm so aus, daß möglichst wenige kritische Situationen auftreten und aus der Maschine ein Maximum an Rechengenauigkeit herausgepreßt wird. Zwei Beispiele zeigen, was gemeint ist:

1) Die Formel lautet [(a/b) - (c/d)] x e. Je nach den Zahlenwerten, die eingesetzt werden, liefert der Computer ein vernünftiges Resultat oder baren Unsinn. Nehmen wir

[(4,08/1200) - (0,135/50)] x 4000.

Auf dem Papier erhalten wir dafür

[0,0034 - 0,0027]x4000 = 2,8.

Wenn sich der Programmierer nichts denkt, tippt er die Formel telquel in den Computer ein. Die Maschine rechnet dann

[0,003 - 0,003] x4000 = 0!

Hätte er zum voraus überlegt, daß bei solchen Zahlen Auslöschung eintritt, wäre er wohl auf die Formel (a x e)/b - (c x e)/d gestoßen.

Damit hätte er nämlich auch auf dem Computer Erfolg:

16320/1200 - 540/50= 2,8.

2) Für die Auflösung der quadratischen Gleichung x2 - 56x + 1= 0 mit der klassischen Formel liefert der Computer die Wurzeln

x1= 28 + Wurzel 783 = 55,982 +/- 0,0005

x2= 28 - Wurzel 783 = 0,018 +/- 0,0005

Mit dem Ergebnis der ersten Wurzel darf der Programmierer zufrieden sein: mehr als die fünf Ziffern kann er auf seiner Maschine nicht kriegen. Aber die zweite Wurzel mit ihren zwei Ziffern (führende Nullen nicht gezählt) stellt nicht das Optimum dar, das er herausholen kann. Er könnte sich nämlich für die Berechnung dieser Zahl folgende Eigenschaft der Wurzeln quadratischer Gleichungen zunutze machen: x1 x X2 = 1.

Also berechnet er bloß die unkritische Wurzel x, nach der herkömmlichen Methode; für die Bestimmung von X2 verwendet er die Formel x2 = 1/x1. Das Maximum an Genauigkeit holt er heraus mit

1000 x X2 = 1000/x1

Mit x1= 55,982 ergibt sich dann X2 = 0,017863. Obschon der Computer bloß auf drei Nachkommastellen genau rechnet, hat der Benutzer aus ihm ein l000 mal genaueres Resultat herausgepreßt!

Computer können also wirklich schlechte Rechner sein, wenn man innen Gelegenheit dazu gibt. Diese Erkenntnis hat in den letzten Jahren zur Entwicklung von ganz neuen Algorithmen (Rechenvorschriften) geführt. Wer seinen Rechner nach diesen programmiert, kann darauf zählen, daß die Resultate richtig sind - wobei "richtig" bedeutet, daß es keine andere vom Computer darstellbare Zahl gibt, die dem mathematisch e exakten Ergebnis näher kommt.

In den neu gefundenen Algorithmen steckt aber noch mehr: Gleichzeitig mit dem Resultat liefern sie auch den Beweis, daß für die fragliche Rechnung überhaupt eine Lösung existiert - was in der Mathematik alles andere als selbstverständlich ist. Aber darauf kommen wir weiter unten noch zu sprechen.

Notfalls ein Lösungsintervall suchen

Hat man den Computer mit "unscharfen" Eingabedaten gefüttert (zum Beispiel mit ungenauen physikalischen Meßwerten), so liefert er aIs Resultat zwei Zahlen, zwischen denen das Ergebnis mit Sicherheit liegt. Dieses Lösungsintervall ist zugleich das engste, das überhaupt in Frage kommt.

Der Wunsch nach zuverlässigen Rechenverfahren ist natürlich nicht neu. Es gab auch früher schon welche, mit denen man versuchte, Grenzen anzugeben, innerhalb denen die wahre Lösung sicher liegen muß (sogenannte Intervall-Arithmetik). Daß das nicht einfach ist, zeigt das folgende Beispiel aus der mathematischen Literatur:

Ein sehr präzise und korrekt arbeitender Computer bearbeitete ein bestimmtes Rechenproblem auf zwei Arten. Die herkömmliche Intervall-Arithmetik lieferte die Grenzwerte 250 000 und 500 000 - irgendwo dazwischen mußte also die richtige Lösung liegen. Beim Versuch, das Ergebnis mit dem Standard-Verfahren direkt zu berechnen, kam aber eine Zahl heraus, die weit außerhalb des Intervalls lag: 166 666,66. Tatsächlich war das mathematisch korrekte Resultat 470 832,00. Die neue Rechentechnik lieferte es exakt. - und zwar auf dem gleichen Computer!

Solche Geschichten stimmen nachdenklich: Wie oft, fragt man sich unwillkürlich, haben sich die Computer in ihrer rund 40jährigen Geschichte wohl schon geirrt, ohne daß es die Benutzer merkten?

Leider, muß man annehmen, sehr oft. Manchmal liefern die elektronischen Superkönner sogar dann noch Resultate, wenn in Wirklichkeit gar keine existieren: Bei Gleichungen, die keine Lösung haben, gaukelt der Rechner halt gerne mal eine vor. Schuld daran sind nicht etwa Programmierfehler oder die eingangs erwähnten Rundungsfehler, sondern einzig und allein die ungünstig gewählte Rechenmethode. Denn das Malheur tritt auch dann auf, wenn bei der maschineninternen Verarbeitung alles koscher zugeht.

Mit den neuen Algorithmen ist man gegen solche Unbill gefeit: Wenn es keine Lösung gibt, merkt das der Computer und teilt seine Erkenntnis dem Benutzer mit.

Compiler sind eine Art Nadelöhr

Seit einiger Zeit verwenden Spezialisten solche Verfahren, um die computerinternen Compilerprogramme zu überprüfen. Compiler dienen dazu, um die .,normalen" Programme, die der Benutzer auf der Tastatur eingibt, in die Maschinensprache zu übersetzen - also in eine kompakte und für die elektronischen Schaltungen lesbare Form.

Die Untersuchungen haben gezeigt, daß auch Compilerprogramme, die im Computer eine Art Nadelöhr sind, wo alles durch muß, nicht unfehlbar sind. Aufgedeckt wurde das, als selbst einer der neuen, angeblich zuverlässigen Algorithmen ein falsches Rechenresultat produzierte. Die Suche ergab, daß der Fehler im Compiler lag: Er hatte einen falschen Maschinencode erzeugt.

Mit der neuen Technik kommen also jetzt langsam Fehler zum Vorschein, die man in der Vergangenheit gemacht hat; es werden aber auch Tücken offengelegt, die überhaupt in der Computerei stecken. Das hat aus zwei Gründen sein Gutes: Erstens einmal kann man erkannte Fehler korrigieren, und zweitens mindert die Erkenntnis, daß auch Computer nicht a priori unfehlbar sind, die Zahl jener, die der seelenlosen Maschine blindes Vertrauen schenken.

Computer sind prinzipiell beschränkt

Bis jetzt war nur von technischen Fehlern und methodischen Irrtümern die Rede, die den Rechner daran hindern, eine perfekte Maschine zu sein. Nun soll auch noch die letzte Bastion fallen, denn wir behaupten: Der Computer mag zwar ein schneller Rechner sein, aber ein mathematischer Alleskönner ist er nicht - ganz egal, wie leistungsfähig und genial programmiert er ist.

Mit Bestimmtheit kann man das deshalb sagen, weil es mathematische Probleme gibt, an denen jeder Computer scheitern muß. Eines der anschaulichsten hat der brillante deutsche Mathematiker David Hilbert im August 1900 an einem denkwürdigen Kongreß in Paris gestellt.

Eigentlich ist Hilberts Problem Nummer 10 - der Göttinger Professor präsentierte noch 22 weitere mathematische Knacknüsse - viel älter, stammt es doch ursprünglich aus der Zeit um 250 a.d. Damals lebte in Alexandrien ein Mathematiker namens Diophant, dessen Leidenschaft den algebraischen Gleichungen galt - insbesondere jenen, die ganzzahlige Lösungen haben.

Wie man algebraische Gleichungen behandelt, lernt man in der Schule, wo zumindest lineare, manchmal auch quadratische Gleichungen zum Pflichtstoff gehören. Eine lineare algebraische Gleichung wie

4x+5=0

zu lösen, ist simpel: x = - 5/4.

Quadratische Gleichungen wie x2 - 4x - 5 = 0

haben zwei Lösungen; für sie gibt es eine Formel, die in unserem Fall wie folgt aussieht:

X1,2=4/2 + Wurzel (4/2)2 + 5

Hier ist also x1=5 und X2= - 1.

Lösungen mit Formeln zu finden, ist eine reine Fleißarbeit. Solche Formeln existieren für Gleichungen in einer Unbekannten bis zum vierten Grad. Bei zwei oder mehr Unbekannten wird die Sache aber wesentlich komplizierter: Solche Gleichungen haben sehr viel mehr Lösungen. Diophant und Hilbert ging es nun darum, daraus die ganzzahligen herauszupicken.

David Hilbert suchte ganzzahlige Lösungen

Zur Veranschaulichung ein Beispiel: Die Gleichung X 2 + y 2 = 2 hat unendlich viele Lösungen, von denen aber lediglich vier ganzzahlig sind: X1,2= +1 und y1,2 = + 1. Eine kleine Änderung, und die Situation präsentiert sich völlig neu: Stände auf der rechten Seite des Gleichheitszeichens statt der 2 eine 3, so hätte die Gleichung überhaupt keine ganzzahlige Lösung.

Die Gleichung x 2= 2y 4 - 1 hat nur zwei ganzzahlige Lösungen. Eine findet man sofort durch Probieren:

x1 = 1, y1= 1. Die zweite fände ein auf Lösungssuche geschickter Computer relativ leicht. Sie lautet

x2= 239, y2 = 1 3.

Obschon ganze Zahlen für den Computer ideale Größen sind, haben die elektronischen Rechner Mühe, bei solchen Gleichungen die ganzzahligen Lösungen herauszufinden. In Anbetracht der Gleichung

x2 + y2 = 3, die überhaupt keine ganzzahlige Lösung hat, verwundert das auch nicht.

Die Frage ist natürlich, ob der Computer merkt, daß diese Gleichung keine ganzzahlige Lösung hat, oder ob er einfach stur sucht und sucht, bis ihn jemand von seinem aussichtslosen Vorgehen abhält und stoppt. Das ist im Prinzip das Problem, das Hilbert damals am Pariser Kongreß präsentierte.

Da es im Jahre 1900 noch keine Computer gab, wie wir sie heute kennen, stellte Hilbert seine Frage ein wenig anders: "Gibt es einen Algorithmus, mit dem man Schritt für Schritt entscheiden kann, ob eine Gleichung mit ganzzahligen Koeffizienten auch ganzzahlige Lösungen hat oder nicht?"

Der Link zur Computerei ist natürlich der, daß man einen solchen Algorithmus auf dem Rechner programmieren und die Aufgabe der Maschine überantworten könnte.

An Hilberts Problem Nummer 10 bissen sich die besten Mathematiker die Zähne aus - vergeblich. Erst 1970 konnte der 22jährige Russe Yuri Matyasevich beweisen, daß es keinen solchen Algorithmus gibt. Fazit: Kein Computer wird je entscheiden können, ob eine bestimmte algebraische Gleichung mit ganzzahligen Koeffizienten auch ganzzahlige Lösungen hat oder nicht.

Witzig an der Sache ist, daß Matyasevich für den Beweis, daß Computer keine allmächtigen Rechner sind, auf eine frühere Arbeit des Mathematikers Alan Turing zurückgriff - jenes Alan Turing, der als einer der Pioniere des modernen Computers in die Geschichte einging.

Quelle: Die Zahlenbeispiele im letzten Kapitel stammen von Keith Devlin (Computer Guardian)