Dr. rer. nat.

Einiges über Computeralgebrasysteme und ihre Grenzen

Viele von uns kennen diverse Computeralgebrasysteme (im Folgenden CAS genannt) oder haben sogar bereits mit diesen gearbeitet.  Und natürlich sind dem einen oder anderen von uns bereits Dinge aufgefallen, die ein Computeralgebrasystem nicht bewältigen kann. Außerdem unterscheiden sich alle Computeralgebrasysteme in diesem Gesichtspunkt: die einen können beispielsweise bestimmte Arten von Integralen berechnen, die anderen können das nicht. Dafür können die anderen Computeralgebrasysteme Integrale berechnen, die unseres nicht kann.

Der Grund dafür lässt sich (relativ) leicht erklären. Viele Probleme in der Mathematik sind leider unentscheidbar. Unentscheidbar bedeutet hierbei, dass es keinen Algorithmus gibt (und geben kann), welcher auf dieses Problem immer eine korrekte Lösung ermittelt, wenn es denn eine gibt. Dazu gehört beispielsweise die Fragestellung, ob ein gewisser Ausdruck A (welcher von einer oder mehreren Unbestimmten abhängen kann), identisch 0 ist, wenn A zu einer „hinreichend komplizierten“ Funktionenklasse gehört (s. Satz von Richardson). Betrachten wir mal ein Beispiel: Jeder wird mir mit Sicherheit zustimmen können, dass der Ausdruck 8/4-2 gleich 0 ist. Andererseits ist es ein wenig schwieriger nachzuweisen, dass die folgenden Ausdrücke gleich 0 sind:

(-7+501/2)1/3 + (-7-501/2)1/3 – 2   oder   (5042+2911·31/2)1/7 – (89·31/2+109·21/2)1/5 + (8119+5741·21/2)1/11 – 3.

Die Unentscheidbarkeit dieses Problems für den Allgemeinfall verhindert leider beispielsweise auch, dass der Risch-Algorithmus (ein Algorithmus, welcher für eine elementare Funktion f entscheidet, ob diese eine elementare Stammfunktion F besitzt) zu einen echten Algorithmus wird. Der Risch-Algorithmus ist nur ein Semi-Algorithmus, denn in einem der Schritte stößt man auch das Problem, dass man entscheiden muss, ob ein bestimmter Ausdruck identisch 0 ist. Besteht die Ausgangsfunktion f dagegen nur aus transzendenten Funktionen, so ist der Risch-Algorithmus in diesem Fall ein echter Algorithmus. Insbesondere bedeutet das, dass kein CAS der Welt für alle Funktionen, welche algebraische Teilausdrücke enthalten, stets Stammfunktionen angeben kann, wenn diese in geschlossener Form durch elementare Funktionen ausgedrückt werden können.

Diese Betrachtungen lassen insbesondere die folgenden Schlüsse zu:

  • Kein CAS wird jemals alle Integrale elementarer Funktionen ermitteln können, welche sich in geschlossener Form durch elementare Funktionen ausdrücken lassen.
  • Kein CAS wird jemals alle Gleichungen (geschweige denn Gleichungssysteme) lösen können, bei denen sich die Lösungen mittels elementarer Funktionen aus den Ausgangsdaten darstellen lassen.
  • Kein CAS wird jemals alle Differentialgleichungen lösen können, bei denen sich die Lösung in geschlosener Form durch elementare Funktionen darstellen lässt.

Der entscheidende Aspekt, welcher über die Qualität eines CAS entscheidet, ist also nicht die Antwort auf die Frage, ob es alle Aufgaben einer bestimmten Sorte bewältigen kann, sondern, dass es möglichst viele Algorithmen beherrscht, welche den Großteil der relevanten Fälle abdecken. Dazu gehören neben diversen Standardalgorithmen, welche in einem modernen CAS implementiert sein müssen, auch diverse heuristische Algorithmen, die „mit cleveren Tricks“ auch schwirige Fälle abdecken können.

Insofern, liebe Nutzer, müsst ihr ein wenig Nachsicht haben, wenn das eine oder andere Ergebnis nicht die optimale Form besitzt oder ein wenig ungeschickt ausgedrückt wird. Denn eine „Standardform“ für allgemeine Ausdrücke kann es den obigen Betrachtungen leider nicht geben.