Entscheidbarkeit transzendentaler Zahlen

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.

computability computable-analysis ipsofacto
quelle

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

Wie wird diese Implikation gezeigt?

$\:$

Antworten:

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 so dass bei jedem wir haben für alle $(a_n)_n$ $f$ $k$ $|a_{m} - a_{n}| < 2^{-k}$ $m, n \geq f(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 die berechenbar Cauchy ist und deren Grenze außerhalb von . Dann ist die Frage "ist eine reelle Zahl ein Element von " unentscheidbar. $S \subseteq \mathbb{R}$ $(a_n)_n$ $x = \lim_n a_n$ $S$ $x$ $S$

Beweis. Angenommen, entscheidbar. Betrachten Sie bei jeder Turingmaschine die Sequenz die als Es ist leicht zu überprüfen, ob rechnerisch Cauchy ist, daher können wir seine Grenze berechnen . Jetzt haben wir $S$ $T$ $b_n$

b_{n} = {\begin{cases} a_{n} & if T has not halted in the first n steps, \\ a_{m} & if T has halted in step m and m \leq n . \end{cases}

$b_n = \begin{cases} a_n & \text{if $T$ has not halted in the first $n$ steps,}\\ a_m & \text{if $T$ has halted in step $m$ and $m \leq n$.} \end{cases}$

b_{n}

$b_n$

y = lim_{n} b_{n}

$y = \lim_n b_n$

iff

hält an, damit wir das Halteproblem lösen können. QED.

y \in S

$y \in S$

T

$T$

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

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

Eine Menge, die die Bedingungen des Satzes nicht erfüllt, ist die Menge rationaler Zahlen, die durch eine nicht berechenbare Zahl . Übung: Ist entscheidbar? $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ $\alpha$ $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

$S$

S

$S$

Andrej Bauer

Was bedeutet es für

, "außerhalb von

berechenbar" zu sein (im Gegensatz zu "außerhalb von

") ?

x

$x$

S

$S$

S

$S\hspace{.01 in}$ ")

$\:$ ?

$\;\;$

Das war ein Tippfehler. Ich fidex es, danke, dass du es bemerkt hast. Andernfalls "

ist computably außerhalb

" könnte so etwas wie meine "für jedes

wir für eine positive rationale berechnen kann

, so daß

", dh die Aussage "

x

$x$

S

$S$

y \in S

$y \in S$

q

$q$

d (x, y) > q

$d(x,y) > q$

\forall y \in S . \exists q \in Q . 0 < q < d (x, y)

$\forall y \in S . \exists q \in \mathbb{Q} . 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

ist. In diesem Fall gibt es also keinen Unterschied zwischen" außerhalb von

"und" berechenbar außerhalb von

x

$x$

S

$S$

S

$S$

S

$S$

Andrej Bauer

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

Kristoffer Arnsfelt Hansen
quelle

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

David Harris
quelle

Die Menge der berechenbaren reellen Zahlen ist in

nicht offen (insbesondere ist sie in

dicht und verdichtet ), aber sie ist entscheidbar.

R

$\mathbf{R}$

R

$\mathbf{R}$

$\:$

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

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.

$\;\;$

e \in N

$e \in \mathbb{N}$

e

$e$

@Carl: Es gibt einen Algorithmus, um einen Index zu erhalten

e \in N

$\: e\in \mathbb{N} \:$

e

$e$

$\hspace{.1 in}$ ein berechenbarer Real.

$\;\;$ Dies ist das einzig interessante Gefühl der Entscheidbarkeit von Realmengen, weil

$\hspace{.2 in}$ Ihre (1) wird genau durch Mengen ohne berechenbare Real erfüllt

$\hspace{2.2 in}$ und dein (2) ist genau zufrieden mit

{}

$\: \{\} \:$

R

$\mathbf{R}$

$\;\;\;$