Entscheidbare Eigenschaften berechenbarer Realwerte

Ja, Rices Theorem für Reals gilt für jede vernünftige Version berechenbarer Reals.

Ich werde zunächst einen bestimmten Satz und eine Folgerung beweisen und später erklären, was dies mit der Berechenbarkeit zu tun hat.

Satz: Angenommen, ist eine Abbildung und zwei Real, so dass und . Dann existiert eine Cauchy-Sequenz so dass für alle $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$ $(x_i)_i$ $p(\lim_i x_i) \neq p(x_j)$ . $j \in \mathbb{N}$

Beweis. Wir konstruieren eine Folge von Realpaaren wie folgt: $(y_i, z_i)_i$

\begin{aligned} (y_{0}, z_{0}) & = (ein, b) \\ (y_{ich + 1}, z_{ich + 1}) & = {\begin{cases} (y_{ich}, (y_{ich} + z_{ich}) /. 2) & wenn p ((y_{ich} + z_{ich}) /. 2) = 1 \\ ((y_{ich} + z_{ich}) /. 2, z_{ich}) & wenn p ((y_{ich} + z_{ich}) /. 2) = 0 \end{cases} \end{aligned}

$\begin{align*} (y_0, z_0) &= (a, b) \\ (y_{i+1}, z_{i+1}) &= \begin{cases} (y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\ ((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\ \end{cases} \end{align*}$ Beachten Sie, dass für alle

i \in N

$i \in \mathbb{N}$

und $p(y_i) = 0$ $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Somit sind die Sequenzen und Cauchy und sie konvergieren zu einem gemeinsamen Punkt . Wenn ist, nehmen wir , und wenn ist, nehmen wir $(y_i)_i$ $(z_i)_i$ $c = \lim_i y_i = \lim_i z_i$ $p(c) = 0$ $(x_i)_i = (z_i)_i$ $p(c) = 1$ . $(x_i)_i = (y_i)_i$ $\square$

Folgerung: Angenommen, und zwei reelle Zahlen, so dass und $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$ . Dann läuft jede Turing-Maschine entweder für immer oder nicht für immer.

Beweis. Nach dem Theorem gibt es eine Cauchy-Folge so dass für alle . Ohne Verlust der Allgemeinheit können wir annehmen, dass und . $(x_i)_i$ $p(x_j) \neq p(\lim_i x_i)$ $j \in \mathbb{B}$ $p(x_j) = 1$ $p(\lim_i x_i) = 0$

Sei eine Turingmaschine. Definieren Sie eine Sequenz durch Die Sequenz ist gut definiert, da wir bis zu Schritten simulieren und entscheiden können, ob es hat innerhalb so vieler Schritte aufgehört oder nicht. Als nächstes beobachte, dass eine Cauchy-Sequenz ist, weil $T$ $y_i$

y_{ich} = {\begin{cases} x_{j} & wenn T. hält im Schritt an j und j \leq ich \\ x_{ich} & wenn T. hört nicht in sich auf ich Schritte \end{cases}

$y_i = \begin{cases} x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\ x_i & \text{if $T$ does not halt within $i$ steps} \end{cases}$

T

$T$

i

$i$

(y_{i})_{i}

$(y_i)_i$

(x_{i})_{i}

$(x_i)_i$ bin eine Cauchy-Sequenz (wir lassen dies als Übung). Sei

. Entweder

oder

z = lim_{i} y_{i}

$z = \lim_i y_i$

p (z) = 0

$p(z) = 0$

p (z) = 1

$p(z) = 1$

wenn ist, läuft für immer. In der Tat, wenn es nach Schritten , dann hätten wir , und so würde widersprechen . $p(z) = 0$ $T$ $j$ $z = x_j$ $p(z) = p(x_j) = 1$ $p(z) = 0$
Wenn ist, läuft nicht für immer. Wenn dies der Fall wäre, hätten wir in der Tat und somit , was widerspricht . $p(z) = 1$ $T$ $z = \lim_i x_i$ $p(z) = p(\lim_i x_i) = 0$ $p(z) = 0$ $\square$

Jetzt können wir erklären, warum dies uns den Satz von Rice für reelle Zahlen gibt. Die Beweise sind konstruktiv und liefern daher berechenbare Verfahren. Dies gilt für jedes Modell der Berechenbarkeit und jede Rechenstruktur von Realwerten, die es verdienen, so genannt zu werden. Tatsächlich können Sie zurückgehen und den Proof als Anweisungen zum Erstellen eines Programms lesen - alle Schritte sind berechenbar.

Wenn wir also eine berechenbare Abbildung und berechenbare so dass und , dann könnten wir die berechenbaren Prozeduren anwenden, die sich aus dem ergeben konstruktive Beweise des Satzes und der Folgerung zur Schaffung des Halting-Orakels. Das Halting-Orakel existiert jedoch nicht für jede berechenbare Karte $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(1) = 1$ $p : \mathbb{R} \to \{0,1\}$ ist konstant.

Ergänzend: Es gab auch eine Frage, ob der Satz von Rice mit der Verbundenheit der Realitäten zusammenhängt. Ja, es ist im Wesentlichen die Aussage, dass die Reals miteinander verbunden sind.

Lassen Sie uns zunächst beobachten, dass eine kontinuierliche Abbildung (wir nehmen die diskrete Topologie auf ) einem Paar disjunkter Clopen- (geschlossen und offen) Mengen so dass . Nehmen Sie in der Tat und $p : X \to \{0,1\}$ $\{0,1\}$ $U, V \subseteq X$ $U \cup V = X$ $U = p^{-1}(\{0\})$ . Da stetig ist und und offen sind, sind und offen, disjunkt und decken offensichtlich ganz . Umgekehrt bestimmt jedes Paar disjunkter Clopens, die bedecken, eine kontinuierliche Abbildung , die Elemente von auf und Elemente von auf abbildet. $V = p^{-1}(\{1\})$ $p$ $\{0\}$ $\{1\}$ $U$ $V$ $X$ $(U,V)$ $X$ $p : X \to \{0,1\}$ $U$ $0$ $V$ $1$

Daraus lernen wir, dass ein Raum genau dann getrennt wird, wenn eine stetige Abbildung und so dass und (wir brauchen und damit wir eine nicht triviale Zerlegung von ). Es gibt eine andere Möglichkeit, dasselbe zu sagen: Ein Raum ist genau dann verbunden, wenn alle fortlaufenden Karten vorhanden sind $X$ $p : X \to \{0,1\}$ $a, b \in X$ $p(a) = 0$ $p(1) = b$ $a$ $b$ $X$ $X$ sind konstant. $X \to \{0,1\}$

In der berechenbaren Mathematik haben wir einen Grundsatz: Jede berechenbare Karte ist stetig . Solange wir uns also im Bereich berechenbarer Objekte befinden, besagt der Satz von Rice tatsächlich, dass ein bestimmter Raum verbunden ist. Im Fall des Satzes klassischen Rices der Raum in Frage ist der Raum des Teil berechenbarer Funktionen . $\mathbb{N} \to \mathbb{N}$

Andrej Bauer
quelle

Vielen Dank! Das habe ich gesucht. Irgendeine Idee zu der anderen Frage - ob dies in direktem Zusammenhang mit der Verbundenheit der Realitäten steht?

Shachaf

Ich habe eine Erklärung hinzugefügt, dass der Satz von Rice tatsächlich eine Form des Satzes der Verbundenheit ist.

Andrej Bauer

Angenommen,

und definieren Sie

wenn

nicht innerhalb von

Schritten anhält, und

ansonsten. Wenn T nicht anhält, konvergiert

gegen

, andernfalls konvergiert es gegen

. Wenn

berechenbar sind, kann man bei gegebener

eine Maschine erzeugen, die die Grenze von berechnet

p (x) = 1, p (x^{'}) = 0

$p(x)=1, p(x')=0$

y_{i} = x

$y_i=x$

T

$T$

i

$i$

y_{i} = x^{'}

$y_i=x'$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

x, x^{'}

$x,x'$

T

$T$

. Warum ist das nicht genugum zu zeigendass

nicht berechenbar sein, oder sogar semidecidable (wie

halt nicht genau dannwenn

ist

am Limit). Offensichtlich fehlt mir etwas, da es nicht triviale Eigenschaften gibt, die halbentscheidbar sind.

y_{i}

$y_i$

p

$p$

T

$T$

p

$p$

1

$1$

Ariel

Ihre Definition von

ist in Ordnung , aber Sie benötigen auch eine berechenbare Konvergenzrate der Sequenz

um zu behaupten, dass ihre Grenze berechenbar ist. Da wir nicht berechnen können, bei welchem Index

die Sequenz

von

nach

springen könnte (oder wir könnten berechnen, bei welchem Schritt

anhalten wird), kann eine solche berechenbare Konvergenzrate nicht gehabt werden.

T

$T$

y_{i}

$y_i$

i

$i$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

T

$T$

Andrej Bauer

Nein. Oder zumindest ist der Beweis nicht trivial, da Sie unter den (im Allgemeinen vielen) möglichen Methoden zur Berechnung eines Real wählen können und möglicherweise einen mit einer Struktur auswählen können, die für die ausgewählte Eigenschaft insgesamt ist Sie reduzieren das Testen der Eigenschaft nicht auf das Problem des Anhaltens.

Ich denke auch, ich brauche ein besseres Verständnis dafür, was "nicht trivial" für die Eigenschaften von Zahlen bedeutet. Für den Satz von Rice ist "nichttrivial" grundsätzlich nicht syntaktisch und nicht durch die Syntax impliziert. Jede berechenbare reelle Zahl ist jedoch kein einzelnes Programm, sondern eine Äquivalenzklasse voller Programme.

Boyd Stephen Smith Jr.
quelle

Ich bin mir nicht sicher, was du hier meinst. Versuchen Sie , zwischen berechenbaren reellen Zahlen (zB zu unterscheiden

, etc.) und die Programme, die sie berechnen? Sicher, es gibt unendlich viele Programme, die jeden berechenbaren Real berechnen, aber es gibt auch unendlich viele Turing-Maschinen, die über eine entscheidbare Sprache entscheiden, und der gewöhnliche Satz von Rice hat damit kein Problem.

2

$2$

22 / 7

$22/7$

π

$\pi$

David Richerby

Haben unterschiedliche Darstellungen von berechenbaren Realwerten tatsächlich signifikant unterschiedliche Berechenbarkeitseigenschaften? Angenommen, ich verwende eine der Definitionen unter en.wikipedia.org/wiki/Computable_number , z. B. wird ein berechenbarer Real durch ein Programm dargestellt, das eine rationale Fehlergrenze annimmt und eine Annäherung innerhalb dieser Grenze erzeugt. Ich meine "trivial" im gleichen Sinne wie der Satz von Rice: Eine Eigenschaft, die für alle berechenbaren Realitäten oder für keine von ihnen gilt. Es ist wahr, dass jede Zahl durch mehrere Programme dargestellt werden kann, aber das gilt auch für Teilfunktionen.

Shachaf

@ Shachaf Das ist "trivialer" als es der Satz von Rice erfordert. "Syntaktische" Eigenschaften sind ebenfalls trivial - z. B. "hat mindestens 4 vom Anfangszustand erreichbare Zustände", "hat einen verbundenen Zustandsgraphen", "hat keinen Übergang, der X auf das Band schreibt" usw. - und sie benötigen Nein, gilt für jede Maschine.

Boyd Stephen Smith Jr.

@ DavidRicherby Ja, ich denke die Unterscheidung ist notwendig. Wenn Sie ausschließlich mit vollständigen oder produktiven Darstellungen arbeiten können, haben Sie mehr Macht.

Boyd Stephen Smith Jr.

Der Satz von Rice befasst sich mit Eigenschaften von Teilfunktionen, nicht mit Algorithmen, die diese berechnen. Ebenso frage ich nach Eigenschaften berechenbarer Reals, nicht nach Programmen, die sie berechnen.

Shachaf

Entscheidbare Eigenschaften berechenbarer Realwerte

Antworten: