Zahlen sind ein grundlegender Bestandteil der Mathematik, und es gibt von ihnen mehr Typen, als wir uns vorstellen können. Manche Zahlen können wir nicht einmal komplett aufschreiben; transzendente Zahlen wie die Kreiszahl Pi zum Beispiel. Solche Zahlen haben unendlich viele Nachkommastellen, die keinem vorhersagbaren Muster folgen. Aber selbst wenn wir solche Zahlen nie in Gänze kennen oder aufschreiben können, können wir doch einen Algorithmus angeben, mit dem sich alle Nachkommastellen zumindest prinzipiell berechnen ließen.

Formal kann man Berechenbarkeit so definieren:

Eine reelle Zahl a ist berechenbar, wenn sie durch eine berechenbare Funktion f angenähert werden kann, wobei diese Funktion für jede positive ganze Zahl n eine ganze Zahl f(n) liefert, mit der die obige Beziehung erfüllt ist.

Und wenn sich die Mathematik schon die Mühe macht, exakt zu definieren, was »berechenbare Zahlen« sind, dann sollte man auch nicht überrascht sein, dass es auch »unberechenbare Zahlen« gibt. Im Jahr 1936 veröffentlichte der britische Mathematiker Alan Turing eine Arbeit mit dem Titel »On Computable Numbers, with an Application to the ›Entscheidungsproblem‹«. Mit dem »Entscheidungsproblem« ist hier die grundlegende Frage nach Verfahren gemeint, mit denen man entscheiden kann, ob eine vorgegebene Aussage im Rahmen einer bestimmten mathematischen Theorie bewiesen werden kann oder nicht. Mit solchen Problemen hatte sich zuvor schon Kurt Gödel beschäftigt; Alan Turing fand aber einen völlig neuen Zugang. Anstatt der arithmetisch-logischen Sprache von Gödel dachte Turing sich formale »Maschinen«, mit denen er die Frage nach der Entscheidbarkeit lösen wollte. Diese »Turingmaschinen« (wie sie heute genannt werden) sind zwar rein mathematische Objekte, aber gleichzeitig auch ein Modell für reale Computer – die damals natürlich noch nicht vorhanden waren.

Die Frage nach der Berechenbarkeit von Zahlen wird im Kontext der Turingmaschinen zum so genannten »Halteproblem«: Gelangt eine Turingmaschine bei der Abarbeitung eines Algorithmus irgendwann zu einem Ende oder nicht? Für viele Spezialfälle lässt sich diese Frage beantworten. Doch Turing konnte zeigen, dass es keinen allgemeinen Algorithmus gibt, der diese Frage für alle beliebigen Algorithmen beantworten kann. Das Halteproblem ist nicht entscheidbar, und daraus folgt direkt die Existenz von Zahlen, die nicht berechenbar sind. Zum Beispiel die »chaitinsche Konstante«, die die Wahrscheinlichkeit angibt, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält. Sortiert man alle möglichen Algorithmen (beziehungsweise Programme für die Turingmaschine) nach ihrer Länge in Bit und schreibt man die chaitinsche Konstante im Binärsystem, dann erhöht jedes haltende Programm der Länge x die x-te Stelle der Zahl um 1. Da es aber eben nicht möglich ist, für ein beliebiges Programm herauszufinden, ob es anhält oder nicht, ist auch die chaitinsche Konstante nicht berechenbar.

An Turings Arbeit erinnern wir uns heute jedoch weniger auf Grund der Aussagen über (un)berechenbare Zahlen, sondern vielmehr wegen seiner Erfindung der Turingmaschinen. Die theoretischen Einsichten in die formalen Maschinen, die Turing dort gewonnen hatte, führten später zum Bau der ersten echten Computer. Mit ihnen konnten die Briten im Zweiten Weltkrieg die Kommunikation der Nazis entschlüsseln. Und in den Jahrzehnten danach entwickelte sich daraus die computerdominierte Welt, in der wir heute leben. Die (unendlich vielen) unberechenbaren Zahlen bleiben allerdings weiterhin unberechenbar – gleich ob man dazu Papier und Bleistift einsetzt oder einen Computer.