Berechenbare Zahl

Als berechenbare Zahl wird eine reelle Zahl bezeichnet, wenn es eine Berechnungsvorschrift gibt, die Approximationen zu jeder vorgegebenen Genauigkeit liefern kann. Insbesondere gibt es nicht-berechenbare Zahlen.

Definition

Eine reelle Zahl $r$ heißt berechenbar, wenn es eine berechenbare Funktion gibt, die jeder natürlichen Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} eine rationale Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} zuordnet, sodass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|r-q\right|<\frac{1}{i}} .

Beispiele und Eigenschaften

Alle reellen algebraischen Zahlen sind berechenbar, aber auch viele transzendente Zahlen, z. B. die Kreiszahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} oder die Eulersche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm e} .

Ein Beispiel einer nicht berechenbaren Zahl ist die Haltezahl. Die Haltezahl sei definiert als diejenige Binärzahl zwischen 0 und 1, deren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -te Stelle nach dem Komma angibt, ob eine Turingmaschine mit Gödelnummer $i$ für die Eingabe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} terminiert (1) oder nicht (0). Die Haltezahl ist nicht berechenbar, denn das Halteproblem ist unentscheidbar.

Da jedes Programm einer Turingmaschine endlich ist und nur aus endlich vielen Zeichen besteht, gibt es nur abzählbar viele solcher Programme und also auch nur abzählbar viele berechenbare Zahlen. Da, wie man sich leicht überlegt, die Summe und das Produkt zweier berechenbarer Zahlen wieder berechenbar ist, und zudem das Inverse jeder berechenbaren Zahl wieder berechenbar ist, bilden die berechenbaren Zahlen einen Teilkörper der reellen Zahlen.

Literatur

• Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. Band 42, 1937, S. 230–265, doi:10.1112/plms/s2-42.1.230. 
• Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction. In: Proceedings of the London Mathematical Society. Band 43, 1938, S. 544–546, doi:10.1112/plms/s2-43.6.544. 
• Ernst Specker: Nicht konstruktiv beweisbare Sätze der Analysis. In: The Journal of Symbolic Logic. Band 14, Nr. 3, 1949, S. 145–158, doi:10.2307/2267043. 
• Klaus Weihrauch: Computable analysis: an introduction. Springer, Berlin 2000, ISBN 3-540-66817-9. 
• Roger Penrose: Computerdenken. Spektrum Verlag, Heidelberg 2002, ISBN 3-89330-708-7.