www.wikidata.de-de.nina.az

Berechenbare Zahl Als berechenbare Zahl wird eine reelle Zahl bezeichnet wenn es eine Berechnungsvorschrift gibt die App

Berechenbare 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

  • Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. Band 42, 1937, S. 230–265, doi:10.1112/plms/s2-42.1.230.
  • Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction. In: Proceedings of the London Mathematical Society. Band 43, 1938, S. 544–546, doi:10.1112/plms/s2-43.6.544.
  • Ernst Specker: Nicht konstruktiv beweisbare Sätze der Analysis. In: The Journal of Symbolic Logic. Band 14, Nr. 3, 1949, S. 145–158, doi:10.2307/2267043.
  • Klaus Weihrauch: Computable analysis: an introduction. Springer, Berlin 2000, ISBN 3-540-66817-9.
  • Roger Penrose: Computerdenken. Spektrum Verlag, Heidelberg 2002, ISBN 3-89330-708-7.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 BearbeitenEine reelle Zahl r displaystyle r nbsp heisst berechenbar wenn es eine berechenbare Funktion gibt die jeder naturlichen Zahl i displaystyle i nbsp eine rationale Zahl q displaystyle q nbsp zuordnet sodass r q lt 1 i displaystyle left r q right lt frac 1 i nbsp Beispiele und Eigenschaften BearbeitenAlle reellen algebraischen Zahlen sind berechenbar aber auch viele transzendente Zahlen z B die Kreiszahl p displaystyle pi nbsp oder die Eulersche Zahl e displaystyle mathrm e nbsp Ein Beispiel einer nicht berechenbaren Zahl ist die Haltezahl Die Haltezahl sei definiert als diejenige Binarzahl zwischen 0 und 1 deren i displaystyle i nbsp te Stelle nach dem Komma angibt ob eine Turingmaschine mit Godelnummer i displaystyle i nbsp fur die Eingabe i displaystyle i nbsp 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 abzahlbar viele solcher Programme und also auch nur abzahlbar 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 Teilkorper der reellen Zahlen Literatur BearbeitenAlan Turing On Computable Numbers with an Application to the Entscheidungsproblem In Proceedings of the London Mathematical Society Band 42 1937 S 230 265 doi 10 1112 plms s2 42 1 230 Alan Turing On Computable Numbers with an Application to the Entscheidungsproblem A Correction In Proceedings of the London Mathematical Society Band 43 1938 S 544 546 doi 10 1112 plms s2 43 6 544 Ernst Specker Nicht konstruktiv beweisbare Satze der Analysis In The Journal of Symbolic Logic Band 14 Nr 3 1949 S 145 158 doi 10 2307 2267043 Klaus Weihrauch Computable analysis an introduction Springer Berlin 2000 ISBN 3 540 66817 9 Roger Penrose Computerdenken Spektrum Verlag Heidelberg 2002 ISBN 3 89330 708 7 Abgerufen von https de wikipedia org w index php title Berechenbare Zahl amp oldid 234607241