While-Berechenbarkeit
Ein While-Programm besteht aus folgenden Komponenten:
Variablen: x0, x1, x2, ... Operationszeichen: +, -, =, !=
Sonderzeichen: ;, {, }, (, ) Schlüsselwörter: while
1. Eine Wertzuweisung der Form xi = xj + c; oder xi = xj - c; (c Konstante) ist ein While-Programm
2. Falls P1 und P2 While-Programme sind, so auch P1;P2
3. Falls P While-Programm ist, so ist auch
4. Nur die durch 1-3 beschiebenen Konstrukte sind While-Programme
Wertzuweisung: xi erhält Wert von xj ± c
Sequenz: erst wird P1 ausgeführt, dann P2
Schleife: P wird so lange ausgeführt, bis xi = 0 gilt. Test vor P-Ausführung
Eingabewerte sind Werte der Variablen x1, ..., xn, alle anderen zunächst 0
Syntax von While-Programmen, induktive Definition: