Ist es möglich zu testen, ob eine berechenbare Zahl rational oder ganzzahlig ist?

18

Ist es möglich, algorithmisch zu testen, ob eine berechenbare Zahl rational oder ganzzahlig ist? Mit anderen Worten, könnte eine Bibliothek, die berechenbare Zahlen implementiert, die Funktionen bereitstellen, isIntegeroder isRational?

Ich vermute, dass es nicht möglich ist und dass dies irgendwie damit zusammenhängt, dass es nicht möglich ist, zu testen, ob zwei Zahlen gleich sind, aber ich sehe nicht, wie ich es beweisen kann.

Edit: Eine berechenbare Zahl x wird durch eine Funktion fx(ϵ) , die eine rationale Approximation von x mit der Genauigkeit ϵ : |xfx(ϵ)|ϵ , für jedes ϵ>0 . Bei einer solchen Funktion ist es möglich , zu testen , ob xQ oder xZ ?

dbarbosa
quelle
3
Wie wird die berechenbare Nummer angegeben?
Tsuyoshi Ito
10
Wie die Nummer angegeben wird, ist natürlich relevant. Wenn die Eingabe ein Flag enthält, ob es sich bei der Zahl um eine Ganzzahl handelt oder nicht, ist die Entscheidung, ob es sich bei der Eingabe um eine Ganzzahl handelt oder nicht, trivial.
Tsuyoshi Ito
3
Ähnliche Frage: cstheory.stackexchange.com/questions/10495/…
Kristoffer Arnsfelt Hansen
3
(1) „Woher weißt du, dass dies eine Ganzzahl ist?“ Warum sollte es mich interessieren? Sie haben nichts über die Anforderungen an den Betrieb gesagt. (2) „Wenn Sie die beiden Antworten bis jetzt sehen, erwähnen sie nichts über die Implementierung.“ Ich weiß nicht, was Sie hier unter „Implementierung“ verstehen oder warum dieser Satz für meine Kommentare relevant ist.
Tsuyoshi Ito
16
Ich hoffe meine Antwort beflügelt diese Diskussion. Tsuyoshi, Sie irren sich, es ist wichtig, welche Operationen berechenbar sind. Wir implementieren keine reellen Zahlen im luftleeren Raum, sondern manipulieren sie . Nach Ihrer Meinung könnten wir einfach den Einheitentyp verwenden, um alles zu implementieren. Ja, wir könnten, aber dann wären einige Operationen nicht berechenbar, und genau das ist das Kriterium, nach dem wir Repräsentationen beurteilen.
Andrej Bauer

Antworten:

32

Es ist leicht zu verwechseln, was es bedeutet, eine reelle Zahl "darzustellen" oder "umzusetzen". In der Tat erleben wir eine Diskussion in den Kommentaren, in denen die Darstellung umstritten ist. Also lassen Sie mich zuerst darauf eingehen.

Woher wissen wir, dass eine Implementierung korrekt ist?

Die Theorie, die erklärt, wie man Dinge in einem Computer darstellt, ist Realisierbarkeit . Die Grundidee ist, dass wir für eine Menge einen Datentyp τ und für jedes x X eine Menge von Werten vom Typ τ auswählen, die dies realisieren . Wir schreiben v x X, wenn v ein Wert ist, der x realisiert . Zum Beispiel (ich werde Haskell ohne guten Grund verwenden), könnte eine sinnvolle Implementierung von N der Datentyp sein, bei dem v k N ist, wenn vXτxXτvxXvxNIntegervkNvErgibt die Ziffer (also insbesondere nicht eine natürliche Zahl darstellen, und auch nicht ein divergierendes Programm). Aber einige Joker konnten zu Fuß durch und legen nahe , dass wir verwenden natürliche Zahlen mit vertreten zu T r u e42 N und F ein l s en N für n 42 . Warum ist das falsch? Wir brauchen ein Kriterium .k¯-42BoolTrue42NFalsenNn42

