Damit wurde Alan Turing berühmt: Die Lösung des “Halteproblems”. EIn Nachtrag zu Turings hundertsten Geburtstag (über den ich bereits beim letzten Mal geschrieben habe).
Manche Computerberechnungen haben ein Ergebnis, andere laufen ewig weiter. Die Frage, ob es eine eindeutige Methode gibt, schon im Vorhinein zwischen diesen beiden Fällen zu unterscheiden, ist das „Halteproblem”. Alan Turing hat es gelöst.
Das Problem wurde freilich schon formuliert, als es noch lange keine Computer gab. Die Mathematik kannte schließlich auch schon vorher komplizierte Algorithmen – Kombinationen von Rechenregeln, die man nach einem festen Schema abarbeitet, um auf ein Ergebnis zu kommen. In der Schule haben wir zum Beispiel Algorithmen gelernt, mit denen wir große Zahlen per Hand multiplizieren konnten. Ziffer für Ziffer haben wir die Zahlen nach bestimmten Regeln bearbeitet, am Ende kam eine Zahl heraus – im optimalen Fall die richtige.
Das Collatz-Problem
Bei so einem Algorithmus ist es recht leicht zu zeigen, dass er ein Ergebnis haben wird. Es gibt aber auch Algorithmen, die möglicherweise nie auf ein Ende führen. Ein schönes Beispiel für so einen Algorithmus mit ungewissem Ausgang ist das Collatz-Problem: Wir beginnen mit einer beliebigen natürlichen Zahl. Wenn sie gerade ist, teilen wir sie durch zwei. Wenn sie ungerade ist, multiplizieren wir sie mit drei und addieren eins. Mit der Zahl, die wir nun bekommen haben, gehen wir genauso vor.
Beispiel: Wir beginnen mit 7 – ungerade, daher: 3×7+1=22. 22 ist gerade, das führt auf 11. Weiter geht’s mit 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Die Collatz-Vermutung ist, dass man mit diesen Rechenregeln immer bei der 1 landet, egal mit welcher Zahl man beginnt. Doch lässt sich das beweisen? Gibt es eine Methode, die zuverlässig entscheidet, ob meine Rechenregeln auf ein Ende führen werden, oder ich vielleicht auf Zahlen stoße, die mich unendlich im Kreis schicken?
Im Fall des Collatz-Problems fehlt die Antwort noch immer. Alan Turing hat allerdings ganz allgemein gezeigt, dass es keine Rechenvorschrift (heute sagt man meistens: kein Computerprogramm) geben kann, um von beliebigen Rechenprozeduren zu entscheiden, ob sie zu einem Ende kommen werden. Das gelang ihm, indem er die Frage stellte: Was würde geschehen, wenn es ein solches Programm gäbe, und man dieses Programm sich selbst untersuchen ließe?
Wie sich zeigen lässt, führt dieser Gedanke auf einen logischen Widerspruch.
Mehr dazu hier auf www.naklar.at.
Werden Sie naklar-Fan auf Facebook
Kommentare (10)