Berechenbare Zahl
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 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 beliebig genau approximieren kann.
Eigenschaften
Alle natürlichen, rationalen und algebraischen Zahlen sind berechenbar, aber auch einige transzendente Zahlen, z.B. die Kreiszahl ? oder die Eulersche Zahl e.
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) berechnenbare Zahl ist insofern gleichbedeutend mit dem Grenzwert ihrer Cauchy-Folge, man kann also die berechenbaren Zahlen durch die entsprechenden berechenbaren Cauchy-Folgen definieren.
Siehe auch
Berechenbarkeit
