In der Mathematik, besonders theoretischen Informatik und mathematischen Logik, sind die berechenbaren Zahlen, auch bekannt als die rekursiven Zahlen oder der berechenbare reals, die reellen Zahlen, die zu innerhalb jeder gewünschten Präzision durch einen begrenzten, endenden Algorithmus geschätzt werden können. Gleichwertige Definitionen können mit μ-recursive Funktionen, Maschinen von Turing oder λ-calculus als die formelle Darstellung von Algorithmen gegeben werden. Die berechenbaren Zahlen bilden ein echtes geschlossenes Feld und können im Platz von reellen Zahlen für viele, aber nicht alle, mathematische Zwecke verwendet werden.

Informelle Definition mit einer Maschine von Turing als Beispiel

Im folgenden definiert Marvin Minsky die Zahlen, die gewissermaßen ähnlich denjenigen zu schätzen sind, die von Alan Turing 1936, d. h. als "Folgen von Ziffern definiert sind, die als Dezimalbrüche" zwischen 0 und 1 interpretiert sind:

: "Eine berechenbare Zahl [ist] ein, für den es eine Maschine von Turing gibt, die, gegeben n auf seinem anfänglichen Band, mit der n-ten Ziffer dieser Zahl [verschlüsselt auf seinem Band] endet." (Minsky 1967:159)

Die Schlüsselbegriffe in der Definition sind (1), dass ein n am Anfang, (2) für jeden n angegeben wird, nimmt die Berechnung nur eine begrenzte Zahl von Schritten, nach denen die Maschine die gewünschte Produktion erzeugt und endet.

Eine abwechselnde Form (2) - die Maschine druckt nacheinander den ganzen n der Ziffern auf seinem Band, das Hinken nach dem Druck des n - betont die Beobachtung von Minsky: (3), Dass durch den Gebrauch einer Maschine von Turing eine begrenzte Definition - in der Form des Tisches der Maschine - verwendet wird, um zu definieren, was eine potenziell unendliche Reihe von dezimalen Ziffern ist.

Das ist jedoch nicht die moderne Definition, die nur verlangt, dass das Ergebnis zu innerhalb jeder gegebenen Genauigkeit genau ist. Die informelle Definition ist oben einem sich rundenden Problem genannt das Dilemma des Tabellenschöpfers unterworfen, wohingegen die moderne Definition nicht ist.

Formelle Definition

Eine reelle Zahl zu sein, der gesagt ist, um berechenbar zu sein, wenn ihm durch etwas berechenbare Funktion auf die folgende Weise näher gekommen werden kann: In Anbetracht jeder ganzen Zahl erzeugt die Funktion eine ganze Zahl k solch dass:

:

Es gibt zwei ähnliche Definitionen, die gleichwertig sind:

• Dort besteht eine berechenbare Funktion, die, in Anbetracht jedes positiven vernünftigen gebundenen Fehlers, eine rationale Zahl r solch dass erzeugt
• Es gibt eine berechenbare Folge von rationalen Zahlen, die zum solchem dass zusammenlaufen

Es gibt eine andere gleichwertige Definition von berechenbaren Zahlen über berechenbare Kürzungen von Dedekind. Ein berechenbarer Dedekind hat geschnitten ist eine berechenbare Funktion, die, wenn versorgt, mit einer rationalen Zahl weil Eingang zurückgibt oder, die folgenden Bedingungen befriedigend:

::::

Ein Beispiel wird durch ein Programm D angeführt, das die Würfel-Wurzel 3 definiert. Das Annehmen davon wird definiert durch:

::

Eine reelle Zahl ist berechenbar, wenn, und nur wenn es KürzungsD eines berechenbaren Dedekinds gibt, der dazu zusammenläuft. Die Funktion D ist für jede vernunftwidrige berechenbare Zahl einzigartig (obwohl natürlich zwei verschiedene Programme dieselbe Funktion zur Verfügung stellen können).

Eine komplexe Zahl wird berechenbar genannt, wenn seine echten und imaginären Teile berechenbar sind.

Eigenschaften