Im Fall von "Joker-Nummern" besteht die einfache Beobachtung darin, dass die Addition nicht implementiert werden kann. Angenommen, ich sage Ihnen, ich habe zwei Zahlen, die beide durch . Können Sie einen Realisator für ihre Summe geben? Nun, das hängt davon ab, ob die Summe 42 ist, aber Sie können es nicht sagen. Da die Addition ein "wesentlicher Bestandteil der natürlichen Zahlen" ist, ist dies nicht akzeptabel. Mit anderen Worten, bei der Implementierung geht es nicht um Mengen, sondern um Strukturen , dh wir müssen Mengen so darstellen, dass es möglich ist, auch die relevante Struktur zu implementieren. Lassen Sie mich das betonen:False

Wir implementieren Strukturen, keine bloßen Mengen. Daher müssen wir in der Lage sein, die gesamte Struktur zusammen mit Operationen und allen Axiomen zu implementieren, damit die Implementierung korrekt ist.

Wenn Sie sich nicht an diesen Grundsatz halten, müssen Sie ein alternatives mathematisches Kriterium für die Richtigkeit vorschlagen . Ich kenne keinen.

Beispiel: Darstellung natürlicher Zahlen

Für natürliche Zahlen wird die relevante Struktur durch Peano-Axiome beschrieben, und das entscheidende Axiom, das implementiert werden muss, ist Induktion (aber auch , Nachfolger, + und × ). Wir können anhand der Realisierbarkeit berechnen, was die Implementierung der Induktion bewirkt. Es stellt sich heraus, dass es sich um eine Karte handelt (wobei es sich um den noch unbekannten Datentyp handelt, der natürliche Zahlen darstellt)0+×nat

induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

befriedigend induction x f zero = xund induction x f (succ n) = f n (induction x f n). All dies kommt aus der Realisierbarkeit. Wir haben ein Kriterium: Eine Implementierung von natürlichen Zahlen ist korrekt, wenn sie eine Implementierung von Peano-Axiomen erlaubt. Ein ähnliches Ergebnis würde erhalten, wenn wir die Charakterisierung von Zahlen als Anfangsalgebra für den Funktor .X1+X

Richtige Implementierung von reellen Zahlen

Lasst uns die Aufmerksamkeit auf die reellen Zahlen und die vorliegende Frage lenken. Die erste Frage lautet: "Wie ist die relevante Struktur der reellen Zahlen?" Die Antwort lautet: Archimedischer Cauchy füllt das bestellte Feld aus . Dies ist die gängige Bedeutung von "reellen Zahlen". Sie können es nicht ändern, es wurde von anderen für Sie repariert (in unserem Fall erweisen sich die alternativen Dedekind-Reals als isomorph zu den Cauchy-Reals, die wir hier betrachten.). Sie können keinen Teil davon wegnehmen. Sie dürfen nicht sagen: "Es ist mir egal, ob Sie Additionen implementieren" oder "Die Reihenfolge ist mir egal". Wenn Sie das tun, dürfen Sie es nicht als "reelle Zahlen" bezeichnen, sondern als "reelle Zahlen, bei denen wir die lineare Reihenfolge vergessen".

Ich werde nicht auf alle Details eingehen, sondern nur erläutern, wie die verschiedenen Teile der Struktur verschiedene Operationen für Real ergeben:

  • Im archimedischen Axiom geht es darum, rationale Approximationen von Realwerten zu berechnen
  • Die Feldstruktur liefert die üblichen arithmetischen Operationen
  • Die lineare Reihenfolge gibt uns ein halbentscheidbares Verfahren zum Testen von x<y
  • lim : (nat -> real) -> real(xn)n m , n|xnxm|2min(n,m)m,n

Was wir nicht bekommen, ist eine Testfunktion für Gleichheit. Es gibt nichts in den Axiomen für Reals , die das fragt sein entscheidbar. (Im Gegensatz dazu implizieren die Peano-Axiome, dass die natürlichen Zahlen bestimmbar sind, und Sie können dies beweisen, indem Sie sie nur als unterhaltsame Übung implementieren .)=eq : nat -> nat -> Boolinduction

