6Formale Algorithmenmodelle

Einfache Modelle für Maschinen

In den bisherigen Abschnitten haben wir bereits einige Formalismen für Algorithmen kennen gelernt. Die Ausführung von Algorithmen haben wir bisher auf einer eher abstrakten Ebene betrachtet und deren Ausführung durch mathematische Funktionen erklärt. Unser Ziel ist nun die Entwicklung von einfachen Modellen für Maschinen, die Algorithmen ausführen. Ein Computer ist hingegen eine durchaus reale Maschine, die Algorithmen ausführen kann, stellt aber tatsächlich ein sehr komplexes Gerät dar, und ist daher sowohl für das Erlernen der Grundprinzipien als auch für mathematische Betrachtungen zu komplex. Unser Ziel sind daher einfache Modelle,

• die näher an tatsächlichen Computern sind als die abstrakte Ausführung etwa von applikativen Algorithmen oder
• einfacher für mathematische Betrachtungen nutzbar sind als die bisherigen Algorithmenmodelle.

Wir beginnen in Abschnitt 6.1 mit dem Modell der Registermaschinen, die sozusagen eine einfache mathematische Variante realer Computer mit Prozessor und Speicher darstellen. Abschnitt 6.2 behandelt abstrakte Maschinen als vereinheitlichendes Modell, um Aspekte wie Laufzeit und Terminierung einer Algorithmenausführung in einem einheitlichen Rahmen einführen zu können. Abschnitt 6.3 betrachtet ein besonders simples Modell, die Markov-Tafeln, das sich allerdings besonders gut eignet, um sich einen eigenen Algorithmeninterpreter zu programmieren.

In Abschnitt 6.4 vergleichen wir die Ausdrucksfähigkeit der verschiedenen Maschinenmodelle, bevor wir abschließend in Abschnitt 6.5 exemplarisch die Realisierung von Algorithmeninterpretern in Java betrachten.

6.1Registermaschinen

Registermaschine als idealisierter Computer

Als erstes formales Modell betrachten wir die sogenannten Registermaschinen. Registermaschinen befinden sich von der Abstraktion nahe an tatsächlichen Computern und bilden daher quasi eine Art »idealisierte« Version eines Prozessors mit Maschinencode-Steuerung.

Eine Registermaschine als Prozessor führt ein Maschinenprogramm aus, das als durchnummerierte Liste von Einzelschritten vorliegt (dies entspricht tatsächlichen Maschinenprogrammen in Rechnern). Die einzige Kontrollstruktur neben der durch die Nummerierung impliziten Sequenz bilden (bedingte) Sprünge, die es erlauben, an einer beliebigen Stelle des Programms mit der Ausführung weiterzufahren.

Daten werden in einem direkt adressierbaren Speicher gehalten, der eine Abstraktion des bekannten Hauptspeichers darstellt. Als theoretisches Modell betrachten wir dabei einen beliebig großen, unbeschränkten Speicher. Arithmetische Manipulationen werden ausschließlich im Akkumulatorregister des Prozessors ausgeführt.

Diese (maschinennahe) Präzisierung des Algorithmenbegriffs werden wir nun als Registermaschinen exakt definieren. Diese stellen eine relativ simple Abstraktion der programmierbaren Rechner dar, so dass wir in den Bezeichnungen auf vertraute Begriffe der technischen Informatik zurückgreifen.

Definition 6.1 Definition einer Registermaschine

Eine Registermaschine besteht aus den Registern

B, C₀, C₁, C₂, …, C_n, …

und einem Programm.

Arten von Registern

Das Register B heißt Befehlszähler, C₀ heißt Arbeitsregister oder Akkumulator und jedes der Register C_n, n ≥ 1 heißt Speicherregister.

Jedes Register enthält als Wert eine natürliche Zahl. Enthält das Register B die Zahl b und für n ≥ 0 das Register C_n die Zahl c_n, so heißt das unendliche Tupel

(b, c₀, c₁, …, c_n, …)

Konfiguration

Konfiguration der Registermaschine.

Das Programm ist eine endliche Folge von Befehlen. Durch die Anwendung eines Befehls wird die Konfiguration der Registermaschine geändert.

Befehle und deren Effekt auf Konfigurationen

Die folgende Aufzählung gibt die zugelassenen Befehle und die von ihnen bewirkte Änderung einer Konfiguration

(b, c₀, c₁, … c_n, …)

in die neue Konfiguration

(b′, c′₀, c′₁, …, c′_n, …),

geschrieben als

(b, c₀, c₁, … c_n, …) (b′, c′₀, c′₁, …, c′_n, …),

an.

Ein- und Ausgabebefehle

Die Abbildung 6–1 listet die drei Arten der Ein- und Ausgabebefehle von Registermaschinen und deren Bedeutung auf.

Abb. 6–1 Ein- und Ausgabebefehle einer Registermaschine

Bei den Eingabebefehlen LOAD i und CLOAD i wird der Wert des i-ten Registers bzw. die Zahl i in den Akkumulator geladen; bei STORE i wird der Wert des Akkumulators in das i-te Speicherregister eingetragen.

Arithmetische Befehle

Die Manipulation der Werte im Akkumulator wird durch die in Abbildung 6–2 aufgelisteten arithmetischen Befehle durchgeführt.

Abb. 6–2 Arithmetische Befehle von Registermaschinen

Bei den Befehlen ADD i, SUB i, MULT i und DIV i erfolgt eine Addition, Subtraktion, Multiplikation und Division des Wertes des Akkumulators mit dem Wert des i-ten Speicherregisters. Da die Operationen nicht aus dem Bereich der natürlichen Zahlen herausführen sollen, wird die Subtraktion nur dann wirklich ausgeführt, wenn der Subtrahend nicht kleiner als der Minuend ist, und sonst 0 ausgegeben; analog erfolgt die Division nur ganzzahlig.

