WHILE-Berechenbarkeit

Eine Funktion ist WHILE-berechenbar, wenn sie durch ein Programm berechnet werden kann, das zusätzlich zu den LOOP-Konstrukten auch WHILE x != 0 DO P END-Schleifen erlaubt. Die Anzahl der Schleifendurchläufe ist hier nicht zwangsläufig im Voraus bekannt, weshalb WHILE-Programme nicht immer terminieren müssen. Dieses Modell ist äquivalent zur Turing-Maschine.