Es ist eine Tatsache, dass die übliche Dezimaldarstellung von Realwerten, die die Menschheit verwendet, schlecht ist, weil wir damit nicht einmal Addition implementieren können. Fließkomma mit unendlicher Mantisse versagt ebenfalls (Übung: Warum?). Was jedoch funktioniert, ist eine vorzeichenbehaftete Zifferndarstellung, dh eine, bei der sowohl negative als auch positive Ziffern zulässig sind. Oder wir könnten Rationalisierungssequenzen verwenden, die den oben genannten Cauchy-Schnelltest erfüllen.

Die Tsuyoshi-Darstellung implementiert auch etwas, aber nichtR

Betrachten wir die folgende Darstellung von Real: Ein Real wird durch ein Paar wobei eine schnelle Cauchy-Folge ist, die zu konvergiert, und ein Boolescher ist, der angibt, ob eine ganze Zahl ist. Damit dies eine Repräsentation der Realwerte ist, müssten wir eine Addition implementieren, aber wie sich herausstellt, können wir die Booleschen Flags nicht berechnen. Das ist also keine Repräsentation der Realitäten. Aber es repräsentiert immer noch etwas, nämlich die Teilmenge des Reals( q , b ) ( q n ) n x b x Z( RZ ) Z( RZ ) Rx(q,b)(qn)nxbxZ(RZ). In der Tat, nach der Realisierbarkeit Auslegung wird eine Vereinigung mit einem Flag implementiert angibt , welcher Teil der Union sind wir in. Im Übrigen ist ein nicht gleich zu , es sei denn , Sie in ausgeschlossenen glauben, die nicht umgesetzt werden können , und ist daher durchaus für diese Diskussion nicht relevant. Wir werden von Computern gezwungen , Dinge intuitiv zu tun.Z(RZ)R

Wir können nicht testen, ob ein Real eine ganze Zahl ist

Lassen Sie mich zum Schluss die gestellte Frage beantworten. Wir wissen jetzt, dass eine akzeptable Repräsentation der Realitäten eine durch schnelle Cauchy-Sequenzen von Rationals ist. (Ein wichtiger Satz besagt, dass zwei beliebige Darstellungen von Real, die akzeptabel sind, tatsächlich rechnerisch isomorph sind.)

Satz: Das Testen, ob ein Real eine ganze Zahl ist, ist nicht entscheidbar.