Die Befehle CADD i, CSUB i, CMULT i und CDIV i arbeiten analog, nur dass anstelle des Wertes des i-ten Registers die natürliche Zahl i benutzt wird. Dadurch werden auch arithmetische Operationen mit Konstanten möglich.

Sprungbefehle

Die dritte Art von Befehlen bilden die beiden Sprungbefehle, die in Abbildung 6–3 aufgelistet werden.

Abb. 6–3 Sprung- und Stoppbefehle einer Registermaschine

In allen bisherigen Fällen wird der Wert des Befehlsregisters um 1 erhöht, d.h., der jeweils nächste Befehl des Programms wird abgearbeitet. Dies ist bei den Sprungbefehlen grundsätzlich anders. Bei GOTO i wird als nächster Befehl der i-te Befehl des Programms festgelegt, während bei der IF-Anweisung in Abhängigkeit von dem Erfülltsein der Bedingung c₀ = 0 der nächste Befehl der i-te bzw. der (b + 1)-te Befehl des Programms ist. Man muss beachten, dass c₀ = 0 die einzige Bedingung ist, die hier angegeben werden kann – sie ist sozusagen Teil der Befehlsbezeichnung.

Stoppbefehl

Der ebenfalls in Abbildung 6–3 aufgelistete Stoppbefehl END bildet den Abschluss der Diskussion von Befehlsarten. Der Befehl END ist kein eigentlicher Stoppbefehl. Er lässt die Konfiguration unverändert, so dass diese nun ad infinitum bestehen bleibt (und daher als das Ende der Berechnung angesehen werden kann).

Abb. 6–4 Aufbau einer Registermaschine

Die Abbildung 6–4 verdeutlicht noch einmal den prinzipiellen Aufbau einer Registermaschine.

Die Arbeitsweise einer Registermaschine lässt sich am besten an einem einfachen Beispiel erläutern.

Beispiel 6.1 Registermaschine M₁

Wir betrachten die Registermaschine M₁ mit dem Programm

1. LOAD 1
2. DIV 2
3. MULT 2
4. STORE 3
5. LOAD 1
6. SUB 3
7. STORE 3
8. END

und untersuchen die Veränderung der Konfiguration, wobei wir uns auf das Befehlsregister, den Akkumulator und die ersten drei Speicherregister beschränken, da nur diese während der Berechnung verändert werden. Stehen in den Registern zuerst die Zahlen

Beispiellauf von M₁

b = 1, c₀ = 0, c₁ = 32, c₂ = 5, c₃ = 0,

so ergibt sich diese Folge von Konfigurationen

womit der »stoppende« Befehl erreicht wird. Sind die Inhalte der Register dagegen

b = 1, c₀ = 0, c₁ = 100, c₂ = 20, c₃ = 0,

so ergibt sich folgende Folge von Konfigurationen

Allgemeiner Lauf von M₁

Allgemeiner lässt sich Folgendes feststellen. Wir betrachten eine Konfiguration, die durch

b = 1, c₀ = 0, c₁ = n, c₂ = m, c₃ = 0

gegeben ist, und nehmen an, dass n = q·m + r mit 0 ≤ r < m gilt, d.h., q = ⌊n/m⌋ ist das ganzzahlige Ergebnis der Division von n durch m und r ist der verbleibende Rest bei dieser Division. Dann ergibt sich immer die Folge

Diese Berechnungsfolge der Registermaschine M₁ berechnet also den ganzzahligen Rest der Division zweier natürlicher Zahlen.

Dieses Beispiel legt Folgendes nahe: Gehen wir von einer Konfiguration aus, die im Befehlsregister eine 1 enthält, d.h., es wird mit der Abarbeitung des Programms beim ersten Befehl begonnen, und in den beiden ersten Speicherregistern zwei natürliche Zahlen n und m führt, so steht nach Abarbeitung des Programms (genauer: in der sich nicht mehr verändernden Konfiguration, die bei der END-Anweisung erreicht wird) im dritten Speicherregister der Rest der ganzzahligen Division von n durch m.

Von M₁ berechnete Funktion

Daher ist es nahe liegend zu sagen, dass die gegebene Registermaschine M₁ – genauer die durch das Programm gegebene Registermaschine – die Funktion r = rest(n, m) berechnet, die durch

r = rest(n, m) genau dann, wenn 0 ≤ r < n und n = qm + r für ein q ∊

gegeben ist.

Wir verallgemeinern diese Idee in der folgenden Definition.

Definition 6.2 Berechnete Funktion einer Registermaschine

Eine Registermaschine M berechnet die Funktion f : ⁿ → ^m mit f(x₁, x₂, …, x_n) = (y₁, y₂, …, y_m), wenn es Zahlen i₁, i₂, …, i_m so gibt, dass M jede Konfiguration (1, 0, x₁, x₂, …, x_n, 0, 0, …) in eine Konfiguration (b, c₀, c₁, …) überführt, für die b die Nummer einer END-Anweisung ist und c_ij = y_j für 1 ≤ j ≤ m gilt.

Intuitiv bedeutet dies Folgendes: Die Registermaschine beginnt die Abarbeitung ihres Programms mit dem ersten Befehl, wobei die Argumente bzw. Eingaben der Funktion in den ersten n Speicherregistern C₁, C₂, …, C_n stehen. Sie beendet ihre Arbeit bei Erreichen eines END-Befehls und die Resultate bzw. Ausgaben stehen in den vorab festgelegten Speicherregistern C_i1, C_i2, …, C_im.

Registermaschinen für arithmetische Grundfunktionen

