Ich bin vor Kurzem auf diese Formel gestoßen:

Man sieht sofort, dass es sich um eine rekursive Formel handelt. Das heißt: Will man den Wert M für eine ganze positive Zahl n berechnen, muss man M zuerst für einen anderen Wert von n bestimmen. Jedenfalls wird die Berechnung sehr einfach, wenn n größer als 100 ist; dann braucht es nämlich nur eine simple Subtraktion.

Werfen wir aber einen Blick auf den interessanteren Fall, bei dem n kleiner oder gleich 100 ist, zum Beispiel für n = 99. Die Formel sagt uns, dass wir zuerst M(M(110)) bestimmen müssen. Für n = 110 liefert die Formel das Ergebnis M = 100; wir müssen also M(100) bestimmen, was uns die nächste Rekursion liefert. Wir berechnen M(M(111)), was zu M(101) führt und schließlich das Ergebnis M = 91 liefert.

Für n = 99 war die Rechnung noch vergleichsweise einfach. Dass in dieser Formel noch sehr viel mehr steckt, lässt sich erkennen, wenn man einen anderen Wert für n ausprobiert, zum Beispiel n = 42. Die Rechnung führt zuerst in die Rekursion M(M(53)). Das lässt sich aber noch nicht direkt auswerten, sondern liefert M(M(M(64))). Und so weiter: Wir müssen erstaunlich viele Rekursionen ineinanderschachteln, bevor wir zu einem Ergebnis kommen. Es empfiehlt sich, diese Arbeit von einem Computer erledigen zu lassen. Am Ende aber wird man feststellen, dass auch hier das Resultat M = 91 lautet.

Tatsächlich kann man zeigen, dass das Ergebnis immer M = 91 lautet, solange n kleiner oder gleich 100 ist und auch für n = 101 erhält man M = 91. Erst danach steigt der Wert für M schrittweise an: M(102) = 92, M(103) = 93, und so weiter. Man könnte aus mathematischer Sicht die komplexe Rekursion M(M(n+11)) in der Formel auch einfach durch »91« ersetzen und hätte eine sehr viel simplere Gleichung. Das war aber gar nicht das, was der Informatiker John McCarthy im Sinn hatte, als er sich diese Gleichung in den 1960er Jahren ausgedacht hat. Er war ganz speziell an einer rekursiven, verschachtelten Formel interessiert, bei der es unter Umständen sehr lange dauert, bis man ein Ergebnis erhält.

Einen Programmprüfer überprüfen

Wer selbst schon einmal Computerprogramme verfasst hat, wird wissen, dass Rekursionen dort eine wichtige Rolle spielen. Ebenso wichtig ist es, Bescheid zu wissen, ob sich ein Programm in so einer Rekursion verlieren kann und in eine Endlosschleife gerät – oder ob der Rechenprozess irgendwann ein Ende haben wird. Die mittlerweile »McCarthy-91-Funktion« genannte Gleichung mag zwar aus rein mathematischer Sicht eine sinnlose Formel sein, die sich leicht vereinfachen lässt. In der Informatik findet sie aber durchaus sinnvolle Anwendung.

Am kniffligsten beim Programmieren sind meistens die Ereignisse, mit denen man nicht gerechnet hat. Ein Programm mag für die meisten Fälle funktionieren, es kann aber auch Umstände geben, an die man beim Programmieren gar nicht gedacht hat. Die McCarthy-91-Formel illustriert das recht gut: Sie funktioniert problemlos, aber nur, wenn die Zahl n größer als 100 ist. Andernfalls wird es sehr schnell sehr kompliziert.

In der Praxis sind die Dinge natürlich nicht immer so einfach, aber auch hier kann es oft genug vorkommen, dass ein Algorithmus in den meisten Fällen das macht, was er soll; für bestimmte Eingabewerte aber plötzlich ein Verhalten zeigt, mit dem man nicht gerechnet hat. Deswegen braucht es Methoden, die Computerprogramme prüfen. Sie können zum Beispiel festzustellen, ob ein Algorithmus wirklich für alle möglichen Eingabewerte zu einem Ergebnis kommt. Für die Entwicklung dieser Methoden braucht es »sinnlose« Formeln wie die McCarthy-91-Funktion: Sie dienen als Testfall, ob die Methoden zur Beurteilung einer Programmierstrategie funktionieren.