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

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 $f_x(\epsilon)$ , die eine rationale Approximation von $x$ mit der Genauigkeit $\epsilon$ : $|x - f_x(\epsilon)| \leq \epsilon$ , für jedes $\epsilon > 0$ . Bei einer solchen Funktion ist es möglich , zu testen , ob $x \in \mathrm{Q}$ oder $x \in \mathrm{Z}$ ?

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 $X$$\tau$$x \in X$$\tau$$v \vdash x \in X$$v$$x$$\mathbb{N}$Integer$v \vdash k \in \mathbb{N}$$v$Ergibt 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 e ⊢ 42 ∈ N und F ein l s e ⊢ n ∈ N für n ≠ 42 . Warum ist das falsch? Wir brauchen ein Kriterium .$\overline{k}$-42Bool$\mathtt{True} \vdash 42 \in \mathbb{N}$$\mathtt{False} \vdash n \in \mathbb{N}$$n \neq 42$

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:$\mathtt{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$$+$$\times$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 .$X \mapsto 1 + 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$(x_n)_n$ m , $|x_n - x_m| \leq 2^{\min(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 nicht$\mathbb{R}$

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 ≤ ( R ≤ Z ) Z ≤ ( R ≤ Z ) $x$$(q,b)$$(q_n)_n$$x$$b$$x$$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$. 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.$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$$\mathbb{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 $(x_n)_n$$x_n = 2^{-n}$$T$$(y_n)_n$

$$y_n = \begin{cases} x_n & \text{if $T$ has not stopped within $n$ steps}\\ x_m & \text{if $T$ stopped in step $m$ and $m \leq n$} \end{cases}$$ $(x_n)_n$$T$lä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.$x_m$$T$$m$$T$$z = \lim_n y_n$$z$$0$z $T$$z$$T$

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 π $\sin 11$$88 \ln 89$ n$e^{\pi \sqrt{163}}$bedeutet 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.$n$$n$

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.

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 $x$$M$$M$$\epsilon$$x$$M$$x$

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

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).

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.

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

$F:\mathbb{R} \to \{Yes,No\}$

$$F(r) = \begin{cases} YES & r\in \mathbb{Q}\\ NO & o.w. \end{cases}$$

ist berechenbar.

$r$$\frac{k}{2^{n}}$$r \in [\frac{k}{2^n},\frac{k+1}{2^n}]$$n$

Dann ist Ihre Funktion nicht stetig und daher nicht berechenbar.

$M$$0$$n$$[-\frac{1}{2^n},\frac{1}{2^n}]$$M$$M$$m$$M$$[-\frac{1}{2^m},\frac{1}{2^m}]$$M$$M$$NO$$YES$$M$$[-\frac{1}{2^m},\frac{1}{2^m}]$$M$$YES$$M$

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