imported>MArcus Sinus: + Link zu Journal of Symbolic Logic

2024-11-14T14:56:40Z

+ Link zu Journal of Symbolic Logic

Neue Seite

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 <math>r</math> heißt ''berechenbar'', wenn es eine [[Berechenbarkeit|berechenbare Funktion]] gibt, die jeder natürlichen Zahl <math>i</math> eine rationale Zahl <math>q</math> zuordnet, sodass <math>\left|r-q\right|<\frac{1}{i}</math>.

== Beispiele und Eigenschaften ==
Alle reellen [[Algebraische Zahl|algebraischen]] Zahlen sind berechenbar, aber auch viele [[Transzendente Zahl|transzendente]] Zahlen, z. B. die [[Kreiszahl]] <math>\pi</math> oder die [[Eulersche Zahl]] <math>\mathrm e</math>.

Ein Beispiel einer nicht berechenbaren Zahl ist die Haltezahl. Die Haltezahl sei definiert als diejenige [[Binärzahl]] zwischen 0 und 1, deren {{nowrap|<math>i</math>-te}} Stelle nach dem Komma angibt, ob eine [[Turingmaschine]] mit [[Gödelnummer]] <math>i</math> für die Eingabe <math>i</math> terminiert (1) oder nicht (0). Die Haltezahl ist nicht berechenbar, denn das [[Halteproblem]] ist [[entscheidbar|unentscheidbar]].

Da jedes Programm einer Turingmaschine endlich ist und nur aus endlich vielen Zeichen besteht, gibt es nur [[Abzählbarkeit|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 [[Inverses Element|Inverse]] jeder berechenbaren Zahl wieder berechenbar ist, bilden die berechenbaren Zahlen einen [[Körper (Algebra)|Teilkörper]] der reellen Zahlen.

== Literatur ==
* {{Literatur
| Autor = [[Alan Turing]]
| Titel = On Computable Numbers, with an Application to the Entscheidungsproblem
|Sammelwerk=Proceedings of the London Mathematical Society
| Band = 42
| Datum = 1937
| Seiten = 230–265
| DOI = 10.1112/plms/s2-42.1.230
}}
* {{Literatur
| Autor = Alan Turing
| Titel = On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
|Sammelwerk=Proceedings of the London Mathematical Society
| Band = 43
| Datum = 1938
| Seiten = 544–546
| DOI = 10.1112/plms/s2-43.6.544
}}
* {{Literatur
| Autor = [[Ernst Specker]]
| Titel = Nicht konstruktiv beweisbare Sätze der Analysis
|Sammelwerk=[[Journal of Symbolic Logic|The Journal of Symbolic Logic]]
| Band = 14
| Nummer = 3
| Datum = 1949
| Seiten = 145–158
| DOI = 10.2307/2267043
}}
* {{Literatur
| Autor = [[Klaus Weihrauch]]
| Titel = Computable analysis: an introduction
| Verlag = Springer
| Ort = Berlin
| Jahr = 2000
| ISBN = 3-540-66817-9
}}
* {{Literatur
| Autor = [[Roger Penrose]]
| Titel = Computerdenken
| Verlag = Spektrum Verlag
| Ort = Heidelberg
| Jahr = 2002
| ISBN = 3-89330-708-7
}}

[[Kategorie:Berechenbarkeitstheorie]]
[[Kategorie:Analysis]]

Berechenbare Zahl - Versionsgeschichte

imported>MArcus Sinus: + Link zu Journal of Symbolic Logic