Die Entwicklung des Computers seit seiner Konzipierung durch den Mathematiker von Neumann vor mehr als 40 Jahren ist, oberflächlich betrachtet, in der Tat beeindruckend und wird nicht ganz zu Unrecht als eine technologische Revolution bezeichnet. Computer, die einst aus etwa 10 000 Röhren, den heute schon fast vergessenen Vorgängern von Transistoren, aufgebaut waren und mehr als 100 Quadratmeter Stellfläche beanspruchten, können derzeit bequem auf einer Platine von der Größe einer DIN-A5-Seite, bestückt mit einigen hochintegrierten Halbleiterbauelementen, untergebracht werden. Es Ist in erster Linie diesem enormen Fortschritt bei der Herstellung hochintegrierter, zuverlässiger und billiger Bauelemente zu verdanken, daß Computer aller Preis- und Leistungsklassen aus unserem Alltag nicht mehr wegzudenken sind. Sie erbringen eine Vielzahl von Dienstleistungen, steuern Industrieanlagen, Verkehrssysteme und Kraftwerke, helfen Wissenschaftlern und Ingenieuren bei der Lösung hochkomplexer Problemstellungen und erschließen völlig neue Möglichkeiten in der Forschung und Technikanwendung: leider auch auf so bedenklichen Gebieten wie der Militärtechnik. Nicht zuletzt sind sie auch ein faszinierendes, Intuition und Kombinationstalent herausforderndes Spielzeug.
Der zum Teil verständliche Enthusiasmus über die offenbar unbegrenzten Einsatzmöglichkeiten hat nicht nur bei Laien dazu geführt, Computern so anspruchsvolle Eigenschaften wie Intelligenz, Unfehlbarkeit und Zuverlässigkeit. zu unterstellen. Leider sind sie davon viel weiter entfernt, als es selbst mancher "Computerexperte" eingestehen mag.
Sämtliche heute im Einsatz befindlich beziehungsweise am Markt erhältlichen Computer sind zwar technologisch außerordentlich hochentwickelte Geräte. Allerdings beruhen sie auf einem reichlich primitiven
Arbeitsprinzip, das sich seit den Anfängen vor mehr als 40 Jahren nicht gewandelt oder wenigstens merklich
weiterentwickelt hat. Dieses Arbeitsprinzip degradiert den Computer zu einem Instrument von bemitleidenswerter Hilflosigkeit, dessen einzige, allerdings überragende Fähigkeit darin besteht, außerordentlich komplexe Berechnungen, Entscheidungsprozesse oder Such- beziehungsweise Sortiervorgänge in großen Datenbeständen mit fantastischer Geschwindigkeit abzuwickeln. Dies setzt allerdings voraus, daß dem Computer ein sehr detaillierter Arbeitsablaufplan, auch Programm genannt, zur Verfügung gestellt wird, der in kleinsten Schritten vorschreibt, wie eine bestimmte Problemstellung mit Hilfe des vorgegebenen Arbeitsprinzips zu lösen ist.
Um diese Ablaufplanung zu verdeutlichen, betrachten wir ein einfaches Basic-Programm zur Multiplikation aller ganzen Zahlen zwischen 1 und einer beliebigen ganzen Zahl N, die im vorliegenden Fall 9 sein soll. Für das Programm ist bewußt eine etwas unelegante Form gewählt worden, die jedoch ziemlich genau die Arbeitsweise eines Computers auf der Hardware-Ebene widerspiegelt.
100 READ(N)
200 LET R = 1
300 N = N - 1
400 R = R * N
500 IF N > 1 THEN 300
600 PRINT(R)
700 DATA 9
Dieses Programm verwendet zwei Namen, R und N, die - nicht sehr zutreffend - auch Variable genannt werden. Die Namen bezeichnen Zellen eines Speichers, deren Inhalte Zahlenwerte darstellen sollen. Die Marken 100, 200 ..., 700 bezeichnen aufeinanderfolgende Zellen desselben Speichers, deren Inhalte die rechts neben den Marken stehenden Befehle sind. Dem Computer unterliegt ein einfacher Steuerungsmechanismus, der die Befehlszellen sequentiell durchläuft und die darin enthaltenen Befehle ausführt. Die Ausführungsreihenfolge wird demnach durch die Aufschreibungsreihenfolge festgelegt. Abweichungen von dieser sequentiellen Abfolge werden durch Steuerbefehle bewerkstelligt, die in Abhängigkeit von dem Wert einer Bedingung (der Eins oder Null ist) den Steuerungsmechanismus an einer explizit angegebenen Marke fortfahren lassen.
Der Befehl 500 in unserem Beispielprogramm bewirkt einen Rücksprung nach dem Befehl 300, solange der in der Zelle N abgespeicherte Zahlenwert größer 1 ist, andernfalls eine Fortsetzung der Programmausführung mit dem Befehl 600.
Alle übrigen Befehle des Programms sind Vorschriften darüber wie mit den Inhalten der durch Namen bezeichneten Speicherzellen zu verfahren ist. Grundsätzlich bedeutet das Auftreten eines Namens auf der rechten Seite des "="-Zeichens daß von dem Inhalt der bezeichneten Zelle eine Kopie gezogen werden soll; das Auftreten eines Namens auf der linken Seite des "="-Zeichens bedeutet, daß der Inhalt der bezeichneten Zelle mit dem Resultat der auf
der rechten Seite vorgeschriebenen, auf die kopierten Werte anzuwendenden Rechenoperation überschrieben werden soll.
Der Befehl 400 unseres Programmes bewirkt demnach folgendes: Von den in den Zellen N und R enthaltenen Zahlenwerten werden Kopien hergestellt (ohne die Zellinhalte dabei zu verändern), die kopierten Zahlenwerte werden miteinander multipliziert, und mit dem Resultat der Multiplikation wird der Inhalt der Zelle R überschrieben (das heißt der bisherige Inhalt wird zerstört).
Schon dieses sehr einfache Beispiel zeigt, daß ein Programmierer offenbar weniger damit beschäftigt ist, festzulegen, was berechnet werden soll, als vielmehr damit, wie die Berechnung auf dem Computer zu organisieren ist. Dies betrifft sowohl die Festlegung von Befehlsfolgen als auch die Verwaltung der Zellinhalte.
Über Namen können Bezüge zwischen Befehlen einerseits und Zellinhalten andererseits völlig freizügig hergestellt werden. Insbesondere ist es zulässig, innerhalb eines Programms einen Namen beliebig oft sowohl auf der linken als auch auf der rechten Seite von Befehlen zu verwenden, das heißt, den Zellinhalt beliebig oder zu überschreiben oder zu kopieren. Der Inhalt einer Zelle kann deshalb durch eine Vielzahl möglicher Befehlsfolgen kopiert oder verändert werden. Die Bedeutung eines aktuell vorliegenden Zellinhalts läßt sich demnach nur aus der genauen Kenntnis der tatsächlich ausgeführten Befehlsfolge erschließen.
Die sorgfältige Planung der Zellbelegungen, das heißt die Verwendung von Namen in Abhängigkeit von möglicherweise sehr vielen alternativen Befehlsfolgen bildet deshalb das schwierigste organisatorische Problem bei der Entwicklung größerer Programme. Selbst bei Einhaltung strikter Regeln wird über die Folgeabhängigkeit der Zellbelegungen ein Programm mit einem weitverzweigten Netz von Ursachen und Wirkungen überzogen, das nicht mehr durchschaubar ist. Die dadurch hervorgerufenen, meist unbeabsichtigten Nebenwirkungen sind verantwortlich für tückische, vielfach unerkannt bleibende Fehler, die große Unsicherheit über die Korrektheit von Programmen hervorrufen.
Angesichts dieser in dem primitiven Arbeitsprinzip begründeten Schwächen drängt sich die Frage auf, ob Computer nicht so konzipiert und konstruiert werden können, daß sie tatsächlich Probleme lösen, statt ein neues zu schaffen, nämlich das der Programmierung. Dem Benutzer kann es selbstverständlich nicht erspart bleiben, in einer dem Computer verständlichen Sprache vollständig zu beschreiben, was berechnet werden soll. Diese Beschreibung muß natürlich so geordnet oder strukturiert sein, daß daraus der Arbeitsplan für die Problemlösung, das heißt, wie gerecht werden soll, unmittelbar hergeleitet werden kann. Es ist naheliegend, einen solchen in der Problembeschreibung indirekt enthaltenen Arbeitsplan maschinell zu nutzen.
Die konsequente Verwirklichung dieser Idee findet sich in sogenannten Reduktionssystemen, in denen der stupide Befehlsgehorsam traditioneller Computer durch ein streng mathematischer Arbeitsprinzip ersetzt wird, so wie es etwa aus der Algebra bekannt ist. Die Problemdarstellung erfolgt in der Form wohlstrukturierter mathematischer Ausdrücke, wie sie zum Beispiel für die Formulierung arithmetischer Berechnungen verwendet werden. Aus der Struktur dieser Ausdrücke, die unter anderem durch Verklammerungen vorgegeben ist, leitet der Verarbeitungsmechanismus mit Hilfe eines einfachen Traversierschemas und durch systematische Anwendung von wenigen Umformungsregeln die Berechnungsabläufe selbständig her.
Zur Erläuterung dieses Arbeitsprinzips greifen wir auf das Beispiel der Multiplikation aller ganzen Zahlen von 1 bis N = 9 zurück. Diese Berechnung kann zum Beispiel durch den Ausdruck
apply rec FAC sub N in
if (N > 1)
then (N*apply FAC to (N - 1))
else 1
to 9
formal beschrieben und dem System über einen Bildschirm eingegeben werden. Dieser sehr einfache Ausdruck enthält bereits alle wesentlichen Elemente der für die Programmierung zu verwendenden Reduktionssprache.
Systemintern wird der Ausdruck in Form einer sich zweifach verzweigenden Baumstruktur dargestellt, wie sie in Abb. 1 a zu sehen ist.
Diese Baumstruktur wird gebildet aus Verzweigungsknoten, denen jeweils ein linker und ein rechter Teilbaum nachfolgen, sowie aus Endknoten, denen keine Teilbäume nachfolgen. Alle Symbole in Verzweigungsknoten stellen Operatoren dar, alle Symbole in Endknoten stellen Operanden dar. Operanden sind entweder Variable oder konkrete Werte. Die Variablen sind Unbekannte im algebraischen Sinne, hinter denen sich, im Gegensatz zu den sogenannten Variablen konventioneller Programmiersprachen, keine Werte verbergen. Die Variablen stellen lediglich sich selbst dar und dienen als Platzhalter, an deren Stelle konkrete Werte oder aber auch Ausdrücke eingesetzt werden können.
Alle Operatoren verknüpfen ihre jeweiligen linken und rechten Teilbäume in sinnvoller Weise miteinander beziehungsweise schreiben vor, wie die Teilbäume zu interpretieren sind.
Der Operator apply legt fest, daß der in seinem rechten Teilbaum dargestellte Ausdruck als eine Funktion und der in seinem linken Teilbaum dargestellte Ausdruck als das Argument dieser Funktion zu verstehen sind, und daß unter bestimmten Voraussetzungen die Funktion auf das Argument anzuwenden, das heißt für das Argument zu berechnen ist.
Der Operator rec schreibt vor, daß jedes Vorkommen der in seinem linken Teilbaum angegebenen Variablen (FAC) in seinem rechten Teilbaum durch eine Kopie des gesamten von rec gebildeten Teilbaumes zu ersetzen ist.
Der Operator sub ersetzt jedes Vorkommen der in seinem linker Teilbaum angegebenen Variablen (N) in seinem rechten Teilbaum durch das Argument der Funktion.
Der Operator if wendet die durch den Operator /_\ gebildete Funktion auf den Ausdruck (N > 1) als Argument an. Die arithmetischen Operatoren +, *, > benutzen ihre Teilbäume als Argumente.
Der dem System zugrunde liegende Verarbeitungsmechanismus durchläuft nun die Baumstruktur nach dem folgenden rekursiven Traversierschema:
(1) Inspiziere den Verzweigungsknoten des Baumes (Teilbaumes);
(2) traversiere rekursive den linken Teilbaum
(3) traversiere rekursiv den rechten Teilbaum.
Dieses sogenannte pre-order Traversierschema durchläuft die in Abb. 1a dargestellte Baumstruktur entlang dem in Abb. 1b angegebenen Pfad und inspiziert dabei die Symbole in der pre-order linearisierten Reihenfolge:
apply 9 rec FAC sub N if > N1 /_\ * N apply - N1 FAC 1.
Diese Folge spiegelt in eindeutiger Weise die Baumstruktur wider, da jedes Verzweigungsknotensymbol rekursiv gefolgt wird von seinem pre-order-linearisierten linken Teilbaum, gefolgt von seinem pre-order-linearisierten rechten Teilbaum.
Während dieses Traversiervorganges wird systematisch versucht, Operatoren auf ihre Operanden beziehungsweise Funktionen auf ihre Argumente anzuwenden. Dies ist immer dann möglich, wenn Funktion und Argumente beziehungsweise Operator und Operanden zueinander passen. Ein arithmetischer Operator ist zum Beispiel nur dann anwendbar, wenn in seinen beiden Teilbäumen Zahlenwerte vorliegen nicht aber, wenn dort weitere Operatoren oder Variable (also Unbekannte) stehen.
Im Falle der Anwendbarkeit wird prinzipiell der Operator zusammen mit seinen beiden Teilbäumen gelöscht, und an seiner Stelle wird das Ergebnis der Operation eingesetzt. Dieses Ergebnis kann beispielsweise in einem umgeformten Teilbaum des Operators bestehen.
Durch eine Sequenz derartiger Transformations- und Reduktionsschritte wird der gesamte Ausdruck solange umgeformt, bis keine weiteren Umformungen mehr möglich sind. Der dann vorliegende Ausdruck ist das Resultat der Berechnung.
Anhand der in Abb. 2 dargestellten Sequenz kann nachvollzogen werden, wie der Beispielausdruck berechnet wird.
Der Verarbeitungsmechanismus führt als erstes den Operator rec aus, dessen Operand der durch rec gebildete Teilbaum selbst ist. Der Operator rec sowie der linke Teilbaum, bestehend aus der Variablen FAC werden gelöscht, und als Ergebnis entsteht ein modifizierter rechter Teilbaum, in dem das Vorkommen der Variablen FAC durch eine Kopie des ursprünglichen rechten Teilbaums ersetzt ist(Abb. 2b.). Es entsteht ein neuer Funktionsausdruck bezüglich des Operators apply der die Ersetzung aller Vorkommen der Variablen N in dem Funktionsausdruck (dem rechten Teilbaum von sub), die nicht durch ein weiteres sub N geschützt sind, durch das Argument 9 vorschreibt. Nach Löschen des Operators apply, des Argumentes 9, sowie der Konstruktion sub N reduziert sich der Ausdruck auf die if-then-else Konstruktion (Abb. 2c), in der nunmehr der Teilbaum (9 > 1) berechnet und durch den Wert "true" ersetzt werden kann (Abb. 2d). Die Anwendung der durch den Operator /_\ gebildeten Funktion über den Operator if auf des Argument "true" ergibt den then-Ausdruck (Abb. 2e), in dem nach Berechnung des Teilbaumes (9 - 1)(Abb. 2f) nunmehr eine erneute Anwendung der ursprünglichen Funktion, diesmal auf das um eins verminderte Argument 8, vorliegt Die Mathematik bezeichnet eine Funktion, die sich auf diese Weise selbst wieder erzeugt, als rekursive Funktion. Entsprechend heißt der Operator rec Rekursionsoperator.
Der beschriebene Umformungszyklus wiederholt sich nun solange bis die rekursive Funktion auf das Argument 0 angewendet wird (Abb. 2g), in welchem Falle sich die If-then-else-Konstruktion zu dem Wert 1 (dem Else-Ausdruck) reduziert. Dadurch entsteht ein Ausdruck (Abb. 2h), in dem die Multiplikation aller Zahlen von 1 bis 9 aufgebaut ist. Die Ausführung der Multiplikationen erfolgt nun schrittweise von rechts nach links (da der Operator * nur auf Zahlen anwendbar ist), bis als Ergebnis die Zahl 362880 entsteht (Abb. 2 i. . .k), die in nichts anderes als sich selbst transformiert werden kann.
Aus der in Abb. 2 dargestellten Folge von Ausdrücken wird unmittelbar klar, weshalb für diese Form der Programmdarstellung und Programmausführung der Begriff "Reduktion" gebraucht wird. Jeder der Transformations- (oder Reduktions-)Schritte überführt einen Ausdruck der Sprache in einen anderen Ausdruck der Sprache, der die gleiche Bedeutung hat, nämlich den am Ende der Folge entstehenden konstanten Wert 362880. Wir können deshalb sagen, daß die Folge von Transformationsschritten den ursprünglichen und jeden Zwischenausdruck auf seine Bedeutung reduziert beziehungsweise in diese überführt. Keiner der Zwischenausdrücke enthält Information darüber, wie er entstanden ist beziehungsweise welches die vorangegangenen Ausdrücke der Folge waren. Die Folge von Reduktionsschritten ist gedächtnislos und demnach auch nicht umkehrbar, da in jedem Schritt. die um Ausdruck enthaltene Information reduziert wird.
Ein Reduktionsrechner, der den geschilderten Verarbeitungsmechanismus direkt unterstützt, bedient sich im wesentlichen dreier Stapelspeicher, die von einer speziellen Verarbeitungseinheit gesteuert werden. Die Stapelspeicher treten an die Stelle des frei adressierbaren Arbeitsspeichers, und die Verarbeitungseinheit tritt an die Stelle des Instruktionsprozessors eines konventionellen Rechners. Stapelspeicher (oder Stacks) erlauben bekanntlich nur einen sehr eingeschränkten Zugriff auf die abgespeicherten Daten beziehungsweise Symbole. Die Zugriffsoperation
- pop entfernt das oberste Datum/Symbol vom Stapel;
- push legt ein neues Datum/Symbol auf den Stapel;
das heißt der Stapel realisiert seine sogenannte LIFO (Last In First Out) Zugriffsdisziplin.
Die drei Stapelspeicher des Reduktionsrechners, die wir mit E, A und M bezeichnen wollen, werden dazu benutzt, einen Ausdruck der Reduktionssprache entsprechend der bereits beschriebenen pre-order-Vorschrift zu traversieren, dabei ausführungsfähige Operatoren zu erkennen, und gegebenenfalls die notwendigen Umformungen auf den betroffenen Teilausdrücken vorzunehmen. Dieser Vorgang soll anhand des einfachen arithmetischen Ausdrucks ((3 + 5) / (6 - 2))
beispielhaft erläutert werden.
Fig. 3 zeigt die drei zur vollständigen Reduktion dieses Ausdruckes erforderlichen Umformungen sowohl anhand der Baumstrukturen als auch anhand der entsprechenden pre-order-linearisierten Darstellungen.
Das Traversieren des Ausdrucks wird mit Hilfe der drei Stacks wie folgt realisiert. Der Ausdruck wird zu Beginn in pre-corder-linearisierter Form in den Stapel E geladen, wobei in oberster Stapelposition der /, gefolgt von seinem linken und rechten Teilbaum erscheint. Der Traversiermechanismus trägt nun den im Stapel E befindlichen Ausdruck Symbol für Symbol ab und baut ihn unter Zuhilfenahme des Stapels M im Stapel A in pre-order-linearisierter Form, allerdings mit links/rechts-vertauschten Teilbäume, wieder auf. Dies geschieht nach folgendem Schema: Auf dem Stapel E wird eine Folge von Popoperationen angewendet, die die Symbole des Ausdrucks an der Stapelspitze entsprechend der Pre-order-Traversiervorschrift erscheine läßt.
Ist des Symbol in oberster Position des Stapels E
- ein Operator, so wird es auf M gestapelt;
- ein Operand, so wird es auf A gestapelt.
Das oberste Operator-Symbol des Stapels M wird entfernt und auf A gestapelt, sobald die beiden zu diese Operator gehörigen Teilbäume vollständig in den Stapel A transportiert sind.
Dieser reine Traversiervorgang ist in verschiedenen Phasen in Abb. 4 dargestellt. Ein wesentliches Merkmal dieser Realisierung besteht nun darin daß Situationen hergestellt werden, in denen die Komponenten eines Teilbaumes so über die Stapel verteilt sind, daß in oberster Position des Stapels
- M sich der Operator
- A sich sein linker Unterbaum und
- E sich sein rechter Unterbaum befindet.
Dies ist der Fall
- für den durch den Operator + gebildeten Teilbaum in Phase d;
- für den durch den Operator - gebildeten Teilbaum in Phase h;
- für den durch den Operator / gebildeten Baum in Phase f.
Diese Phasen sind perfekt dafür geigten, durch Inspektion der Stapelspitze zu beurteilen, ob ein Operator auf seine Argumente beziehungsweise Operanden anwendbar ist. In konkreten Beispiel arithmetischer Operatoren ist dies immer dann der Fall wenn auf den Spitzen der Stapel E und A Zahlenwerte vorliegen. Die Zahlenwerte können dann zusammen mit den auf M befindlichen Operator von den Stapelspitzen entfernt und in der Verarbeitungseinheit entsprechend verknüpft werden. Das Ergebnis der Teilberechnung wird auf dem Stapel E abgelegt.
Die Durchführung dieser Berechnungen oder bedeutungserhaltenden den Umformungen während des Traversiervorgangs führt zu den in Abb. 5 dargestellten Phasen. Aktivierte Operatoren liegen in den Phasen d, h und i vor. Denkt man sich in den Phasen e und g jeweils alle Symbole zurückverlegt auf den stapel E, so entstehen in den Phasen a, e, g und q genau die Ausdrucke der in Abb. 3 dargestellten Reduktionsfolge vollständig im Stapel E.
Ein System von drei Stapeln ist für das geschilderte Arbeitsprinzip ausreichend. Allerdings ist es zweckmäßig, für aufwendigere Umformungen wie zum Beispiel im Falle der Ersetzung von Variablen durch Argumentausdrücke bei der Reduktion der Operatoren sub oder rec mehr als drei Stapel zur Verfügung zu haben. Es hat sich gezeigt, daß insgesamt acht Stapel, die den Arbeitsspeicher eines Reduktionsrechners bilden eine praktikable Lösung sind, Um selbst aufwendige Umformungen die die Zerlegung eines Ausdrucks in viele Komponenten erfordern, elegant und zeiteffizient zu unterstützen.
Der entscheidende Unterschied zu konventionellen Rechnern besteht darin, daß in Reduktionsrechnern bei der Ausführung von Operationen deren Komponenten, das heißt der Operator und seine beiden Teilausdrücke, verbraucht werden, und an deren Stelle ein neuer Ausdruck oder ein Resultat erzeugt wird. Dies bedeutet, daß mehrere Operatoren, die den gleichen Teilausdruck beziehungsweise Wert als Operand benötigen, eigene Exemplare dieses Operanden zur Verfügung gestellt werden müssen. Die geordnete Vervielfältigung eines solchen Teilausdrückes wird über den im ersten Beispielprogramm eingeführten Operator sub (für Substitution) bewerkstelligt der ein Argument so oft reproduziert, wie in den rechten Teilbaum vom sub die durch diesen Operator gebundene Variable auftritt. Das gleiche gilt für den Operator rec, der eine rekursive Funktion so oft reproduziert, wie die durch rec gebundene Variable in der Funktion selbst auftritt.
Die in konventionellen Rechnern über die Angabe von Zellnamen völlig freizügig herstellbaren Bezüge zwischen Operatoren und Operanden sind hier ersetzt durch eine geordnete und direkte Zuführung von Operanden zu Operatoren über die speziellen Operatoren sub beziehungsweise rec. Es werden genau so viele Exemplare eines Ausdruckes erzeugt, wie von nachfolgenden Operatoren zum Verbrauch benötigt werden.
Die Einführung der beiden Operatoren sub und rec ist maßgebend dafür, daß die Programmierung von der Festlegung eines Arbeitsplanes für den Computer befreit und auf die Formulierung mathematischer Ausdrücke, die lediglich festlegen, was berechnet werden soll, beschränkt werden kann. Diese Operatoren stellen nämlich eine wichtige Systemkomponente jedes Rechners, die Logistik der Verknüpfung von Operatoren und Operanden, ebenfalls auf eine mathematisch begründbare Grundlage.
Ein auf dem beschriebenen Reduktionsprinzip basierender Rechner ist als Labormodell bereits 1979 in der Gesellschaft für Mathematik und Datenverarbeitung in Bonn gebaut worden und seitdem in Betrieb. Außerdem existieren eine Reihe von Simulationsprogrammen, die Reduktionsrechner auf konventionellen Großrechnern nachbilden. Die praktische Anwendung der Reduktionssprache in verschiedenen Bereichen der Datenverarbeitung konnte exemplarisch demonstriert werden.
Langfristige Zielsetzungen der laufenden Forschungs- und Entwicklungsarbeiten auf diesem Gebiet beinhalten eine Verallgemeinerung des Konzeptes. Reduktionssysteme transformieren Problemstellungen Schritt für Schritt unter Beibehaltung der Bedeutung in eine Resultatdarstellung. Dabei folgen sie festen Umformungsregeln. Logische Maschinen, wie sie in Japan als Computer der fünften Generation konzipiert werden, sollen so ausgelegt werden; daß sie aus einer Menge von Regeln und Aussagen neue Aussagen herleiten oder die Verträglichkeit einer neuen Aussage mit existierenden Aussagen beziehungsweise Regeln überprüfen können. Auch diese Maschine benötigen Mechanismen, über die Programmstrukturen durch Ersetzungen systematisch umgeformt werden können.
Das Reduktionsprinzip stellt eine mathematisch fundierte Grundlage für die Entwicklung derartiger Maschinen dar.
*Dr.Werner Kluge ist Professor am Institut für Informatik der Universität Bonn und Berater der GMD, Schloß Birlinghoven.