Rozstrzygalność liczb transcendentalnych

Mam pytanie, na które odpowiedź jest prawdopodobnie dobrze znana, ale nie wydaje mi się, że po kilku poszukiwaniach znajdę coś znaczącego, więc byłbym wdzięczny za pomoc.

Moje pytanie brzmi, czy wiadomo, że podjęcie decyzji, czy liczba jest transcendentalna, jest nierozstrzygalne.

Być może ktoś przyjmuje jako dane wejściowe, powiedzmy program, który zwraca i-ty bit liczby. Z góry dziękuję za wszelkie wskazówki.

computability computable-analysis

— ipsofacto
źródło

Jeśli liczby rzeczywiste są reprezentowane przez programy obliczające dany bit lub programy obliczające racjonalne aproksymacje, lub jakiekolwiek podobne programy, wówczas jedynymi decydującymi zestawami liczb rzeczywistych są trywialne (tj. Te, które zawierają wszystkie obliczalne wartości rzeczywiste lub żadnych obliczalnych wartości rzeczywiste) , według twierdzenia Rice'a.

— Emil Jeřábek

Jak pokazano tę implikację?

$\:$

Odpowiedzi:

Rozwiązania Kristoffera można użyć do wykazania, że przy założeniu, że realia są reprezentowane, abyśmy mogli obliczyć granice sekwencji reali, które są obliczalnie Cauchy'ego. Przypomnij sobie, że sekwencja $(a_n)_n$ jest obliczalne Cauchy'ego, jeśli istnieje mapa obliczalna $f$ takie, że dane $k$ mamy $|a_{m} - a_{n}| < 2^{-k}$ dla wszystkich $m, n \geq f(k)$ . Standardowe reprezentacje rzeczywistości są takie, na przykład ta, w której rzeczywistość jest reprezentowana przez maszynę, która oblicza dowolnie dobre racjonalne przybliżenie. (Możemy również mówić w kategoriach cyfr obliczeniowych, ale musimy dopuścić cyfry ujemne. Jest to dobrze znany problem w teorii obliczeń rzeczywistych.)

Twierdzenie: załóżmy $S \subseteq \mathbb{R}$ jest podzbiorem takim, że istnieje sekwencja obliczalna $(a_n)_n$ która jest obliczalna Cauchyego i jego granica $x = \lim_n a_n$ jest na zewnątrz $S$ . Zatem pytanie „jest liczbą rzeczywistą $x$ element $S$ „jest nierozstrzygalny.

Dowód. Przypuszczać $S$ były rozstrzygalne. Biorąc pod uwagę dowolną maszynę Turinga $T$ rozważ sekwencję $b_n$ zdefiniowana jako

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}$ Łatwo to sprawdzić

b_{n}

$b_n$ jest obliczalne Cauchy'ego, dlatego możemy obliczyć jego limit

y = lim_{n} b_{n}

$y = \lim_n b_n$ . Teraz mamy

y \in S

$y \in S$ iff

T

$T$ zatrzymuje się, abyśmy mogli rozwiązać problem zatrzymania. CO BYŁO DO OKAZANIA.

Istnieje podwójne twierdzenie, w którym zakładamy, że sekwencja jest na zewnątrz $S$ ale jego limit jest w $S$ .

Przykłady zestawów $S$ spełniające te warunki to: przerwa otwarta, przerwa zamknięta, liczby ujemne, singleton $\lbrace 0 \rbrace$ , liczby wymierne, liczby niewymierne, liczby transcedentalne, liczby algebraiczne itp.

Zbiór niespełniający warunków twierdzenia jest zbiorem $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ liczb wymiernych przetłumaczonych przez liczbę niepoliczalną $\alpha$ . Ćwiczenie: jest $S$ rozstrzygalny?

— Andrej Bauer
źródło

Dzięki za odpowiedź. Tylko wyjaśnienie, czy twierdzenie mówi, że jeśli zbiór S ma co najmniej jeden punkt graniczny poza S, to podjęcie decyzji, czy element x jest w S nierozstrzygalny? W tych przykładach jestem nieco zdezorientowany co do zamkniętego interwału w przykładach.

