Die Berechenbarkeitstheorie befasst sich als Teilgebiet der theoretischen Informatik (und der mathematischen Logik) befasst sich mit der zentralen Frage, welche Funktionen sich mit welchem (Berechenbarkeits-)Modell berechnen lassen. Es werden dazu Modelle für die Berechenbarkeit und deren Leistungsfähigkeit untersucht.
Im Mittelpunkt steht die Frage, wie man den intuitiven Begriff der Berechenbarkeit formalisieren kann. Als weitgehend anerkannte Antwort hat sich die Turingmaschine als mögliches Model durchgesetzt (Church-Turing-These). Es wurde erkannt, dass die Berechnungsfähigkeit der Turingmaschine gleichmächtig zu vielen anderen Berechnungsmodellen ist.
Welche Aufgaben kann eine Turingmaschine lösen?
Ein Problem heißt entscheidbar, wenn es durch einen Algorithmus, der nach endlich vielen Schritten terminiert, gelöst werden kann. Viele Probleme sind entscheidbar, es sind aber auch viele unentscheidbare Probleme bekannt, hierzu zählen u.a. das Halteproblem oder das Entscheidungsproblem. Nur wenn eine Turingmaschine ein Problem vollständig lösen kann, gilt es als berechenbar.
Weitere Berechenbarkeitsmodelle
Neben der Turingmaschine gibt es verschiedene Modelle, die gleichmächtig zu dieser sind, z. B. die Registermaschine oder ein Kellerautomat mit zwei Kellerspeichern (weitere Modelle: wikipedia).
Im Folgenden soll hier jedoch auf die WHILE- und die GOTO-Berechenbarkeit eingegangen werden.
Hinweis: Bei der Definition von WHILE-Programmen, GOTO-Programmen (und auch z. B. LOOP-Programmen oder Registermaschinen) findet man verschieden umfangreiche Definitionen – je nachdem, wo man sucht (wikipedia, Seiten oder Scripte von verschiedenen Unis, …). In einer puristischen Definition ist z. B. eine Anweisung wie x_i := x_j nicht erlaubt. Da diese jedoch mit zwei drei Zeilen leicht implementiert werden kann, wird eine solche Definition auf einigen Seiten erlaubt … ohne Syntactic Sugar will man nicht in WHILE oder GOTO programmieren. Ähnlich verhält es sich mit der Definition von IF-THEN in WHILE-Programmen.
WHILE-Programme
WHILE-Programme bestehen aus folgenden Zeichen:
- Variablen: x_0 \, x_1 \, x_2 \, . . .
- Konstanten: 0 1 2 . . .
- Operationssymbole: + \, -
- Trennsymbole: ; \, := \, \neq
- Schlüsselwörter: WHILE DO END
Die Syntax von WHILE-Programmen wird wie folgt induktiv definiert:
- Jede Wertzuweisung der Form x_i:= x_j + c oder x_i:= x_j - c ist ein WHILE-Programm, wobei c Konstante ist.
Der Wert der Variablen x_i berechnet sich wie gewohnt aus dem Wert der Variablen x_j vermehrt / vermindert um c; falls der Subrahend größer als der Minuend ist, ist das Ergebnis 0. - Falls P_1 und P_2 WHILE-Programme sind, so sind auch P_1; P_2 und \text{WHILE} \, x_i \neq 0 \, \text{DO} \, P_1 \, \text{END} wieder WHILE-Programme.
Damit sind Konkatenationen und Schachtelungen von WHILE-Programmen möglich. Zu beachten ist, dass mit WHILE nur auf \neq 0 getestet werden darf.
Mit diesen wenigen Vereinbahrungen sind nun (theoretisch) beliebige Programme schreibbar. Theoretisch? Nun ja, ähnlich wie bei der Turingmaschine und der Registermaschine genügt es nachzuweisen, dass Grundfunktionen realisierbar sind.
Die Addition zweier Werte kann in einem WHILE-Programm wie folgt realisiert werden:
x_0 := x_1+0; \\ \text{WHILE} \, x_2 \neq 0 \, \text{DO} \\ \qquad x_0 := x_0+1; \\ \qquad x_2 := x_2−1 \\ \text{END}
Zuweisungen von Konstanten, also x_i := c, sind in WHILE-Programmen nicht direkt möglich. Stattdessen kann man zum Beispiel das folgende Programmschema nehmen:
\text{WHILE} \, x_i \neq 0 \, \text{DO} \\ \qquad x_i := x_i−1 \\ \text{END;} \\ x_i := x_i+c
Ebenso können algorithmische Strukturen, z. B eine Verzweigung der Art \text{IF} \, v \neq 0 \, \text{THEN P END} implementiert werden. Dabei bezeichnen z und v Platzhalter, die in einem konkreten Programm mit richtigen Variablen belegt werden müssten.
z := v + 0; \\ \text{WHILE} z \neq 0 \text{DO} \\ \qquad P; \\ \qquad z := 0 \\ \text{END}
GOTO-Programme
In GOTO-Programmen sind folgende Zeichen und Symbole definiert:
- Variablen: x_0 \, x_1 \, x_2 \, . . .
- Konstanten: 0 1 2 . . .
- Operationssymbole: + \, -
- Trennsymbole: : \, ; \, := \, \neq
- Marken: M_1 \, M_2 \, M_3 \, ...
- Schlüsselwörter: GOTO IF THEN STOP
Die Syntax von GOTO-Programmen ist wie folgt definiert. Ein GOTO-Programm besteht aus einer endlichen Folge von Anweisungen A_i, die jeweils durch eine Marke M_i eingeleitet werden:
\qquad M_1 \, : \, A_1; \\ \qquad M_2 \, : \, A_2; \\ \qquad ... \\ \qquad M_k \, : \, A_k
Dabei ist jede Anweisung A_i \, \text{mit} \, 1 \leq i \leq k von folgender Form:
- Wertzuweisung: x_i := x_j \, ; x_i := x_j + c \, \text{oder} \, x_i := x_j - c, wobei c eine Konstante ist,
- unbedingter Sprung: \text{GOTO} \, M_i,
- bedingter Sprung: \text{IF} \, x_i = c \, \text{THEN GOTO} \, M_i oder
- Stopanweisung: STOP.
GOTO-Anweisungen springen zu der entsprechenden Marke. Die letzte Anweisung im Programm ist entweder STOP oder ein unbedingten Sprung. Ein GOTO-Programm kann einen Wert ausgeben – nach Programmende der Wert von x_0.
GOTO-Programme sind offensichtlich verständlicher für uns, da diese eher Programmen für die Registermaschine ähneln als z. B. WHILE-Programme. In einem (ersten) Beispielprogramm soll die Summe x_1 + x_2 von zwei nicht negativen Zahlen berechnet werden, das Ergebnis steht in x_3 (wikipedia)
M_1 \, : \, x_3 := x_1; \\ M_2 \, : \, x_4 := x_2; \\ M_3 \, : \text{IF} \, x_4 = 0 \, \text{THEN GOTO} \, M_7; \\ M_4 \, : \, x_4 = x_4 - 1; \\ M_5 \, : \, x_3 = x_3 + 1; \\ M_6 \, : \, \text{GOTO} \, M_3; \\ M_7 \, : \, \text{STOP}
Zur Vereinfachung könnte man die nicht benötigten Sprungmarken auch weglassen, d. h. zwingend müssten hier nur M_1, \, M_3 und M_7 angegeben werden.
WHILE- und GOTO-Berechenbarkeit
Welche Funktionen können nun mit GOTO- bzw. WHILE-Programmen berechnet werden? Kann man mit diesen Programmen mehr oder nicht alle Programme einer Turingmaschine implementieren? Gibt es GOTO-Programme, die nicht als WHILE-Programme implementiert werden können?
Für einfache Funktionen gibt es die Möglichkeit, die Programme ineinander umzuwandeln, ein allgemeingültiger Nachweis soll an dieser Stelle nicht erfolgen. Es ist jedoch nachgewiesen, dass alle Funktionen, die mithilfe einer Turingmaschine berechenbar sind auch mithilfe eines GOTO- oder WHILE-Programms berechenbar sind.
Ausgehend von der Church-Turing-These „Jede intuitiv berechenbare Funktion ist auch Turing-berechenbar“ gibt es demzufolge eine GOTO-Berechenbarkeit und WHILE-Berechenbarkeit, die in zueinander äquivalent sind.