Die arithmetischen Grundfunktionen lassen sich in diesem Sinn einfach berechnen. Zum Beispiel berechnet die Registermaschine mit dem Programm

1. LOAD 1
2. ADD 2
3. STORE 3
4. END

aus den Werten x und y in den Registern C₁ und C₂ die Summe x + y und legt diese im Register C₃ ab, realisiert also mit i₁ = 3 die Addition. Analog verfährt man bei den anderen Operationen. Im Allgemeinen ist es natürlich aufwendiger, die berechnete Funktion einer gegebenen Registermaschine zu bestimmen.

Beispiel 6.2 Registermaschine M₂

Wir betrachten die Registermaschine M₂ mit dem Programm

1. CLOAD 1
2. STORE 3
3. LOAD 2
4. IF c₀ = 0 GOTO 12
5. LOAD 3
6. MULT 1
7. STORE 3
8. LOAD 2
9. CSUB 1
10. STORE 2
11. GOTO 4
12. END

und bestimmen die Funktion f₂ : ² → , die das Ergebnis im dritten Speicherregister enthält.

Konkrete Abarbeitung von M₂

Wir betrachten zuerst die Entwicklung einer konkreten Konfiguration (1, 0, 5, 3, 0, …), wobei wir uns erneut auf das Befehlsregister, den Akkumulator und die ersten drei Speicherregister beschränken, da nur diese vom Programm betroffen sind. Es ergibt sich folgende Abarbeitung des Programms:

Dieses konkrete Beispiel ergibt f₂(5, 3) = 125.

Allgemeine Abarbeitung von M₂

Für den allgemeinen Fall, d.h. die Konfiguration (1, 0, x, y, 0, …), gelten folgende Bemerkungen. Nach der Abarbeitung der Befehle 1 – 3 ergibt sich die Konfiguration (4, y, x, y, 1, …).

Falls y = 0 ist, so wird zur END-Anweisung gegangen, und es ergibt sich aus der Konfiguration (12, y, x, y, 1) = (12, 0, x, 0, 1) das Ergebnis 1 aus dem dritten Speicherregister. Falls y ≠ 0 ist, so werden die Befehle 5 – 11 durchlaufen, wodurch ins dritte Speicherregister der Wert 1 · x und ins zweite Speicherregister der Wert y − 1 geschrieben wird, d.h., die erreichte Konfiguration ist (4, y−1, x, y−1, 1·x, …).

Ist y − 1 = 0, so wird zur Konfiguration (12, y −1, x, y −1, x, …) = (12, 0, x, 0, x, …) übergegangen und x als Ergebnis ausgegeben. Ist y − 1 ≠ 0, so werden erneut die Befehle 5 – 11 abgearbeitet und (4, y − 2, x, y − 2, x², …) erhalten.

Ist y−2 = 0, so wird (12, y−2, x, y−2, x², …) = (12, 0, x, 0, x², …) erreicht und das Ergebnis ist x²; bei y − 2 ≠ 0 werden erneut die Befehle 5 – 11 abgearbeitet.

Folglich bricht der Prozess mit (12, y − k, x, y − k, x^k, …) = (12, 0, x, 0, x^y, …) (wegen y = k) ab.

Berechnete Funktion von M₂

Somit ist die von M₂ berechnete Funktion

f₂(x, y) = x^y.

Dieses Beispiel zeigt daher, dass neben den arithmetischen Grundoperationen auch das Potenzieren eine durch Registermaschinen berechenbare Funktion ist.

Das folgende Beispiel demonstriert, dass die Betrachtungen der vorherigen Kapitel bezüglich Terminierung von Algorithmen auch für Registermaschinen zutreffen.

Beispiel 6.3 Registermaschine M₃

Offensichtlich berechnet die Registermaschine M₃ mit dem Programm

1. LOAD 1
2. IF c₀ = 0 GOTO 4
3. GOTO 2
4. END

die Funktion

denn nur in dem Fall, dass die Eingabe 0 ist, wird zur END-Anweisung gesprungen, ansonsten werden die Befehle 2 und 3 abwechselnd unendlich lange hintereinander ausgeführt und damit kein Ergebnis produziert.

Partielle Funktionen

Dieses Beispiel zeigt insbesondere, dass die von Registermaschinen berechneten Funktionen partiell sein können, d.h., ihr Definitionsbereich ist eine echte Teilmenge von ⁿ.

Beispiel 6.4 Registermaschine M₄

Wir wollen nun eine Registermaschine M₄ konstruieren, die die Funktion

berechnet.

Eine natürliche Zahl x ist bekanntlich genau dann eine Primzahl, wenn x ≥ 2 ist und nur die Teiler 1 und x besitzt.

Hieraus resultiert folgendes Vorgehen: Wir überprüfen zuerst, ob die Eingabe x ≤ 1 ist. Sollte dies der Fall sein, so ist x keine Primzahl und wir schreiben in das zweite Speicherregister eine 0 und beenden die Arbeit. Ist dagegen x ≥ 2, so testen wir der Reihe nach, ob x durch 2, 3, 4, …, x − 1 teilbar ist. Gibt einer dieser Tests ein positives Resultat, so ist x keine Primzahl; fallen dagegen alle diese Tests negativ aus, so ist x prim.

Das Programm in Abbildung 6–5 realisiert diese Idee (zur Illustration geben wir in der rechten Spalte kurze Erläuterungen zu den Befehlen).

Abb. 6–5 Registermaschine zur Berechnung des Primzahltests

6.2Abstrakte Maschinen

Wir haben nun bereits eine Reihe von Algorithmenmodellen kennen gelernt: applikative und imperative Algorithmen sowie Registermaschinen. Welche Eigenschaften haben diese gemeinsam und folgen derartige gemeinsame Eigenschaften sogar aus unserer intuitiven Algorithmencharakterisierung?

