Mit dem Begriff berechenbare Zahl werden solche Zahlen ausgezeichnet, bei denen alle Dezimalstellen mit einer Berechnungsvorschrift erzeugt werden können. So ist es insbesondere interessant zu wissen, dass es nicht berechenbare Zahlen gibt. Mit der Church-Turing-These kann man für den Begriff Berechnungsvorschrift die Turingmaschine wählen.

Definition

---

Eine Zahl $r\; \backslash in\; \backslash mathbb\{R\}$ heißt genau dann berechenbar, wenn es eine Turing-Maschine gibt, die für jedes ε > 0 eine Zahl q ausgibt, so dass gilt, die also die Zahl $r$ beliebig genau approximieren kann.

Alle natürlichen Zahlen, rationalen Zahlen und algebraischen Zahlen sind berechenbar, aber auch einige transzendente Zahlen wie z.B. die Kreiszahl π oder Eulersche Zahl e.

Eigenschaften

---

Das Berechnen der nächsten Dezimalstelle kann man mit dem Begriff der Cauchy-Folge darstellen. Somit kann man die berechenbaren Zahlen dadurch charakterisieren, dass man die berechenbaren Cauchy-Folgen auszeichnet.

Existenz nicht berechenbarer Zahlen

---

Da es nur abzählbar viele Turing-Maschinen, aber überabzählbar viele reelle Zahlen gibt, sind die berechenbaren Zahlen eine echte Teilmenge von $\backslash mathbb\{R\}$.

Siehe auch

---

• Berechenbarkeit

Rekursionstheorie

Computable number | Nombre réel calculable | מספר חשיב | Beräkningsbart tal