Kurs:Algorithmen und Datenstrukturen/Vorlesung/Definiertheit

Definiertheit von imperativen Algorithmen

Gegeben ist folgender Algorithmus:

$f(x):=ifx==0then0elsef(x-1)$

Auf welchen Eingaben ist der Algorithmus definiert?

Auswertung:

$f(0)\to 0$

$f(1)\to f(0)\to 0$

$f(2)\to f(1)\to f(0)\to 0$

$f(x)\to 0\mathrm{\forall }x\in int,x>0$

$f(-1)\to f(-2)\to ...$ Diese Auswertung terminiert nicht!

Somit gilt:

$f(x):=\{\begin{array}{cc}0& fallsx\ge 0\\ \mathrm{\perp }& sonst\end{array}$