Bezugsrahmen für verschiedene Algorithmenmodelle

Gemeinsam ist diesen Modellen die Kombination von Kontrollstrukturen mit elementaren, durch eine Art »Maschine« ausführbaren Einzelschritten. Wir werden nun versuchen, die diversen Modelle in einen einheitlichen Bezugsrahmen zu setzen, um diese besser vergleichen zu können und um wichtige Eigenschaften wie Laufzeit, Terminierung etc. unabhängig von einem konkreten Algorithmenmodell konkretisieren zu können.

Wir bedienen uns dabei des Modells der abstrakten Maschine als universelles Rahmenmodell für verschiedene Algorithmen-Notationen, wie es in der theoretischen Informatik seit langem bekannt ist.

Definition 6.3 Abstrakte Maschine

Wir definieren ein recht allgemeines mathematisches Modell für deterministische Algorithmen, »abstrakte Maschine« genannt. Eine abstrakte Maschine M ist ein 7-Tupel

M = (X, Y, K, α, ω, τ, σ),

wobei gilt:

Einige dieser Begriffe sind uns bereits aus der Diskussion der Registermaschinen vertraut, sie werden in abstrakten Maschinen in ähnlicher Weise eingesetzt.

Die Aufgabe der Stoppfunktion ist es, bestimmte Konfigurationen als Endkonfigurationen zu markieren.

Definition 6.4 Endkonfiguration

Die Menge der Endkonfigurationen zu M ist

E = {k ∊ K | σ(k) = true}

Eine abstrakte Maschine M lässt sich auch durch ein Diagramm darstellen (siehe Abbildung 6–6). Die grafische Darstellung verdeutlicht insbesondere die eingehende Information und die Ergebnisse der Verarbeitung.

Arbeitsweise einer abstrakten Maschine

Eine abstrakte Maschine arbeitet nun folgendermaßen:

1. Ein Eingabewert x ∊ X bestimmt die Anfangskonfiguration k₀ = α(x) ∊ K.
2. Wir überführen mittels τ Konfigurationen in Folgekonfigurationen, also

   k₁ = τ(k₀), k₂ = τ(k₁), …

   bis zum ersten Mal eine Endkonfiguration k_i ∊ E erreicht wird. Dies braucht natürlich niemals einzutreten.

Abb. 6–6 Abstrakte Maschine

1. 3.Wird eine Endkonfiguration k_i ∊ E erreicht, so wird der Ausgabewert ω(k_i) ∊ Y ausgegeben.

Bei Eingabe von x ∊ X gibt es also zwei Möglichkeiten:

1. Die Maschine hält nie an.
2. Die Maschine hält und gibt einen eindeutig bestimmten Ausgabewert y ∊ Y aus.

Auf diese Weise berechnet die Maschine M eine partielle Funktion

f_M : X → Y

Wir präzisieren diese Verhaltensweise mathematisch.

Definition 6.5 Laufzeit einer abstrakten Maschine

Die Laufzeit einer abstrakten Maschine M für die Eingabe x ∊ X ist definiert als

t_M(x) = (µn)[σ(τⁿ(α(x)))]

Hierbei ist (µn)[B] die kleinste natürliche Zahl n ∊ = {0, 1, 2, …}, so dass die Bedingung B = true wird und B für alle m ≤ n definiert ist. Gibt es keine solche Zahl n ∊ , so ist t_M(x) = ⊥ (undefiniert).

Definition 6.6 Berechnete Funktion einer abstrakten Maschine

Die von einer abstrakten Maschine M berechnete Funktion

f_M : X → Y

ist gegeben durch

f_M(x) = ω(τ^t_M(x)(α(x)))

Ist t_M(x) = ⊥, so ist f_M(x) = ⊥.

Applikative und imperative Algorithmen sind Beispiele dieses allgemeinen Algorithmenmodells, d.h., sie lassen sich als abstrakte Maschinen auffassen. Wir skizzieren den Zusammenhang grob, ohne ins Detail zu gehen.

Beispiel 6.5 Applikativer Algorithmus als abstrakte Maschine

Applikative Algorithmen (nur ganzzahlige E/A). Gegeben seien folgende Funktionsdefinitionen:

f_i(u_i, 1, …, u_i,ni) = t_i(u_i, 1, …, u_i,ni), i = 1, …, m.

Diese werden als abstrakte Maschine wie folgt realisiert:

• X = ^n₁
• Y =
• K = Terme ohne Unbekannte
• α(a₁, …, a_n1) = der Term »f₁(a₁, … a_n1)«
• ω(t) = der Wert von t
• τ: Termauswertung aufgrund der Funktionsdefinitionen.
  Da diese nichtdeterministisch ist, müssen wir sie durch eine zusätzliche »Berechnungsvorschrift« deterministisch machen, z.B. durch die Forderung, das erste Auftreten von links eines Funktionsaufrufs mit Konstanten, f_i(b₁, …, b_ni) mit b_j ∊ , j = 1, …, n_i, durch die rechte Seite t_i(b₁, …, b_ni) zu ersetzen.
• 

Beispiel 6.6 Imperativer Algorithmus als abstrakte Maschine

Imperative Algorithmen (nur ganzzahlige E/A). Gegeben sei ein imperativer Algorithmus wie folgt:

Ein derartiges Programm wird abgebildet auf:

• X = ⁿ
• Y = ^m
• K = {(Z, β) | Z Zustand, β Anweisung }

  Z bezeichnet den aktuellen Zustand,

  β die noch auszuführende Anweisung

• α(a₁, …, a_n) = (Z₀ β,), wobei

• ω (Z, β) = (Z(Y₁), …, Z(Y_m))
• τ (Z, β) = (Z′, β′), wobei

