Wir halten fest: Gegeben ein WHILE-Programm \(P\), bezeichnen wir mit \(\textbf{TIME}_P^k\) die partielle Funktion \(\mathbb{N}^k \rightarrow \mathbb{N}\), welche die Ausführungszeit von \(P\) auf der Eingabe beschreibt. Dabei kostet jede Zuweisung einen Schritt, ebenso die Evaluierung der \(\textbf{WHILE}\)-Bedingung. \(\textbf{TIME}_P(a_1,\ldots,a_k)\) ist also die Anzahl der Ausführungsschritte von \(P\) bei Eingaben \(a_1,\ldots,a_k \in \mathbb{N}\) (undefiniert, falls \(P\) auf \(a_1,\ldots,a_k\) nicht terminiert).

Andere Berechnungsmodelle

Es gibt eine Vielzahl von Berechnungsmodellen, die ähnlich formal wie die WHILE-Sprache definiert sind; die folgende Liste ist eine Auswahl.

• GOTO-Programme; diese sind sehr ähnlich zu WHILE-Programmen, erlauben aber anstelle von Schleifen GOTO-Anweisungen.
• Turingmaschinen; das wohl bekannteste und historisch wichtigste Modell.
• Der Lambda-Kalkül; eine sehr mathematische Formalisierung von Berechenbarkeit.
• \(\mu\)-Rekursion; eine wiederum mathematische Formalisierung, welche mit Abschlusseigenschaften arbeitet.

Interessanterweise sind alle diese Berechnungsmodelle äquivalent, das heißt, dieselben Funktionen sind berechenbar in jedem Modell. Außerdem sind in diese Modelle auch äquivalent zur Mächtigkeit moderner Programmiersprachen. Diese Eigenschaft der Programmiersprachen nennt man Turing-Vollständigkeit.

LOOP-Berechenbarkeit

Wir führen jetzt eine Schleife ein, bei der die Anzahl der Schleifendurchläufe bei Schleifeineintritt schon feststeht. Dazu verwenden wir \(\textbf{LOOP }x_i\textbf{ DO }P\textbf{ END}\) mit der Semantik, dass \(P\) genau so oft ausgeführt wird, wie \(x_i\) zum Zeitpunkt des Schleifeneintritts festlegt. Wenn wir keine unbeschränkten Schleifen (WHILE-Schleifen) zulassen, sondern nur LOOP-Schleifen, dann terminiert das Programm immer; solche Programme nennt man LOOP-berechenbar (oder auch primitiv rekursiv). Es gibt allerdings Funktionen, die zwar WHILE-berechenbar sind, jedoch nicht LOOP-berechenbar, zum Beispiel die Ackermannfunktion. Somit hat die LOOP-Sprache (ohne WHILE) einige Vorteile (weil die berechneten Funktionen immer total sind), andereseits aber auch Nachteile (weil einige WHILE-berechenbare Funktionen nicht LOOP-berechenbar sind).

Was haben wir gelernt?

1. WHILE-Programme sind eine Möglichkeit der Formalisierung von Berechnung. Viele andere Formalisierungen sind möglich und äquivalent.
2. Ohne Syntactic Sugar will man nicht in WHILE programmieren.
3. Die Laufzeit von WHILE-Programmen kann man unabhängig von Hardware als Anzahl der ausgeführten Befehle definieren.
4. Restriktivere Berechnungsmodelle sind selten, ermöglichen aber teilweise andere interessante Eigenschaften (zum Beispiel, dass alle Programme terminieren).

Bonus: Geschichte der Berechnungsmodelle