Berechenbare Zahl

Art von definierbarer reeller 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

Bearbeiten

Eine reelle Zahl   heißt berechenbar, wenn es eine berechenbare Funktion gibt, die jeder natürlichen Zahl   eine rationale Zahl   zuordnet, sodass  .

Beispiele und Eigenschaften

Bearbeiten

Alle reellen algebraischen Zahlen sind berechenbar, aber auch viele transzendente Zahlen, z. B. die Kreiszahl   oder die Eulersche Zahl  .

Ein Beispiel einer nicht berechenbaren Zahl ist die Haltezahl. Die Haltezahl sei definiert als diejenige Binärzahl zwischen 0 und 1, deren  -te Stelle nach dem Komma angibt, ob eine Turingmaschine mit Gödelnummer   für die Eingabe   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 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

Bearbeiten