Auch Registermaschinen lassen sich direkt als Spezialfall einer abstrakten Maschine beschreiben.

Abstrakte Maschinen sind natürlich zu »abstrakt«, um direkt nutzbar zu sein. Unsere Beschäftigung mit ihnen sollte aber das Gemeinsame hinter den unterschiedlichen Algorithmenmodellen verdeutlicht haben. Des Weiteren haben wir nun eine Definition von Laufzeit und berechneter (partieller) Funktion, die wir unabhängig vom konkret benutzten Algorithmenmodell nutzen können.

6.3Markov-Algorithmen

Als letztes Beispiel für ein Maschinenmodell betrachten wir die sogenannten Markov-Algorithmen als ein einfaches mathematisch orientiertes Modell, das eine Spezialisierung abstrakter Maschinen darstellt.

Der besondere Reiz von Markov-Algorithmen liegt darin, dass diese sich sehr leicht programmtechnisch in einen Interpretierer für sogenannte Markov-Tafeln umsetzen lassen. Hiermit ergibt sich sehr schnell die Möglichkeit, die auf den ersten Blick als mathematische Spielereien erscheinenden formalen Algorithmenmodelle auch in einer eigenen Programmierung ausprobieren zu können. Jeder Rechner führt ja Algorithmen, die in einer Algorithmensprache wie Java programmiert wurden, in ähnlicher Weise aus – daher sollte man die Chance eines möglichst einfachen Algorithmenmodells nutzen, um sich mit diesem Konzept vertraut zu machen.

Markov-Algorithmus

Sei A = (a₁, …, a_n) ein Alphabet und sei A* die Menge der Worte (Texte) über A. Wir definieren die Klasse der Markov-Algorithmen, im Namen angelehnt an das ursprüngliche Modell (Markov 1954). Die elementaren Einzelschritte dieser Algorithmen beruhen auf Regeln der Form ϕ → ψ, wobei Zeichenketten ϕ, ψ ∊ A* sind. Diese Angaben bedeuten, dass das (Teil-)Wort ϕ durch das Wort ψ ersetzt werden soll. Angewendet auf ein Wort ξ ∊ A* entsteht somit auf eindeutige Weise ein neues Wort g[ϕ → ψ](ξ), das wie folgt definiert ist:

1. Ist ϕ ein Teilwort von ξ, also ξ = µϕν für µ, ν ∊ A*, und ist ϕ an dieser Stelle (also nach µ) das erste Auftreten (von links) von ϕ in ξ, so ist g[ϕ → ψ](ξ) = µψν, d.h., ϕ wird (nur!) an dieser Stelle durch ersetzt.
2. Ist ϕ kein Teilwort von ξ, so ist g[ϕ → ψ](ξ) = ξ, d.h., es passiert nichts.

Es wird also das erste Auftreten des Teilworts ϕ durch das Teilwort ψ ersetzt.

Beispiel 6.7 Anwendung einer Regel

Sei A = (0, 1). Wir wenden die Regel 01 → 10 sukzessive an.

Diese Regel verschiebt also quasi die Nullen nach rechts.

Markov-Tafeln

Ein Markov-Algorithmus besteht nun aus einer Menge solcher Regeln, zusammen mit einer »Kontrollstruktur«, die eindeutig festlegt, wann welche Regel anzuwenden ist. Diese Information wird übersichtlich in einer Tabelle, der Markov-Tafel, zusammengefasst. Diese hat fünf Spalten und beliebig viele (natürlich nur endlich viele) Zeilen. Eine Zeile ist ein 5-Tupel der Form

k ϕ ψ i j,

wobei i, j, k ∊ sind. k ist die Zeilennummer, ϕ und ψ stellen die Regel ϕ → ψ dar, i ist die Nummer der nächsten Zeile, falls das Teilwort ϕ gefunden (die Regel also angewandt) wurde, und j ist die Nummer der nächsten Zeile, falls ϕ nicht auftrat.

Die Ausführung der Markov-Tafel beginnt in der ersten Zeile (Nummer 0) und stoppt, sobald zu einer nicht vorhandenen Zeilennummer (i oder j) gegangen werden soll. Dazwischen werden die Regeln der angelaufenen Zeilen auf das Eingabewort nacheinander angewandt.

Bevor wir Beispiele betrachten, definieren wir Markov-Algorithmen zunächst als abstrakte Maschinen:

Definition 6.7 Markov-Algorithmus

Ein Markov-Algorithmus über dem Alphabet A ist gegeben durch

Wie man sieht, ist ein Markov-Algorithmus tatsächlich eine direkte Spezialisierung des Konzepts der abstrakten Maschine.

Wir betrachten nun einige einfache Markov-Tafeln. Markov-Algorithmen arbeiten dabei auf Zeichenketten und nicht etwa auf natürlichen Zahlen wie die anderen vorgestellten Modelle. Wir werden Zahlen entweder im unären Zahlsystem (nur eine Ziffer) darstellen, die Zahl 5 also als |||||, oder im Binärsystem kodieren.

Beispiel 6.8 Markov-Tafel für Addition von 1

»Addiere |«.

Die Markov-Tafel lautet:

Diese Markov-Tafel berechnet die Funktion f(|ⁿ) = |ⁿ⁺¹, n ∊ , also die Successor-Funktion im unären Zahlsystem.

Zu diesem Beispiel ist eine Bemerkung notwendig. Das leere Wort ε kommt in jedem Wort vor (an jeder Stelle!). Das erste Auftreten ist dabei ganz am Anfang. Der Algorithmus schreibt also ein | vor das Eingabewort |ⁿ = | | … |. Der j-Eintrag der Tabelle kann niemals angelaufen werden und ist daher irrelevant. Dies deuten wir durch das Zeichen − in der Tabelle an.