Während der Satz von reellen Zahlen unzählbar ist, ist der Satz von berechenbaren Zahlen nur zählbar, und so sind fast alle reellen Zahlen nicht berechenbar. Die berechenbaren Zahlen können durch das Zuweisen einer Zahl von Gödel jeder Maschinendefinition von Turing aufgezählt werden. Das gibt eine Funktion vom naturals bis den berechenbaren reals. Obwohl die berechenbaren Zahlen ein bestelltes Feld sind, ist der Satz von Zahlen von Gödel entsprechend berechenbaren Zahlen nicht selbst berechenbar enumerable, weil es nicht möglich ist effektiv zu bestimmen, welche Zahlen von Gödel Maschinen von Turing entsprechen, die berechenbaren reals erzeugen. Um einen berechenbaren echten zu erzeugen, muss eine Maschine von Turing eine Gesamtfunktion schätzen, aber das entsprechende Entscheidungsproblem ist im Grad von Turing 0′′. so kann das diagonale Argument des Kantoren nicht verwendet werden, um unzählbar viele berechenbare reals zu erzeugen; bestenfalls, der von dieser Methode gebildete reals wird unberechenbar sein.

Die arithmetischen Operationen auf berechenbaren Zahlen sind selbst im Sinn berechenbar, dass, wann auch immer reelle Zahlen a und b dann berechenbar sind, die folgenden reellen Zahlen auch berechenbar sind: + b, - b, ab, und a/b, wenn b Nichtnull ist.

Diese Operationen sind wirklich gleichförmig berechenbar; zum Beispiel gibt es eine Maschine von Turing, die auf dem Eingang (A, B,) Produktion r erzeugt, wo A die Beschreibung einer Maschine von Turing ist, die a näher kommt, ist B die Beschreibung einer Maschine von Turing, die b näher kommt, und r ist eine Annäherung von a+b.

Die berechenbaren reellen Zahlen teilen alle Eigenschaften der in der Analyse verwendeten reellen Zahlen nicht. Zum Beispiel braucht das einer begrenzten zunehmenden berechenbaren Folge von berechenbaren reellen Zahlen gebundene am wenigsten obere keine berechenbare reelle Zahl (Brücken und Richman, 1987:58) zu sein. Eine Folge mit diesem Eigentum ist als eine Folge von Specker bekannt, wie der erste Aufbau wegen E. Speckers (1949) ist. Trotz der Existenz von Gegenbeispielen wie diese können Teile der Rechnung und echten Analyse im Feld von berechenbaren Zahlen entwickelt werden, zur Studie der berechenbaren Analyse führend.

Die Ordnungsbeziehung auf den berechenbaren Zahlen ist nicht berechenbar. Es gibt keine Maschine von Turing der auf dem Eingang (die Beschreibung einer Maschine von Turing, die der Zahl näher kommt) Produktionen "JA" wenn und "NEIN" wenn. Der Grund: Nehmen Sie an, dass die durch A beschriebene Maschine outputting 0 als Annäherungen behält. Es ist nicht klar, wie lange man vor dem Entscheiden wartet, dass die Maschine nie Produktion eine Annäherung wird, die zwingt, positiv zu sein. So wird die Maschine schließlich glauben müssen, dass die Zahl 0 gleich sein wird, um eine Produktion zu erzeugen; die Folge kann später verschieden von 0 werden. Diese Idee kann verwendet werden, um zu zeigen, dass die Maschine auf einigen Folgen falsch ist, wenn es eine Gesamtfunktion schätzt. Ein ähnliches Problem kommt vor, wenn die berechenbaren reals vertreten werden, als Dedekind schneidet. Dasselbe hält für die Gleichheitsbeziehung: Der Gleichheitstest ist nicht berechenbar.

Während die volle Ordnungsbeziehung nicht berechenbar ist, ist die Beschränkung davon Paaren von ungleichen Zahlen berechenbar. D. h. es gibt ein Programm, das einen Eingang zwei Maschinen von Turing A und B näher kommende Zahlen a und b, wo ab und Produktionen ob a nimmt

Jede berechenbare Zahl, ist aber nicht umgekehrt definierbar. Es gibt viele definierbare, nichtberechenbare reelle Zahlen, einschließlich:

• Die binäre Darstellung des Stockenden Problems (oder jeder andere unberechenbare Satz von natürlichen Zahlen).
• Die Konstante von Chaitin, der ein Typ der reellen Zahl ist, die zum Stockenden Problem gleichwertiger Turing ist.

Eine reelle Zahl ist berechenbar, wenn, und nur wenn der Satz von natürlichen Zahlen sie vertritt (wenn geschrieben, in der Dualzahl und angesehen als eine charakteristische Funktion) berechenbar ist.

