Entscheidbarkeit transzendentaler Zahlen

9

Ich habe eine Frage, deren Antwort wahrscheinlich bekannt ist, aber ich kann nach einigem Suchen anscheinend nichts Sinnvolles finden, daher würde ich mich über Hilfe freuen.

Meine Frage ist, ob bekannt ist, dass die Entscheidung, ob eine Zahl transzendent ist, unentscheidbar ist.

Möglicherweise nimmt man als Eingabe ein Programm an, das das i-te Bit der Zahl zurückgibt. Vielen Dank im Voraus für Hinweise.

ipsofacto
quelle
5
Wenn Realzahlen durch Programme dargestellt werden, die ein bestimmtes Bit berechnen, oder durch Programme, die rationale Approximationen berechnen, oder durch eine ähnliche Art von Programmen, dann sind die einzigen entscheidbaren Mengen von Realzahlen die trivialen (dh diejenigen, die entweder alle berechenbaren Realzahlen oder keine berechenbaren Realzahlen enthalten). nach dem Satz von Rice.
Emil Jeřábek
1
Wie wird diese Implikation gezeigt?

Antworten:

8

Kristoffers Lösung kann verwendet werden, um zu zeigen, dass unter der Annahme, dass Realwerte dargestellt werden, wir Grenzen von Sequenzen von Realwerten berechnen können, die berechenbar Cauchy sind. Denken Sie daran, dass eine Sequenz berechenbar Cauchy ist, wenn es eine berechenbare Abbildung f gibt, so dass bei jedem k, das wir haben | a m - a n | < 2 - k für alle m , n f ( k )(einn)nfk|einm- -einn|<2- -km,nf(k). Die Standarddarstellungen von Real sind ähnlich, zum Beispiel die, bei denen ein Real durch eine Maschine dargestellt wird, die eine beliebig gute rationale Näherung berechnet. (Wir können auch in Bezug auf die Berechnung von Ziffern sprechen, aber dann müssen wir negative Ziffern zulassen. Dies ist ein bekanntes Problem in der Berechenbarkeitstheorie der Realzahlen.)

Satz: Angenommen, ist eine Teilmenge, so dass es eine berechenbare Folge ( a n ) n gibt, die berechenbar Cauchy ist und deren Grenze x = lim n a n außerhalb von S liegt . Dann ist die Frage "ist eine reelle Zahl x ein Element von S " unentscheidbar.SR(an)nx=limnanSxS

Beweis. Angenommen, entscheidbar. Betrachten Sie bei jeder Turingmaschine T die Sequenz b n, die als b n = { a n definiert ist, wenn  T  in den ersten n  Schritten nicht angehalten hat  , a m, wenn  T  in Schritt m angehalten hat   und  m n . Es ist leicht zu überprüfen, ob b n rechnerisch Cauchy ist, daher können wir seine Grenze y = lim n b n berechnen . Jetzt haben wir ySTbn

bn={anif T has not halted in the first n steps,amif T has halted in step m and mn.
bny=limnbn iff T hält an, damit wir das Halteproblem lösen können. QED.yST

Es gibt einen dualen Satz, in dem wir annehmen, dass die Sequenz außerhalb von , ihre Grenze jedoch in S liegt .SS

Beispiele für Mengen die diese Bedingungen erfüllen, sind: ein offenes Intervall, ein geschlossenes Intervall, die negativen Zahlen, der Singleton { 0 } , rationale Zahlen, irrationale Zahlen, transzedentale Zahlen, algebraische Zahlen usw.S{0}

Eine Menge, die die Bedingungen des Satzes nicht erfüllt, ist die Menge rationaler Zahlen, die durch eine nicht berechenbare Zahl α übersetzt werden . Übung: Ist S entscheidbar?S={q+αqQ}αS

Andrej Bauer
quelle
Danke für deine Antwort. Nur eine Klarstellung, sagt der Satz, dass wenn die Menge S mindestens einen Grenzpunkt außerhalb von S hat, dann zu entscheiden, ob ein Element x in S unentscheidbar ist? Dann bin ich etwas verwirrt über das geschlossene Intervall in den Beispielen.
ipsofacto
Das geschlossene Intervall folgt dem dualen Satz, in dem Sie eine Folge außerhalb von deren Grenze in S liegt . SS
Andrej Bauer
Was bedeutet es für , "außerhalb von S berechenbar" zu sein (im Gegensatz zu "außerhalb von S ") ?xSS")?
Das war ein Tippfehler. Ich fidex es, danke, dass du es bemerkt hast. Andernfalls " ist computably außerhalb S " könnte so etwas wie meine "für jedes y S wir für eine positive rationale berechnen kann q , so daß d ( x , y ) > q ", dh die Aussage " y S . q Q . 0 < q < d ( x , y )xSySqd(x,y)>qyS.qQ.0<q<d(x,y)"wird realisiert. Wenn Sie jedoch an das Markov-Prinzip glauben, können Sie eine solche Karte rekonstruieren, indem Sie nur wissen, dass nicht in S ist. In diesem Fall gibt es also keinen Unterschied zwischen" außerhalb von S "und" berechenbar außerhalb von S ". xSSS
Andrej Bauer
5

Bei einer Turing Maschine , definiert eine Turing Maschine M ' repräsentiert eine Zahl wie folgt: Bei der Eingabe i laufe M für i auf den leeren Eingabeschritte. Wenn M angehalten hat, wird 0 ausgegeben . Andernfalls wird das i- te Bit von π ausgegeben .MMiMiM0iπ

Kristoffer Arnsfelt Hansen
quelle
1

Die Menge der Transzendentalen ist in nicht offen (insbesondere ist sie in R dicht und verdichtet . Daher ist sie unentscheidbar.RR

David Harris
quelle
4
Die Menge der berechenbaren reellen Zahlen ist in nicht offen (insbesondere ist sie in R dicht und verdichtet ), aber sie ist entscheidbar.RR
1
Ricky, das ist nicht wahr. Bei einem Orakel für eine reelle Zahl können Sie nicht feststellen, ob es berechenbar ist oder nicht.
David Harris
1
Der Satz, den ich gegeben habe, ist durch den Algorithmus entscheidbar, der immer mit "Ja" antwortet. Ihr zweiter Satz zeigt, dass der Satz, den ich gegeben habe, nicht vom Typ zwei entscheidbar ist.
eNe
@Carl: Es gibt einen Algorithmus, um einen Index zu erhalten eNe ein berechenbarer Real. Dies ist das einzig interessante Gefühl der Entscheidbarkeit von Realmengen, weil Ihre (1) wird genau durch Mengen ohne berechenbare Real erfüllt und dein (2) ist genau zufrieden mit {}R