Beweis. Angenommen, wir könnten testen, ob ein Real eine ganze Zahl ist (natürlich wird der Real durch eine schnelle Cauchy-Sequenz realisiert). Die Idee, mit der Sie einen viel allgemeineren Satz beweisen können, besteht darin, eine schnelle Cauchy-Folge von Nicht-Ganzzahlen zu konstruieren, die zu einer ganzen Zahl konvergiert. Das ist einfach, nimm einfach . Lösen Sie als Nächstes das Halteproblem wie folgt. Definieren Sie bei gegebener Turing-Maschine eine neue Folge durch Das heißt, die neue Sequenz sieht aus wie die Sequenz , solangex n = 2 - n T ( y n ) n y n = { x n, wenn  T  nicht innerhalb von n  Schritten gestoppt hat  x m, wenn  T  in Schritt m gestoppt hat   und  m n ( x n ) n T x m T m T z = lim n y n z 0(xn)nxn=2nT(yn)n

yn={xnif T has not stopped within n stepsxmif T stopped in step m and mn
(xn)nTläuft, aber dann bleibt es bei " wenn in Schritt anhält . Sehr wichtig ist, dass die neue Sequenz auch eine schnelle Cauchy-Sequenz ist (und wir können dies beweisen, ohne zu wissen, ob anhält). Daher können wir seine Grenze berechnen , da unsere Darstellung von korrekt ist. Testen Sie, ob eine Ganzzahl ist. Wenn dies der Fall ist, muss es und dies geschieht nur, wenn für immer ausgeführt wird. Andernfalls ist keine ganze Zahl, daher muss aufgehört haben. QED.xmTmTz=limnynz0z TTzT

Aufgabe: Passen Sie den obigen Beweis an, um zu zeigen, dass wir nicht auf rationale Zahlen testen können. Passen Sie es dann an, um zu zeigen, dass wir nichts Nicht-Triviales testen können (dies ist etwas schwieriger).

Manchmal sind die Leute verwirrt über all dieses Testgeschäft. Sie denken, wir haben bewiesen, dass wir niemals testen können, ob ein Real eine ganze Zahl ist. Aber sicher ist 42 ein Real und wir können erkennen, ob es eine ganze Zahl ist. Tatsächlich können wir mit jedem bestimmten Real, das wir uns einfallen lassen, , , usw., sehr gut sagen, ob es sich um ganze Zahlen handelt. Wir können genau sagen, weil wir zusätzliche Informationen haben: Diese Reals werden uns nicht als Sequenzen gegeben, sondern als symbolische Ausdrücke, aus denen wir das Tsuyoshi-Bit berechnen können. Sobald die einzige Information, die wir über das Reale haben, eine Folge rationaler Annäherungen ist, die sich diesem annähern (und ich auch)88 ln 89 e π sin1188ln89 nneπ163bedeutet nicht einen symbolischen Ausdruck, der die Sequenz beschreibt, sondern eine Blackbox, die den ten Term bei Eingabe von ) ausgibt, dann sind wir genauso hilflos wie Maschinen.nn

Die Moral der Geschichte

Es macht keinen Sinn, über die Implementierung eines Sets zu sprechen, wenn wir nicht wissen, welche Art von Operationen wir darauf ausführen möchten.

Andrej Bauer
quelle
16
Wenn meine Antworten Ehefrauen wären, könnte ich nur einmal antworten. Oder ich müsste zumindest die vorherige Antwort löschen, bevor ich die nächste schreibe.
Andrej Bauer
5
@Max: Die ersten Sätze dieser Art stammen von Kreisel, Lacombe und Shoenfield (siehe KLS-Satz). Unabhängig davon gab Tsteitin einen Satz an, der KLS verallgemeinerte und explizit die Form "Jede berechenbare Karte ist berechenbar stetig" hatte.
Andrej Bauer
6
Ich muss ein Lehrbuch schreiben - (Google google google). Okay, gut, du hast eine Amtszeit. Tue es!
Jeffs
10
@ Tsuyoshi: Die Frage verwendete die etablierte Phrase "reelle Zahl" ohne Qualifikation. Die Struktur von reellen Zahlen ist Standard. Es steht Ihnen frei, andere Strukturen in Betracht zu ziehen, es steht Ihnen jedoch nicht frei, die Standardterminologie falsch zu interpretieren.
Andrej Bauer
21
Technisch gesehen haben Sie recht, das Wort "real" wurde nicht verwendet. Aber Sie täuschen sich über die Definition von reellen Zahlen. Oder ich würde es so ausdrücken: Es ist eine schlechte Mathematik zu denken, dass die Realzahlen eine bestimmte Menge sind, die zuerst kommt, gefolgt von einer gewissen Struktur. Genau wie wir Gruppen, Ringe, topologische Räume usw. in Bezug auf ihre Struktur definieren, sollten wir spezielle Objekte in Bezug auf ihre universellen Eigenschaften definieren (natürliche Zahlen sind das anfängliche Semiring, ganze Zahlen der anfängliche Ring, rationelles Anfangsfeld, reelle Zahlen) das .....).
Andrej Bauer
10

Ich neige dazu, dies für unentscheidbar zu halten:

Sei eine berechenbare irrationale Zahl. Betrachten wir eine TM . Sie können eine Funktion , die auf , und parallel mit wachsender Genauigkeit berechnen . Wenn anhält, wird berechnet , andernfalls wird fortgefahren.M M x M xxMMϵxMx

Die Entscheidung, ob diese Funktion eine rationale Zahl berechnet, entspricht dem Halteproblem.