— ipsofacto

Po zamkniętym przedziale następuje podwójne twierdzenie, w którym bierzesz sekwencję na zewnątrz

S

$S$ którego limit jest w

S

$S$ .

— Andrej Bauer,

Co to znaczy

x

$x$ być na zewnątrz

S

$S$ obliczalnie ”(w przeciwieństwie do„ na zewnątrz

S

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

$\:$ ?

$\;\;$

To była literówka. Fidex, dzięki za zauważenie. Inaczej, "

x

$x$ jest obliczalnie na zewnątrz

S

$S$ „może oznaczać coś takiego” dla każdego

y \in S

$y \in S$ możemy obliczyć pozytywne racjonalne

q

$q$ takie, że

d (x, y) > q

$d(x,y) > q$ „, tj. oświadczenie”

\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)$ "zostało zrealizowane. Ale jeśli wierzysz w zasadę Markowa, możesz zrekonstruować taką mapę, wiedząc o tym

x

$x$ nie jest w

S

$S$ , więc w tym przypadku nie ma różnicy między „na zewnątrz”

S

$S$ i „obliczalnie na zewnątrz

S

$S$ „.

— Andrej Bauer,

Biorąc pod uwagę maszynę Turinga $M$ , zdefiniuj maszynę Turinga $M'$ reprezentujący liczbę w następujący sposób: na wejściu $i$ biegać $M$ dla $i$ kroki na pustym wejściu. Gdyby $M$ zatrzymany, wyjście $0$ . W przeciwnym razie wypisz $i$ trochę $\pi$ .

— Kristoffer Arnsfelt Hansen
źródło

Zestaw transcendentałów nie jest otwarty w $\mathbf R$ (w szczególności jest gęsty i codense w $\mathbf R$ . Dlatego jest nierozstrzygalny.

— David Harris
źródło

Zestaw obliczalnych liczb rzeczywistych nie jest otwarty

R

$\mathbf{R}$ (w szczególności jest gęsty i codense w

R

$\mathbf{R}$ ), ale jest to rozstrzygalne.

$\:$

Ricky, to nie prawda. Biorąc pod uwagę wyrocznię dla liczby rzeczywistej, nie można ustalić, czy można ją obliczyć, czy nie.

— David Harris

Zestaw, który podałem, jest rozstrzygalny według algorytmu, który zawsze odpowiada „Tak”.

$\:$ Twoje drugie zdanie pokazuje, że zbiór, który podałem, nie podlega rozstrzygnięciu typu drugiego.

$\;\;$

@Ricky Demer: zbiór obliczalnych liczb rzeczywistych jest nierozstrzygalny w dwóch aspektach: (1) biorąc pod uwagę dowolny indeks

e \in N

$e \in \mathbb{N}$ , decydować czy

e

$e$ jest indeksem maszyny Turinga, która oblicza obliczalną rzeczywistość. (2) biorąc pod uwagę dowolną szybko zbieżną sekwencję Cauchy'ego, ustal, czy jest to sekwencja obliczalna. Nie ma zdrowego rozsądku, w którym zbiór obliczalnych liczb rzeczywistych jest rozstrzygalny.

— Carl Mummert

@ Carl: Istnieje algorytm do nadania indeksu

e \in N

$\: e\in \mathbb{N} \:$ to jest indeks maszyny Turinga, który oblicza obliczalną rzeczywistość, zdecyduj, czy

e

$e$ jest indeksem obliczanej maszyny Turinga

$\hspace{.1 in}$ obliczalna rzeczywistość.

$\;\;$ Jest to jedyne interesujące poczucie rozstrzygalności zbiorów rzeczywistych, ponieważ

$\hspace{.2 in}$ twój (1) jest spełniony dokładnie przez zestawy bez rzeczywistych obliczalnych

$\hspace{2.2 in}$ a twój (2) jest dokładnie spełniony

{}

$\: \{\} \:$ i

R

$\mathbf{R}$ .

$\;\;\;$