Beispiel 6.9 Markov-Tafel für Addition im unären System

»Addition« im unären System.

Die Markov-Tafel lautet:

Der Algorithmus löscht das erste + im Eingabewort, also:

f(|ⁿ + |^m) = |^n+m

Die Addition im unären Zahlsystem erfolgt einfach durch Aneinanderhängen der Strichlisten.

Diese beiden Algorithmen haben natürlich kein besonders aufregendes Verhalten gezeigt. Etwas mehr Aufwand muss man beim nächsten Beispiel treiben, der Verdopplung einer Strichliste (also der Multiplikation mit 2 im unären Zahlsystem).

»Verdopplung« im unären System.

Beispiel 6.10 Markov-Tafel für Verdopplung einer Strichliste

Das Zeichen # spielt die Rolle einer Markierung, die einmal von links nach rechts durchwandert und dabei die Zeichen | verdoppelt. In den Kommentaren der folgenden Tafel gilt p = (n − q).

Eine Berechnung mit dem Eingabewort | | | ergibt:

Allgemein wird die Funktion f(|ⁿ) = |²ⁿ berechnet.

Das folgende Beispiel definiert die Multiplikation zweier als Strichlisten kodierter Zahlen, wobei die bisherigen Beispieltafeln zum Teil als Teil»programme« verwendet werden können.

Beispiel 6.11 Markov-Tafel zur Multiplikation im unären System

»Multiplikation« im unären System.

Der folgende Markov-Algorithmus berechnet die Multiplikation, also die Funktion f(|ⁿ_* |^m) = |^n*m :

Mit der Eingabe | | | * | | ergibt sich z.B. folgende Berechnungsfolge:

Als letztes Beispiel betrachten wir eine Markov-Tafel für Eingaben in binärer Darstellung.

Beispiel 6.12 Markov-Tafel für Kopieren einer Zeichenkette

»Kopieren« im binären System.

Der folgende Markov-Algorithmus berechnet die Funktion

also die Verdopplung einer Zeichenkette mit einem Trennsymbol in der Mitte. Die Markov-Tafel lautet:

Mit der Eingabe 0 1 0 ergibt sich die folgende Berechnung:

Markov-Tafeln arbeiten auf einem sehr einfachen Niveau, da nur reine Zeichenketten und keine »höheren« Datentypen wie Zahlen unterstützt werden. Dies macht natürlich gerade das Formulieren arithmetischer Funktionen aufwendig, da ja Zahlen als Zeichenketten kodiert werden müssen. Auch werden Markov-Tafeln für größere Alphabete schnell unhandlich, da in jedem logischen Schritt Fallunterscheidungen für alle Symbole notwendig werden können.

Andererseits ist der einzelne Bearbeitungsschritt leicht mit Standardoperationen des Datentyps string in gängigen Programmiersprachen umsetzbar: Suchen des ersten Auftretens eines Teil-Strings, Ersetzen eines Teil-Strings sind dort elementare Operationen. Daher lässt sich ein Markov-Interpreter besonders einfach realisieren.

6.4Church’sche These

Ausdrucksfähigkeit der verschiedenen Algorithmenmodelle

Gerade nach der Diskussion eines doch eher einfachen Modells wie das der Markov-Algorithmen stellt sich die Frage der Ausdrucksfähigkeit der verschiedenen Algorithmenmodelle.

Welche Funktionen können nun durch Markov-Algorithmen berechnet werden? Leisten Markov-Algorithmen mehr oder weniger als applikative bzw. imperative Algorithmen? Wie kann man überhaupt die Leistungen von Algorithmenmodellen miteinander vergleichen?

Einem direkten Leistungsvergleich steht zunächst der Umstand im Wege, dass die unterschiedlichen Arten von Algorithmen auf ganz verschiedenen Argument- und Wertebereichen definiert sind:

Um vergleichen zu können, muss man zunächst die Argument- und Wertebereiche »vereinheitlichen«, d.h., man muss einen Argument- und Wertebereich finden, mit dem sich alle Ein- und Ausgaben aller Algorithmenmodelle eindeutig und effektiv (i.e. berechenbar)kodieren lassen.

Einen solchen für die Zwecke der Berechenbarkeit »universellen« Bereich bilden u.a. Texte A* über einem festen Alphabet A = {a₁, …, a_n}: derselbe Wertebereich wie für die Algorithmentexte!

Es gilt das folgende wichtige, grundlegende (und vielleicht überraschende) Ergebnis: Alle bisher behandelten und weitere Algorithmenmodelle leisten prinzipiell gleich viel.

Den Beweis dieses Satzes wollen wir hier nicht durchführen. Er wird konstruktiv geführt, indem man allgemeine »Übersetzer« angibt, die jeden Algorithmus des einen Modells in einen gleichwertigen des anderen Modells überführen, der dieselbe Funktion berechnet. Die Konstruktion solcher Übersetzer ist – auch für einfache mathematische Algorithmenmodelle – sehr aufwendig und langwierig. Bemerkung: Auch viele andere Algorithmenmodelle führen auf diese gleiche Klasse berechenbarer Funktionen, z.B. rekursive Funktionen, -Kalkül, Turing-Maschinen, Post’sche Normalsysteme, Random-Access-Maschinen, universelle Registermaschinen etc.

Derartige Ergebnisse haben 1936 den Logiker und Mathematiker A. Church veranlasst, folgende – prinzipiell nicht beweisbare – These aufzustellen:

Church’sche These

Die These ist allein dadurch prinzipiell nicht beweisbar, da der Begriff »intuitiv« sich nicht formal fassen lässt.

Bemerkung: Diese These wurde nahezu gleichzeitig unabhängig von mehreren Personen aufgestellt. Sie ist daher auch als Turing-Church-These bekannt.

