Berechenbare Zahl

Als berechenbare Zahl wird eine reelle Zahl bezeichnet, wenn es eine Berechnungsvorschrift gibt, die jede ihrer Dezimalstellen erzeugen kann. Insbesondere gibt es nicht-berechenbare Zahlen.

Inhaltsverzeichnis

Definition

Eine reelle Zahl r heißt berechenbar, wenn die Funktion, die jeder ganzen Zahl i die i-te Stelle der Binärdarstellung von r zuordnet, berechenbar ist.

Dabei wird ein Berechnungsmodell vorausgesetzt, zum Beispiel die Turingmaschinen.

Eigenschaften

Alle natürlichen, rationalen und algebraischen Zahlen sind berechenbar, aber auch viele transzendente Zahlen, z. B. die Kreiszahl π oder die Eulersche Zahl e. Die Haltezahl sei definiert als diejenige Binärzahl zwischen 0 und 1, deren i-te Stelle nach dem Komma angibt, ob die i-te Turingmaschine für die Eingabe i terminiert (1) oder nicht (0). Die Haltezahl ist nicht berechenbar, denn das Halteproblem ist unentscheidbar.

Sind die Phasen einer Turingmaschine so eingerichtet, dass sie jeweils die nächste Dezimalstelle ausgeben, so stimmt dies mit einem elementaren Interpolationsverfahren überein. Die jeweilige (auch irrationale) berechenbare Zahl ist insofern gleichbedeutend mit dem Grenzwert ihrer Cauchy-Folge, man kann also die berechenbaren Zahlen durch die entsprechenden berechenbaren Cauchy-Folgen definieren.

Da jedes Programm einer Turingmaschine endlich ist und nur aus endlich vielen Zeichen besteht, gibt es nur abzählbar vieler 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.

Siehe auch

Literatur

Roger Penrose: Computerdenken. Spektrum Verlag, Heidelberg 2002, ISBN 3893307087.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Berechenbare Funktion — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Berechenbar — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Turing-Berechenbarkeit — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Berechenbarkeit — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Konstruktivistische Mathematik — Der mathematische Konstruktivismus ist eine Richtung der Philosophie der Mathematik, die den Standpunkt vertritt, dass mathematische Aussagen keine Beschreibung von ontologischen Objekten sind, die unabhängig von unserem Denken existieren,… …   Deutsch Wikipedia

  • Mathematischer Konstruktivismus — Der mathematische Konstruktivismus ist eine Richtung der Philosophie der Mathematik, die den Standpunkt vertritt, dass mathematische Aussagen keine Beschreibung von ontologischen Objekten sind, die unabhängig von unserem Denken existieren,… …   Deutsch Wikipedia

  • Chaitins Konstante — Die chaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält. Ω ist ein Beispiel für eine nicht berechenbare Zahl. Sie ist nach Gregory Chaitin definiert als wobei die Summe… …   Deutsch Wikipedia

  • Chaitinsche Konstante — Die chaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält. Ω ist ein Beispiel für eine nicht berechenbare Zahl. Sie ist nach Gregory Chaitin definiert als wobei die Summe… …   Deutsch Wikipedia

  • Konstruktive Mathematik — Der mathematische Konstruktivismus ist eine Richtung der Philosophie der Mathematik, die den Standpunkt vertritt, dass mathematische Aussagen keine Beschreibung von ontologischen Objekten sind, die unabhängig von unserem Denken existieren,… …   Deutsch Wikipedia

  • Ackermann-Funktion — Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer und Berechnungsmodellen aufgezeigt werden können. Heute… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”