Stichpunkte

Allgemein
	insbesondere in Zusammenhang mit Berechenbarkeit. Inhaltsverzeichnis showTocToggle("Anzeigen"
	WHILE-Programme spielen in der Theoretischen Informatik eine Rolle
	"Verbergen") 1 Syntax 2 Kleenesche Normalform für WHILE-Programme 3 Konsequenzen 4 Siehe auch [Bearbeiten]
Syntax
	x_i ne 0
	|
	x_i := x_j - c
	P
	|
	WHILE-Programme haben folgende Syntax in Backus-Naur-Form: <math>P ::= x_i := x_j + c
	mathrm{DO}
	mathrm{WHILE}
	mathrm{END}<math> <math>WHILE<math> ist die Menge aller WHILE-Programme gemäß obiger Definition
	|
	P;P
	Jede WHILE-berechenbare Funktion ist GOTO-berechenbar und umgekehrt sowie turingberechenbar. [Bearbeiten]
Kleenesche Normalform für WHILE-Programme
	Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden
	Beweis: Sei <math>P<math> ein beliebiges WHILE-Programm
	um ein äquivalentes GOTO Programm <math>P'<math> zu erhalten und dann wieder zurück in ein äquivalentes WHILE-Programm <math>P''<math>
	Wir formen <math>P<math> zunächst um
	Per Konstruktion hat dieses nur eine WHILE-Schleife. [Bearbeiten]
Konsequenzen
	hat zur Konsequenz
	wie ein beliebiges BASIC-Programm
	Die einfach beweisbare Tatsache
	dass ein beliebiges Pascal-Programm die gleichen Leistungen erbringen kann
	dass jedes Goto-Programm in ein While-Programm überführt werden kann und umgekehrt
	dass man beweisen kann
	Und zeigt
	dass man jedes Programm auch strukturiert programmieren kann
	ohne Spagetticode zu erzeugen. [Bearbeiten]
Siehe auch
	LOOP-Programm µ-Rekursion

Dieser Artikel basiert auf dem Artikel WHILE-Programm aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.