Dass jede in einem der Algorithmenmodelle berechenbare Funktion auch intuitiv berechenbar ist, ist klar. Die wesentliche Aussage der These besagt, dass jede Funktion, die man intuitiv als berechenbar ansehen würde, tatsächlich auch in jedem dieser Algorithmenmodelle berechenbar ist. Das heißt im Grunde, dass der intuitive Begriff der Berechenbarkeit durch die mathematische Präzisierung korrekt und vollständig erfasst ist.

Definition 6.8 Universelles Algorithmenmodell

Ein Algorithmenmodell heißt universell, wenn es alle berechenbaren Funktionen zu beschreiben gestattet.

Nahezu alle Programmiersprachen, höhere sowie niedere, sind in diesem Sinne universell. Allein Sprachen für Spezialaufgaben, so etwa die Sprache SQL für den Datenbankzugriff, sind in ihrer Reinform nicht universell.

Universelle Sprachen zeichnen sich insbesondere durch folgende Eigenschaften aus:

• Der nutzbare Bereich für die Daten / Parameterwerte ist nicht beschränkt (dabei reicht der Datentyp integer ohne Begrenzung durch ein maxint für diese Eigenschaft aus!).
• Konzepte wie Rekursion oder Iteration mittels while bzw. bedingten Sprüngen erlauben eine (bedingte) Wiederholung von Teilaufgaben.

6.5Interpreter für formale Algorithmenmodelle in Java

Inhalt dieses Kapitels waren unter anderem formale Algorithmenmodelle, die einfache, aber mathematisch rigide Sprachen für Algorithmen definierten. Die »Einfachheit« dieser Modelle ermöglicht es uns, bereits mit geringen Programmierkenntnissen Interpreter für derartige Sprachen bauen zu können, sozusagen unsere eigenen »virtuellen« Maschinen zur Ausführung von Algorithmen.

Wir beginnen mit einer relativ primitiven Realisierung von Markov-Algorithmen in Java. Primitiv soll hier heißen, dass wir keine der »höheren« Sprachkonstrukte von Java nutzen – faktisch benutzen wir noch nicht einmal Objekte und Klassen. Auch verzichten wir auf das Einlesen der Markov-Tafeln von einer Datei und kodieren diese jeweils direkt im Programmtext (eine neue oder geänderte Markov-Tafel erfordert also eine Änderung des Interpreters – softwaretechnisch völlig unbefriedigend, aber leicht darzustellen). Der Vorteil dieser Primitivlösung besteht darin, dass sie sehr einfach in jede Programmiersprache umzusetzen ist, die den Datentyp String sowie einen Feld-Konstruktor besitzt.

6.5.1Java: Markov-Interpreter

Als ersten Schritt definieren wir eine Datenstruktur, die eine Markov-Tafel abspeichern kann. Wir benötigen dafür die Information über die Anzahl Zeilen. Für die zweiten bis fünften Komponenten einzelner Zeilen definieren wir jeweils ein Feld vom passenden Datentyp – die erste Spalte ergibt sich implizit durch das Durchnummerieren. Der Einfachheit halber definieren wir dies als globale Datenstruktur einer Klasse (Programm 6.1). Diese Datenstruktur muss nun geeignet initialisiert werden. Anstelle des eigentlich sinnvollen Einlesens aus einer Datei oder von der Tastatur erfolgt die Initialisierung durch geeignete Konstantenzuweisung an die Feldvariablen.

Programm 6.1 Einfacher Markov-Interpreter in Java

Bei dem Beispiel handelt es sich um die Verdopplung einer Zeichenkette aus Beispiel 6.10 auf Seite 171. Das dort genutzte Symbol − wurde durch den Wert − 1 ersetzt.

Der eigentliche Markov-Interpreter in der Methode run realisiert die Ausführungsvorschrift in einer while-Schleife. Hierzu werden Standardfunktionen von Strings benutzt, um die Position eines Teilwortes zu finden (indexOf), Teil-Strings auszuwählen (substring) und Strings wieder zusammenzusetzen (+). Im Verbose-Modus, der über einen booleschen Parameter beim »Erzeugen« des Interpreters eingeschaltet werden kann, gibt das Programm dabei alle Zwischenschritte aus. Die run-Methode wird schließlich mit dem zu verarbeitenden Wort als Parameter in der main-Methode des Programms aufgerufen.

Ein etwas komplexeres Beispiel, die Multiplikation aus Beispiel 6.11 von Seite 172, zeigt das abschließende Programmfragment, das den Initialisierungsteil aus Programm 6.1 ersetzt:

Das letzte Beispiel zeigt natürlich, wie umständlich es ist, in dieser primitiven Realisierungsvariante eine neue Markov-Tafel zu programmieren (ganz zu schweigen von den bei jeder Änderung notwendigen Compiler-Läufen etc.). Der Leser dieses Buches kann es als gute Fingerübung in Java betrachten, aus dieser Primitivrealisierung ein anspruchvolles Programm mit Einlesen der Markov-Tafeln aus Dateien und der Testwerte von der Tastatur zu erzeugen.

6.5.2Registermaschine in Java

Als etwas anspruchvolleres Beispiel für einen Interpreter eines formalen Maschinenmodells betrachten wir abschließend die Registermaschine. Wir werden dabei auf einige Konzepte von Java zurückgreifen, die erst in Kapitel 12 im Detail eingeführt werden, deren Anwendung jedoch bereits in diesem Kontext sinnvoll ist. Im Zweifelsfall sollte also Kapitel 12 konsultiert oder zu einem späteren Zeitpunkt zu diesem Abschnitt zurückgekehrt werden.

