While-Programmiersprache als Berechnungsmodell
Programmiersprachen als Ausgangspunkt
Es liegt ebenfalls nahe, sich Programmiersprachen als Ausgangspunkt zu wählen, um die Idee "Computer" zu erfassen?
Wir werden hier die sehr einfache Programmiersprache While betrachten, die nur wenige Programmierkonstrukte
zur Verfügung stellt.
Hier ein erstes Programm der Programmiersprache While.
x0 = x1
while x2 != 0:
x0 = x0 + 1
x2 = x2 - 1
#while
Variablen dürfen nur in der folgenden Form gebildet werden:
x0,x1,x2, ...
Als Konstanten können alle natürlichen Zahlen benutzt werden:
0,1,2, ...
Es dürfen nur folgende Rechenoperationen verwendet werden:
+,-
Zuweisungen müssen eine der folgenden Gestalten haben:
variable = konstante
variable = variable
variable = variable + konstante
variable = variable - konstante
Anweisungen können (in verschiedenen Zeilen) sequentiell hintereinander geschrieben werden.
Mit der Anweisung
while bedingung:
...
#while
können Wiederholungen modelliert werden. Die drei Punkte ... stehen für eine beliebige Sequenz von Anweisungen. Wir werden diese Sequenz - wie in Python üblich - einrücken.
Als Bedingung sind nur Ausdrücke der Gestalt
variable != 0
erlaubt.
Die Programmiersprache While ist eine sehr einfache Programmiersprache, die nur mit den oben genannten Programmierelementen auskommt.
Aufgabe 1
Was leistet das oben gezeigte While-Programm? Stelle eine Vermutung auf. Überprüfen kannst du sie mit einem geeigneten Python-Programm.
# Initialisierung der Variablen
x0 = 0
x1 = 3
x2 = 7
# While-Programm
x0 = x1
while x2 != 0:
x0 = x0 + 1
x2 = x2 - 1
#while
# Ausgabe der Variablen
print('x0: ', x0)
print('x1: ', x1)
print('x2: ', x2)
Aufgabe 2
Entwickle ein While-Programm zur Lösung eines der folgenden Berechnungsprobleme:
(a) Verdopplungsproblem: Berechnet werden soll die Verdopplungsfunktion f: N -> N mit f(n) = 2*n.
(b) Multiplikationsproblem: Berechnet werden soll die Multiplikationsfunktion f: N, N -> N mit f(n1, n2) = n1 * n2.
(c) Divisionsproblem: Berechnet werden soll die Divisionsfunktion f: N, N -> N mit f(n1, n2) = n1 // n2, sofern n2 ungleich 0 ist, bzw. f(n1, n2) ist nicht definiert, sofern n2 gleich 0 ist.
Fachkonzept - While-Berechenbarkeit
Der Begriff der While-Berechenbarkeit lässt sich jetzt wie folgt präzisieren.
Eine (k-stellige) Funktion f: N, ..., N -> N heißt While-berechenbar genau dann, wenn gilt: Es gibt ein While-Programm mit der folgenden Eigenschaft:
Ausgangszustand: Die Variablen x1, ..., xk verwalten die zu verarbeitenden natürlichen Zahlen n1, ..., nk.
{x0 -> 0; x1 -> 7; x2 -> 3; ...}
Fall 1: f(n1, ..., nk) ist definiert.
Zielzustand: Die Variable x0 verwaltet den Funktionswert f(n1, ..., nk).
{x0 -> 10; x1 -> ...; x2 -> ...; ...}
Fall 2: f(n1, ..., nk) ist nicht definiert.
Zielzustand: Die Ausführung des While-Programms hält nicht.
Aufgabe 3
Formuliere die Berechenbarkeitsergebnisse aus Aufgabe 1 und Aufgabe 2 mit dem neu eingeführten Begriff.