Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 82

Das erste Beispiel soll zeigen, dass die Bestimmung der Bedeutung keine einfache Aufgabe ist. Wir betrachten folgenden Algorithmus:

f(x) = if x > 100 then x − 10 else f(f(x + 11)) fi

Um einen ersten Eindruck zu bekommen, betrachten wir ein paar Beispielberechnungen:

f(100)		f(f(111)) f(101) 91
f(99)		f(f(110)) f(100) … 91
…		… 91

Tatsächlich gilt die folgende Äquivalenz:

f(x) = if x > 100 then x − 10 else 91 fi

Aufgrund dieser Äquivalenz und seines »Erfinders« ist dieser Algorithmus auch als McCarthys 91-Funktion bekannt. Der Beweis dieser Äquivalenz ist allerdings nicht ganz einfach! In Abschnitt 7.2 werden wir anhand dieser Funktion die Korrektheit applikativer Algorithmen behandeln (Beispiel 7.7 auf Seite 207).

Dieses Beispiel zeigt ein erstes Problem auf, mit dem wir uns später noch intensiver beschäftigen werden: Wie kann bewiesen werden, dass ein gegebener applikativer Algorithmus eine gegebene mathematische Funktion als Semantik hat, oder auch wie kann man die Äquivalenz zweier applikativer Algorithmen beweisen?

Das folgende Beispiel zeigt, dass bereits bei einfachen Funktionen diese Beweisführung kritisch ist.