Shaull
quelle
Ich verstehe deine Antwort nicht. Könntest du bitte mehr ausarbeiten? Ich verstehe nicht, wie Sie es mit dem Problem des Anhaltens in Verbindung bringen, und was noch wichtiger ist, ich glaube, es gibt keinen Grund, warum jemals anhalten sollte (selbst wenn eine ganze Zahl ist). xMx
Dbarbosa
Wie Tsuyoshi betont hat, hängt die Antwort von der Darstellung und dem Rechenmodell ab. Ihre Antwort lautet richtig: Wenn die Eingaben als berechenbare reelle Zahlen angesehen werden, die von einem TM-Computer angegeben werden, ist die Gleichheit nicht bestimmbar. Dies ist richtig, kommt jedoch keinem in der Praxis verwendeten Modell nahe.
Kaveh
2
In der Tat bezieht sich meine Antwort auf Darstellungen, wie sie in der Frage veröffentlicht sind, ob sie nun praktisch sind oder nicht. @dbarbosa - Ich erkläre: Wenn Sie ein TM , folgen Sie der Konstruktion in der Antwort. Nehmen Sie dann im Widerspruch an, Sie können entscheiden, ob die ausgegebene Maschine eine vernünftige Maschine darstellt oder nicht. Wenn es ein Rational ist, bedeutet dies, dass irgendwann stehen bleibt und wir aufhören, die Zahl zu berechnen. Wenn es jedoch irrational ist, hört nicht auf. Somit wissen wir, ob anhält und das als unentscheidbar bekannte Problem des Anhaltens löst. M M MMMMM
Shaull
10

Angenommen, ein Real wird als Folge rationaler Approximationen angegeben, wobei der Fehler durch eine bekannte berechenbare Funktion begrenzt wird, die gegen Null tendiert (alle derartigen Approximationen sind äquivalent und entsprechen der üblichen Topologie des Real).

Berechenbare Funktionen sind fortlaufend. IsRational und IsInteger sind nicht kontinuierlich und daher nicht berechenbar.

IsInteger ist semi- computable: Es gibt eine Prozedur, die letztendlich "false" ausgibt, wenn die Eingabe keine Ganzzahl ist, aber für immer ausgeführt wird, wenn die Eingabe eine Ganzzahl ist. Diese Prozedur untersucht einfach jede Approximation und prüft, ob sich eine ganze Zahl innerhalb der Fehlergrenze befindet. Diese Funktion ist kontinuierlich, wenn die Sierpiński-Topologie für {true, false} verwendet wird (dh {false} ist eine offene Menge, {true} jedoch nicht).

Max
quelle
Danke für die Antwort. Ich verstehe das nicht stetig => nicht berechenbar, ich vermute, dass Sie einen (wahrscheinlich weithin bekannten) Satz verwendet haben, den ich nicht kenne oder an den ich mich nicht erinnere. Können Sie uns bitte nähere Informationen zu diesem Schritt geben?
Dbarbosa
1
"computable => continuous" scheint ein Volkstheorem zu sein - ich kann kein Originalzitat finden. Die Theorie der Berechnung von unendlichen Objekten und die Verbindungen zur Topologie werden in diesen Kursfolien von Brattka ( math.uni.wroc.pl/~pkowa/slides/brattka.pdf ) recht gut beschrieben (IMO ). Satz 2 in den Folien besagt, dass alle berechenbaren Funktionen in Sequenzen von Naturalien stetig sind; kombiniert mit Satz 12 erhält man das Ergebnis für Funktionen anderer Typen.
Max
6

Es ist nicht zu entscheiden, ob eine bestimmte berechenbare Zahl gleich Null ist .

(Ihr Orakel für rationale Näherung gibt also für jede versuchte Näherung 0 zurück. Vielleicht haben Sie es einfach nicht klein genug gegeben.)

Daher ist es nicht zu entscheiden, ob eine bestimmte berechenbare Zahl zwischen -½ und + ½ eine ganze Zahl ist.

Jeffε
quelle
2

Eine berechenbare Funktion ist stärker als die stetige Funktion, dh jede berechenbare Funktion muss in der Informationstopologie stetig sein.

F:R{Yes,No}

F(r)={YESrQNOo.w.

ist berechenbar.

rk2nr[k2n,k+12n]n

Dann ist Ihre Funktion nicht stetig und daher nicht berechenbar.

M0n[12n,12n]MMmM[12m,12m]MMNOYESM[12m,12m]MYESM

Der Beweis, dass eine berechenbare Funktion kontinuierlich sein muss, ist ähnlich.

Kaveh
quelle