Decidability angka transendental

Saya punya pertanyaan, yang jawabannya mungkin terkenal, tetapi saya tidak bisa menemukan sesuatu yang berarti setelah sedikit pencarian, jadi saya sangat menghargai bantuan.

Pertanyaan saya adalah apakah diketahui bahwa memutuskan apakah suatu angka bersifat transendental tidak dapat diputuskan.

Mungkin, orang menganggap sebagai input, katakan sebuah program yang mengembalikan bit ke-i dari angka tersebut. Terima kasih sebelumnya untuk petunjuk apa pun.

computability computable-analysis ipsofacto
sumber

Jika real diwakili oleh program yang menghitung bit yang diberikan, atau program yang menghitung perkiraan rasional, atau program sejenis lainnya, maka hanya set real yang dapat ditentukan adalah yang sepele (yaitu, yang berisi semua real yang dapat dihitung atau tidak real yang dapat dihitung) , oleh teorema Rice.

Emil Jeřábek

Bagaimana implikasi itu ditunjukkan?

$\:$

Jawaban:

Solusi Kristoffer dapat digunakan untuk menunjukkan bahwa, dengan asumsi real diwakili sehingga kita dapat menghitung batas urutan real yang dapat dihitung Cauchy. Ingat bahwa urutan adalah computably Cauchy jika ada peta dihitung seperti itu, mengingat setiap kita memiliki untuk semua $(a_n)_n$ $f$ $k$ $|a_{m} - a_{n}| < 2^{-k}$ $m, n \geq f(k)$ . Representasi standar real seperti itu, misalnya yang real diwakili oleh mesin yang menghitung perkiraan rasional yang baik secara sewenang-wenang. (Kita juga dapat berbicara dalam hal angka komputasi, tetapi kemudian kita harus membiarkan angka negatif. Ini adalah masalah yang terkenal dalam teori komputabilitas dari real.)

$S \subseteq \mathbb{R}$ $(a_n)_n$ $x = \lim_n a_n$ $S$ $x$ $S$

Bukti. Misalkan dapat dipilih. Diberikan mesin Turing apa pun , pertimbangkan urutan didefinisikan sebagai Mudah untuk memeriksa bahwa adalah computably Cauchy, oleh karena itu kita dapat menghitung batasnya . Sekarang kita memiliki iff berhenti, sehingga kita dapat memecahkan Masalah Henti. QED. $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$

y \in S

$y \in S$

T

$T$

Ada teorema ganda di mana kita asumsikan urutan luar tetapi batasnya adalah di . $S$ $S$

Contoh himpunan memenuhi kondisi ini adalah: interval terbuka, interval tertutup, angka negatif, singleton , bilangan rasional, bilangan irasional, bilangan transcedental, bilangan aljabar, dll. $S$ $\lbrace 0 \rbrace$

Satu set yang tidak memenuhi kondisi teorema adalah himpunan bilangan rasional diterjemahkan oleh non-komputasi jumlah . Latihan: apakah dapat dipilih? $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ $\alpha$ $S$

Andrej Bauer
sumber

Terima kasih untuk balasan Anda. Hanya klarifikasi, apakah teorema mengatakan bahwa jika himpunan S memiliki setidaknya satu titik batas di luar S, maka memutuskan apakah suatu elemen x berada dalam S tidak dapat ditentukan? Kemudian, saya agak bingung tentang interval tertutup dalam contoh.

ipsofacto

Interval tertutup berikut dengan teorema ganda di mana Anda mengambil urutan luar yang batas di .

S

$S$

S

$S$

Andrej Bauer

Apa artinya menjadi "di luar dapat dihitung" (sebagai lawan dari "di luar ") :?

x

$x$

S

$S$

S

$S\hspace{.01 in}$

$\:$

$\;\;$

Itu salah ketik. Aku melakukannya, terima kasih sudah memperhatikan. Kalau tidak, " dapat dihitung di luar " bisa berarti sesuatu seperti "untuk setiap kita dapat menghitung rasional yang positif sehingga ", yaitu, pernyataan " "direalisasikan. Tetapi jika Anda percaya pada prinsip Markov, maka Anda dapat merekonstruksi peta seperti itu hanya dengan mengetahui bahwa tidak ada di , jadi dalam hal ini tidak ada perbedaan antara "di luar dan" yang dapat dihitung di luar ".

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)$

x

$x$

S

$S$

S

$S$

S

$S$

Andrej Bauer

Diberikan mesin Turing , tentukan mesin Turing mewakili angka sebagai berikut: Pada input menjalankan untuk langkah pada input kosong. Jika berhenti, output . Kalau tidak, output bit . $M$ $M'$ $i$ $M$ $i$ $M$ $0$ $i$ $\pi$

Kristoffer Arnsfelt Hansen
sumber

Himpunan transendental tidak terbuka di (khususnya, padat dan kodens dalam Oleh karena itu tidak dapat diputuskan. $\mathbf R$ $\mathbf R$

David Harris
sumber

R

$\mathbf{R}$

R

$\mathbf{R}$

$\:$

Ricky, ini tidak benar. Diberi oracle untuk bilangan real, Anda tidak dapat menentukan apakah itu dapat dihitung atau tidak.

David Harris

Set yang saya berikan dapat dipilih, dengan algoritma yang selalu menjawab "Ya".

$\:$ Kalimat kedua Anda menunjukkan bahwa himpunan yang saya berikan tidak bertipe dua yang dapat dipilih.

$\;\;$

e \in N

$e \in \mathbb{N}$

e

$e$

@ Carl: Ada algoritma untuk diberi indeks

e \in N

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

e

$e$

$\hspace{.1 in}$ real yang dapat dihitung.

$\;\;$ Ini adalah satu - satunya rasa menarik dari decidability set real, karena

$\hspace{.2 in}$ (1) Anda puas persis dengan set tanpa real yang dapat dihitung

$\hspace{2.2 in}$ dan (2) Anda dipenuhi persis oleh

{}

$\: \{\} \:$

R

$\mathbf{R}$

$\;\;\;$