Entscheidbare Eigenschaften berechenbarer Realwerte

10

Ist "Rices Theorem für die berechenbaren Realitäten" - das heißt, keine nichttriviale Eigenschaft der Zahl, die durch einen bestimmten berechenbaren Realwert dargestellt wird, entscheidbar - wahr?

Entspricht dies in direkter Weise der Verbundenheit der Realitäten?

Shachaf
quelle

Antworten:

8

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 a , b R zwei Real, so dass p ( a ) = 0 und p ( b ) = 1 . Dann existiert eine Cauchy-Sequenz ( x i ) i, so dass p ( lim i x i ) p ( x j ) für alle j istp:R{0,1}a,bRp(a)=0p(b)=1(xi)ip(limixi)p(xj) .jN

Beweis. Wir konstruieren eine Folge von Realpaaren wie folgt: ( y 0 , z 0 )(yi,zi)i

(y0,z0)=(ein,b)(yich+1,zich+1)={(yich,(yich+zich)/.2)wenn p((yich+zich)/.2)=1((yich+zich)/.2,zich)wenn p((yich+zich)/.2)=0
Beachten Sie, dass für alle :ichN.
  • und p ( z i ) = 1p(yich)=0p(zich)=1
  • |zich- -yich|=|b- -ein|2- -ich
  • |yich+1- -yich||b- -ein|2- -ich
  • |zich+1- -zich||b- -ein|2- -ich

Somit sind die Sequenzen und ( z i ) i Cauchy und sie konvergieren zu einem gemeinsamen Punkt c = lim i y i = lim i z i . Wenn p ( c ) = 0 ist, nehmen wir ( x i ) i = ( z i ) i , und wenn p ( c ) = 1 ist, nehmen wir ( x)(yich)ich(zich)ichc=limichyich=limichzichp(c)=0(xich)ich=(zich)ichp(c)=1 . (xich)ich=(yich)ich

Folgerung: Angenommen, und a , b R zwei reelle Zahlen, so dass p ( a ) = 0 und p ( b ) = 1p::R.{0,1}}ein,bR.p(ein)=0p(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 p ( x j ) p ( lim i x i ) für alle j B gilt . Ohne Verlust der Allgemeinheit können wir annehmen, dass p ( x j ) = 1 und p ( lim i x i ) = 0 ist .(xich)ichp(xj)p(limichxich)jB.p(xj)=1p(limichxich)=0

Sei eine Turingmaschine. Definieren Sie eine Sequenz y i durch y i = { x j, wenn  T  in Schritt j anhält  und  j i x i, wenn  T  nicht innerhalb von  i  Schritten anhält.  Die Sequenz ist gut definiert, da wir T bis zu i Schritten simulieren und entscheiden können, ob es hat innerhalb so vieler Schritte aufgehört oder nicht. Als nächstes beobachte, dass ( y i ) i eine Cauchy-Sequenz ist, weil ( x i )T.yich

yich={xjwenn T. hält im Schritt an j und jichxichwenn T. hört nicht in sich auf ich Schritte
T.ich(yich)ich(xich)ich bin eine Cauchy-Sequenz (wir lassen dies als Übung). Sei . Entweder p ( z ) = 0 oder p ( z ) = 1 :z=limichyichp(z)=0p(z)=1
  • wenn ist, läuft T für immer. In der Tat, wenn es nach j Schritten aufhört , dann hätten wir z = x j , und so würde p ( z ) = p ( x j ) = 1 p ( z ) = 0 widersprechen .p(z)=0T.jz=xjp(z)=p(xj)=1p(z)=0

  • Wenn ist, läuft T nicht für immer. Wenn dies der Fall wäre, hätten wir in der Tat z = lim i x i und somit p ( z ) = p ( lim i x i ) = 0 , was p ( z ) = 0 widerspricht . p(z)=1T.z=limichxichp(z)=p(limichxich)=0p(z)=0

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 a , b R hätten, so dass p ( a ) = 0 und p ( 1 ) = 1 , 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 : R{ 0 , 1 }p::R.{0,1}}ein,bR.p(ein)=0p(1)=1p::R.{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 { 0 , 1 } ) einem Paar disjunkter Clopen- (geschlossen und offen) Mengen U , V X entspricht, so dass U V = X . Nehmen Sie in der Tat U = p - 1 ( { 0 } ) und V = p - 1 ( { 1 })p::X.{0,1}}{0,1}}U.,V.X.U.V.=X.U.=p- -1({0}}) . Da p stetig ist und { 0 } und { 1 } offen sind, sind U und V offen, disjunkt und decken offensichtlich ganz X ab . Umgekehrt bestimmt jedes Paar ( U , V ) disjunkter Clopens, die X bedecken, eine kontinuierliche Abbildung p : X { 0 , 1 } , die Elemente von U auf 0 und Elemente von V auf 1 abbildet.V.=p- -1({1}})p{0}}{1}}U.V.X.(U.,V.)X.p::X.{0,1}}U.0V.1

Daraus lernen wir, dass ein Raum genau dann getrennt wird, wenn eine stetige Abbildung p : X { 0 , 1 } und a , b X existiert, so dass p ( a ) = 0 und p ( 1 ) = b (wir brauchen a und b, damit wir eine nicht triviale Zerlegung von X erhalten ). Es gibt eine andere Möglichkeit, dasselbe zu sagen: Ein Raum X ist genau dann verbunden, wenn alle fortlaufenden Karten vorhanden sindX.p::X.{0,1}}a,bXp(a)=0p(1)=babXX sind konstant.X{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 .NN

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 y i = x, wenn T nicht innerhalb von i Schritten anhält, und y i = x ' ansonsten. Wenn T nicht anhält, konvergiert y i gegen x , andernfalls konvergiert es gegen x ' . Wenn x , x ' berechenbar sind, kann man bei gegebener T eine Maschine erzeugen, die die Grenze von berechnetp(x)=1,p(x)=0yi=xTiyi=xyixxx,xT . Warum ist das nicht genugum zu zeigendass p nicht berechenbar sein, oder sogar semidecidable (wie T halt nicht genau dannwenn p ist 1 am Limit). Offensichtlich fehlt mir etwas, da es nicht triviale Eigenschaften gibt, die halbentscheidbar sind. yipTp1
Ariel
1
Ihre Definition von ist in Ordnung , aber Sie benötigen auch eine berechenbare Konvergenzrate der Sequenz y i, um zu behaupten, dass ihre Grenze berechenbar ist. Da wir nicht berechnen können, bei welchem ​​Index i die Sequenz y i von x nach x ' springen könnte (oder wir könnten berechnen, bei welchem ​​Schritt T anhalten wird), kann eine solche berechenbare Konvergenzrate nicht gehabt werden. TyiiyixxT
Andrej Bauer
-1

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
1
Ich bin mir nicht sicher, was du hier meinst. Versuchen Sie , zwischen berechenbaren reellen Zahlen (zB zu unterscheiden , 22 / 7 , π , 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. 222/7π
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