Jede berechenbare Zahl ist arithmetisch.

Der Satz von berechenbaren reellen Zahlen (sowie jede zählbare, dicht bestellte Teilmenge von reals ohne Enden) ist zum Satz von rationalen Zahlen mit der Ordnung isomorph.

Ziffer-Schnuren und die Räume von Cantor und Baire

Das ursprüngliche Papier von Turing hat berechenbare Zahlen wie folgt definiert:

Reelle

:A-Zahl ist berechenbar, wenn seine Ziffer-Folge durch einen Algorithmus oder Maschine von Turing erzeugt werden kann. Der Algorithmus nimmt eine ganze Zahl als Eingang und erzeugt die-th Ziffer der dezimalen Vergrößerung der reellen Zahl als Produktion.

(Bemerken Sie, dass sich die dezimale Vergrößerung eines einzigen auf die Ziffern im Anschluss an den dezimalen Punkt bezieht.)

Turing war bewusst, dass diese Definition zu - Annäherungsdefinition gleichwertig ist, die oben gegeben ist. Das Argument geht wie folgt weiter: Wenn eine Zahl im Sinn von Turing berechenbar ist, dann ist es auch im Sinn berechenbar: wenn, dann die ersten n Ziffern der dezimalen Vergrößerung für ein Versorgen einer Annäherung von a. Für das gegenteilige picken wir eine berechenbare reelle Zahl a auf und erzeugen zunehmend precisce Annäherungen bis zur n-ten Ziffer, nachdem der dezimale Punkt sicher ist. Das erzeugt immer eine dezimale a gleiche Vergrößerung, aber er kann in einer unendlichen Folge 9's unpassend enden, in welchem Fall er einen begrenzten (und so berechenbar) richtige dezimale Vergrößerung haben muss.

Wenn bestimmte topologische Eigenschaften der reellen Zahlen nicht wichtig sind, ist es häufig günstiger, sich mit Elementen (geschätzte 0,1 Gesamtfunktionen) statt reals Zahlen darin zu befassen. Die Mitglieder dessen können mit binären dezimalen Vergrößerungen, aber seit den dezimalen Vergrößerungen erkannt werden und dieselbe reelle Zahl anzeigen der inteveral kann nur bijektiv (und homeomorphically unter der Teilmenge-Topologie) identifiziert mit der Teilmenge des nicht Endes insgesamt 1's sein.

Bemerken Sie, dass dieses Eigentum von dezimalen Vergrößerungen bedeutet, dass es unmöglich ist, berechenbare reelle Zahlen effektiv zu identifizieren, die in Bezug auf eine dezimale Vergrößerung und diejenigen definiert sind, die im Annäherungssinn definiert sind. Hirst hat gezeigt, dass es keinen Algorithmus gibt, der als Eingang die Beschreibung einer Maschine von Turing nimmt, die Annäherungen für die berechenbare Zahl a erzeugt, und als Produktion eine Maschine von Turing erzeugt, die die Ziffern im Sinne der Definition von Turing aufzählt (sieh Hirst 2007). Ähnlich bedeutet es, dass die arithmetischen Operationen auf dem berechenbaren reals auf ihren Dezimaldarstellungen als nicht wirksam sind, wenn sie Dezimalzahlen hinzufügen, um eine Ziffer zu erzeugen, die es notwendig sein kann, willkürlich weit zum Recht auszusehen, zu bestimmen, ob es ein Tragen zur aktuellen Position gibt. Dieser Mangel an der Gleichförmigkeit ist ein Grund, dass die zeitgenössische Definition von berechenbaren Zahlen Annäherungen aber nicht dezimale Vergrößerungen verwendet.

Jedoch, von einem rechenbetonten oder messen theoretische Perspektive die zwei Strukturen und sind im Wesentlichen identisch. und Berechenbarkeitstheoretiker beziehen sich häufig auf Mitglieder als reals. Während für Fragen über Klassen oder Zufälligkeit völlig getrennt wird, ist es viel weniger unordentlich, um darin zu arbeiten.

Elemente dessen werden manchmal reals ebenso genannt, und obwohl, ein homeomorphic Image zusätzlich dazu enthaltend, völlig getrennt zu werden, nicht sogar lokal kompakt ist. Das führt zu echten Unterschieden in den rechenbetonten Eigenschaften. Zum Beispiel muss die Zufriedenheit mit dem freien quatifier berechenbar sein, während die einzigartige Zufriedenheit einer universalen Formel in der hyperarithmetischen Hierarchie willkürlich hoch sein kann.

Können berechenbare Zahlen statt des reals verwendet werden?

Die berechenbaren Zahlen schließen viele der spezifischen reellen Zahlen ein, die in der Praxis, einschließlich aller algebraischen Zahlen, sowie e, und vieler anderer transzendenter Zahlen erscheinen. Obwohl die berechenbaren reals jene reals erschöpfen, die wir berechnen oder näher kommen können, führt die Annahme, dass alle reals berechenbar sind, zu wesentlich verschiedenen Beschlüssen über die reellen Zahlen. Die Frage entsteht natürlich dessen, ob es möglich ist, über den vollen Satz von reals zu verfügen und berechenbare Zahlen für die ganze Mathematik zu verwenden. Diese Idee appelliert aus einem constructivist Gesichtspunkt, und ist dadurch verfolgt worden, was Bishop und Richman die russische Schule der konstruktiven Mathematik nennen.

Um wirklich Analyse über berechenbare Zahlen zu entwickeln, muss etwas Sorge genommen werden. Zum Beispiel, wenn man die klassische Definition einer Folge verwendet, wird der Satz von berechenbaren Zahlen unter der grundlegenden Operation nicht geschlossen, das Supremum einer begrenzten Folge zu nehmen (zum Beispiel, denken Sie eine Folge von Specker). Diese Schwierigkeit wird durch das Betrachten von nur Folgen gerichtet, die ein berechenbares Modul der Konvergenz haben. Die resultierende mathematische Theorie wird berechenbare Analyse genannt.

Durchführung

Es gibt einige Computerpakete, die mit berechenbaren reellen Zahlen, arbeiten

das Darstellen der reellen Zahlen als Programme Rechenannäherungen.

Ein Beispiel ist das Paket von RealLib (reallib Hausseite).

Siehe auch

• Definierbare Zahl
• Halbberechenbare Funktion
• Problem von Transcomputational
• Oliver Aberth 1968, Analyse im Berechenbaren Numerischen Feld, der Zeitschrift der Vereinigung, um Maschinerie (JACM), vol 15, iss 2, Seiten 276-299 Zu schätzen. Dieses Papier beschreibt die Entwicklung der Rechnung über das berechenbare numerische Feld.
• Errett Bishop und Douglas Bridges, Konstruktive Analyse, Springer, 1985, internationale Standardbuchnummer 0387150668
• Douglas Bridges und Fred Richman. Varianten der Konstruktiven Mathematik, Oxfords, 1987.
• Jeffry L. Hirst, Darstellungen von reals in der Rückmathematik, Meldung der polnischen Akademie von Wissenschaften, Mathematik, 55, (2007) 303-316.
• Marvin Minsky 1967, Berechnung: Begrenzte und Unendliche Maschinen, Prentice-Hall, Inc. Englewood Klippen, New Jersey. Keine Bibliothek der internationalen Standardbuchnummer der Kongress-Kartei Nr. 67-12342. Sein Kapitel §9 "Die Berechenbaren Reellen Zahlen" breitet sich zu den Themen dieses Artikels aus.

• E. Specker, "Nicht konstruktiv beweisbare Sätze der Analysis" J. Symbol. Logik, 14 (1949) Seiten 145-158

• (und). Berechenbare Zahlen (und Turing Maschinen) wurden in dieser Zeitung eingeführt; die Definition von berechenbaren Zahlen verwendet unendliche dezimale Folgen.
• Klaus Weihrauch 2000, Berechenbare Analyse, Texte in der theoretischen Informatik, dem Springer, der internationalen Standardbuchnummer 3540668179. §1.3.2 führt die Definition durch verschachtelte Folgen von Zwischenräumen ein, die zum echten Singleton zusammenlaufen. Andere Darstellungen werden in §4.1 besprochen.
• Klaus Weihrauch, Eine einfache Einführung in die berechenbare Analyse

Berechenbare Zahlen wurden unabhängig von Turing, Posten und Kirche definiert. Sieh Das Unentscheidbare, die Hrsg. Martin Davis für weitere ursprüngliche Papiere.