Als wesentliche Abstraktionen bzw. Module einer Registermaschine werden die Konfiguration mit den Registerbelegungen und dem Befehlszähler, die Umsetzung der verschiedenen Befehle sowie die eigentliche Maschine benötigt. Alle diese Abstraktionen werden jeweils als eigenständige Java-Klasse implementiert. Betrachten wir zunächst die Klasse Configuration in Programm 6.2. Ein Objekt dieser Klasse repräsentiert eine konkrete Konfiguration der Registermaschine. Die Variable ic entspricht dabei dem Befehlszähler, das Feld registers nimmt die einzelnen Register auf, wobei registers[0] der Akkumulator ist.

Programm 6.2 Klasse für die Konfiguration

Neben den Variablen umfasst die Klasse noch Methoden zum Rücksetzen der Register (init) sowie zum Auslesen bzw. Ändern der Register (getRegister und setRegister) und des Befehlszählers (getICounter und setICounter). Die Methode incICounter sorgt schließlich für das Weitersetzen des Befehlszählers. Eine Ausgabe der Konfiguration, d.h. der Belegung aller Register, ist über die Methode toString möglich, die eine Zeichenkette mit der textuellen Repräsentation liefert.

Die Befehle werden ebenfalls durch einzelne Klassen implementiert. Dies erleichtert nicht nur das Hinzufügen neuer Befehle, sondern erhöht auch die Übersichtlichkeit, da die eigentliche Funktionalität des Befehls durch die Klasse gekapselt ist. Damit alle Befehle einheitlich behandelt werden können, müssen diese eine gemeinsame Schnittstelle unterstützen. Diese Schnittstelle Instruction in Programm 6.3 definiert nur eine einzige Methode eval, die die Ausführung des jeweiligen Befehls bewirkt. Da ein Befehl immer auf die Konfiguration der Maschine wirkt, muss die Konfiguration als Parameter übergeben werden.

Programm 6.3 Schnittstelle für Befehle

Die Implementierung der konkreten Befehle wollen wir anhand von LOAD und IF c₀=0 GOTO i im Rahmen der Klassen Load bzw. IfGoto veranschaulichen. Für den Befehl LOAD i muss zunächst der Parameter gesichert werden, d.h. das Register, dessen Wert in den Akkumulator zu laden ist. Dieser Parameter wird in der Variablen reg gespeichert und im Rahmen des Konstruktors initialisiert.

Die Methode eval übernimmt die eigentliche Ausführung des Befehls. Für LOAD bedeutet dies, zuerst den Inhalt des Registers registers[reg] in das Register registers[0] zu laden und anschließend den Befehlszähler zu inkrementieren.

Programm 6.4 Implementierung des Befehls LOAD

Für den Befehl IF c₀=0 GOTO i wird die Sprungadresse in der Variablen pos gespeichert. In der Methode eval wird zunächst der Wert des Akkumulators geprüft. Ist dieser gleich 0, so wird der Befehlszähler mit der Sprungadresse belegt, andernfalls einfach auf den nächsten Befehl gesetzt. Da wir – wie später noch zu sehen ist – ein Programm als ein Feld von »Befehlsobjekten« verwalten, beginnt die Ausführung eines Programms immer mit der Position 0. Dementsprechend muss der Befehlszähler bei einem Sprungbefehl GOTO pos in unserer Implementierung auf den Wert pos-1 gesetzt werden.

Programm 6.5 Implementierung des Befehls IF-GOTO

Mithilfe dieser Klassen kann nun die eigentliche Registermaschine implementiert werden (Programm 6.6). Eine solche Maschine umfasst eine Konfiguration (ein Objekt der Klasse Configuration) sowie ein Programm, das als Feld von Objekten, die die Instruction-Schnittstelle unterstützen, realisiert ist (Feld program). Die wichtigste Methode der Registermaschine ist die Methode run. Diese führt den Befehl aus, auf den der Befehlszähler zeigt, indem für diesen Befehl die eval-Methode aufgerufen wird. Da in jedem Befehl der Befehlszähler verändert wird, wird durch wiederholtes Ausführen der Anweisung program[config.getICounter()].eval(config) das gesamte Programm abgearbeitet. Die Abbruchbedingung ist dabei das Erreichen des END-Befehls, der anhand der String-Repräsentation des Befehlsobjektes identifiziert wird.

Die weiteren Methoden der Klasse Machine dienen zum Initialisieren der Konfiguration (Konstruktor), zur Ausgabe der aktuellen Registerbelegung (printConfiguration), zum Zugriff auf die Konfiguration (getConfiguration) sowie zum Initialisieren des Programms (setProgram). Letzteres erzeugt zunächst ein Feld, dessen Größe der Programmlänge entspricht, und kopiert anschließend unter Zuhilfenahme der Java-Systemmethode arraycopy die Befehlsobjekte in dieses Feld.

Programm 6.6 Implementierung der Registermaschine

In Programm 6.7 wird die Ausführung eines Programms der Registermaschine demonstriert. Nachdem eine neue Maschine erzeugt wurde, kann sie mit dem Programm versehen werden. Dieses Programm wird als Feld von Objekten konstruiert, die wiederum durch Aufruf der Konstruktoren der jeweiligen Klasse mit den entsprechenden Parameterwerten erzeugt werden.

Vor der Ausführung werden zunächst die Register in der gewünschten Weise initialisiert. Durch Aufruf der Methode run wird danach das Programm ausgeführt und nach dessen Beendigung abschließend die Endkonfiguration ausgegeben.

Programm 6.7 Programmausführung mit der Registermaschine

Auch diese Implementierung lässt natürlich noch viel Raum für Verbesserungen. So kann beispielsweise das Programm aus einer Datei eingelesen werden oder eine grafische Benutzerschnittstelle hinzugefügt werden, die neben der Inspektion der Registerinhalte auch einen Einzelschrittmodus unterstützt.