Apakah mungkin untuk menguji apakah bilangan yang dihitung rasional atau bilangan bulat?

Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational?

Saya menduga itu tidak mungkin, dan bahwa ini entah bagaimana terkait dengan fakta bahwa tidak mungkin untuk menguji apakah dua angka sama, tetapi saya tidak melihat bagaimana membuktikannya.

Sunting: Angka dapat dihitung diberikan oleh fungsi yang dapat mengembalikan perkiraan rasional dengan presisi : , untuk setiap . Dengan fungsi seperti itu, apakah mungkin untuk menguji apakah atau ?f x ( ϵ ) x ϵ | x - f x ( ϵ ) | ≤ ϵ ϵ > 0 x ∈ Q x ∈ $x$$f_x(\epsilon)$$x$$\epsilon$$|x - f_x(\epsilon)| \leq \epsilon$$\epsilon > 0$$x \in \mathrm{Q}$$x \in \mathrm{Z}$

Sangat mudah untuk bingung tentang apa artinya "mewakili" atau "menerapkan" bilangan real. Bahkan, kami menyaksikan diskusi di komentar di mana representasi itu kontroversial. Jadi izinkan saya mengatasi ini dulu.

Bagaimana kita tahu bahwa implementasi itu benar?

Teori yang menjelaskan bagaimana merepresentasikan sesuatu dalam komputer adalah realisasi . Ide dasarnya adalah bahwa, diberikan himpunan , kami memilih tipe data dan untuk setiap set nilai dari tipe yang menyadarinya . Kami menulis ketika adalah nilai yang menyadari . Misalnya (saya akan menggunakan Haskell tanpa alasan yang jelas), implementasi masuk akal mungkin merupakan tipe data di mana saat mengevaluasi ke angka ( dengan demikian khususnyaτ x ∈ X τ v ⊢ x ∈ X v x N v ⊢ k ∈ N v ¯ k T r u e ⊢ 42 ∈ N F a l s e ⊢ n ∈ n ∈ N n ≠ $X$$\tau$$x \in X$$\tau$$v \vdash x \in X$$v$$x$$\mathbb{N}$Integer$v \vdash k \in \mathbb{N}$$v$$\overline{k}$-42tidak mewakili angka alami, dan juga tidak ada program yang berbeda). Tetapi beberapa joker bisa berjalan dan menyarankan agar kita gunakan Booluntuk merepresentasikan bilangan asli dengan dan untuk . Kenapa ini salah? Kami membutuhkan kriteria .$\mathtt{True} \vdash 42 \in \mathbb{N}$$\mathtt{False} \vdash n \in \mathbb{N}$$n \neq 42$

Dalam kasus "angka joker" pengamatan yang mudah adalah bahwa penambahan tidak dapat diterapkan. Misalkan saya memberi tahu Anda saya memiliki dua angka, keduanya diwakili oleh . Bisakah Anda memberi realizer untuk jumlah mereka? Ya, itu tergantung apakah jumlahnya 42, tetapi Anda tidak tahu. Karena penambahan adalah "bagian penting dari bilangan asli", ini tidak dapat diterima. Dengan kata lain, implementasi bukan tentang set, tetapi tentang struktur , yaitu, kita harus mewakili set sedemikian rupa sehingga dimungkinkan untuk juga menerapkan struktur yang relevan. Biarkan saya menekankan ini:$\mathtt{False}$

Kami menerapkan struktur, bukan set telanjang. Oleh karena itu, kita harus dapat mengimplementasikan seluruh struktur, bersama dengan operasi dan semua aksioma, agar implementasi menjadi benar.

Jika Anda tidak mematuhi prinsip ini, maka Anda harus menyarankan kriteria matematis alternatif tentang kebenaran. Saya tidak tahu satu pun.

Contoh: representasi bilangan asli

Untuk bilangan asli struktur yang relevan dijelaskan oleh aksioma Peano, dan aksioma penting yang harus dilaksanakan adalah induksi (tetapi juga , penerus, dan ). Kita dapat menghitung, menggunakan kesadaran, apa yang dilakukan oleh induksi. Ternyata menjadi peta (di mana datatype belum diketahui yang mewakili bilangan asli)+ $0$$+$$\times$nat

induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

memuaskan induction x f zero = xdan induction x f (succ n) = f n (induction x f n). Semua ini keluar dari kesadaran. Kami memiliki kriteria: implementasi bilangan asli benar ketika memungkinkan implementasi aksioma Peano. Hasil serupa akan diperoleh jika kita menggunakan karakterisasi angka sebagai aljabar awal untuk functor .$X \mapsto 1 + X$

Implementasi bilangan real yang benar

Mari kita perhatikan bilangan real dan pertanyaan yang ada. Pertanyaan pertama yang diajukan adalah "apa struktur yang relevan dari bilangan real?" Jawabannya adalah: Archimedean Cauchy isian lengkap yang dipesan . Ini adalah arti mapan dari "bilangan real". Anda tidak bisa mengubahnya, itu telah diperbaiki oleh orang lain untuk Anda (dalam kasus kami real Dedekind alternatif ternyata isomorfik dengan real Cauchy, yang kami pertimbangkan di sini.) Anda tidak dapat mengambil bagian dari itu, Anda tidak diperbolehkan mengatakan "Saya tidak peduli tentang penerapan penambahan", atau "Saya tidak peduli dengan pesanan". Jika Anda melakukan itu, Anda tidak boleh menyebutnya "bilangan real", tetapi sesuatu seperti "bilangan real di mana kami lupa urutan linier".

Saya tidak akan membahas semua detail, tetapi izinkan saya hanya menjelaskan bagaimana berbagai bagian struktur memberikan berbagai operasi pada real:

• yang Archimedean aksioma adalah tentang komputasi rasional perkiraan dari real
• struktur lapangan memberikan operasi aritmatika yang biasa
• urutan linier memberi kita prosedur yang dapat ditentukan sebelumnya untuk pengujian $x < y$
• lim : (nat -> real) -> real$(x_n)_n$ m , $|x_n - x_m| \leq 2^{\min(n,m)}$$m, n$

Apa yang kita tidak dapatkan adalah fungsi tes untuk kesetaraan. Tidak ada dalam aksioma untuk real yang meminta bahwa dapat dipilih. (Sebaliknya, aksioma Peano menyiratkan bahwa bilangan asli dapat ditentukan, dan Anda dapat membuktikan bahwa dengan menerapkan hanya menggunakan sebagai latihan yang menyenangkan).$=$eq : nat -> nat -> Boolinduction

Adalah fakta bahwa representasi desimal biasa dari realita yang digunakan umat manusia adalah buruk karena dengan itu kita bahkan tidak dapat mengimplementasikan penambahan. Titik mengambang dengan mantissa tak terbatas juga gagal (olahraga: mengapa?). Apa yang berhasil, bagaimanapun adalah representasi digit yang ditandatangani , yaitu, di mana kami mengizinkan digit negatif dan juga digit positif. Atau kita bisa menggunakan urutan rasional yang memenuhi tes Cauchy cepat, seperti yang dinyatakan di atas.

Representasi Tsuyoshi juga mengimplementasikan sesuatu, tetapi tidak$\mathbb{R}$

Mari kita perhatikan representasi real berikut: a nyata diwakili oleh pasangan mana adalah deretan Cauchy cepat yang konvergen ke dan adalah Boolean yang menunjukkan apakah adalah bilangan bulat. Agar ini menjadi representasi dari real, kita harus mengimplementasikan penambahan, tetapi ternyata kita tidak dapat menghitung bendera Boolean. Jadi ini bukan representasi dari real. Tapi itu masih merupakan sesuatu, yaitu bagian dari real( q , b ) ( q n ) n x b x Z ∪ ( R ∖ Z ) Z ∪ ( R ∖ Z ) $x$$(q,b)$$(q_n)_n$$x$$b$$x$$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$. Memang, menurut interpretasi realisasi sebuah serikat diterapkan dengan bendera yang menunjukkan bagian mana dari serikat kita berada. Omong-omong, adalah a tidak sama dengan , kecuali jika Anda percaya pada tengah yang dikecualikan, yang tidak dapat diimplementasikan dan karena itu sangat tidak relevan untuk diskusi ini. Kita dipaksa oleh komputer untuk melakukan berbagai hal secara intuisi.$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$$\mathbb{R}$

Kami tidak dapat menguji apakah real adalah bilangan bulat

Akhirnya, izinkan saya menjawab pertanyaan yang diajukan. Kita sekarang tahu bahwa representasi real yang dapat diterima adalah satu dengan deretan rasional Cauchy yang cepat. (Teorema penting menyatakan bahwa dua representasi real yang dapat diterima sebenarnya adalah isomorfik yang dapat dihitung).

Teorema: Menguji apakah real adalah integer tidak dapat ditentukan.

Bukti. Misalkan kita dapat menguji apakah real adalah bilangan bulat (tentu saja, real direalisasikan oleh deretan Cauchy yang cepat). Idenya, yang akan memungkinkan Anda untuk membuktikan teorema yang jauh lebih umum jika Anda mau, adalah untuk membangun urutan Cauchy cepat dari non-integer yang konvergen ke integer. Ini mudah, ambil saja . Selanjutnya, selesaikan masalah Hentikan sebagai berikut. Diberikan mesin Turing , tentukan urutan baru oleh Artinya, urutan baru seperti urutan selamax n = 2 - n T ( y n ) n y n = { x n jika  T  tidak berhenti dalam  n  langkah x m jika  T  berhenti pada langkah  m  dan  m ≤ n ( x n ) n T x m T m T z = lim n y n z $(x_n)_n$$x_n = 2^{-n}$$T$$(y_n)_n$

$$y_n = \begin{cases} x_n & \text{if $T$ has not stopped within $n$ steps}\\ x_m & \text{if $T$ stopped in step $m$ and $m \leq n$} \end{cases}$$ $(x_n)_n$$T$berjalan, tetapi kemudian "macet" di jika berhenti pada langkah . Sangat penting, urutan baru juga merupakan urutan Cauchy cepat (dan kita dapat membuktikan ini tanpa mengetahui apakah berhenti). Oleh karena itu, kita dapat menghitung batasnya , karena representasi real kita benar. Uji apakah adalah bilangan bulat. Jika ya, maka harus dan ini hanya terjadi jika berjalan selamanya. Kalau tidak, bukan bilangan bulat, jadi harus berhenti. QED.$x_m$$T$$m$$T$$z = \lim_n y_n$$z$$0$z $T$$z$$T$

Latihan: sesuaikan bukti di atas untuk menunjukkan bahwa kita tidak dapat menguji angka rasional. Kemudian sesuaikan untuk menunjukkan bahwa kami tidak dapat menguji apa pun yang non-sepele (ini agak sulit).

Terkadang orang bingung tentang semua bisnis pengujian ini. Mereka pikir kami telah membuktikan bahwa kami tidak pernah dapat menguji apakah real adalah bilangan bulat. Tapi yang pasti, 42 adalah nyata dan kita bisa tahu apakah itu bilangan bulat. Faktanya, setiap real khusus yang kita buat, , , , dll., Kita dapat dengan baik mengetahui apakah mereka bilangan bulat. Tepatnya, kita dapat mengetahui karena kita memiliki informasi tambahan: real ini tidak diberikan kepada kita sebagai urutan, melainkan sebagai ekspresi simbolik dari mana kita dapat menghitung bit Tsuyoshi. Begitu satu-satunya informasi yang kita miliki tentang yang sebenarnya adalah serangkaian perkiraan rasional yang menyatu dengannya (dan saya lakukan88 ln 89 e π $\sin 11$$88 \ln 89$ n$e^{\pi \sqrt{163}}$bukan berarti ekspresi simbolik yang menggambarkan urutan, tetapi kotak hitam yang menampilkan istilah ke- pada input ) maka kita akan sama tidak berdaya dengan mesin.$n$$n$

Moral cerita

Tidak masuk akal untuk berbicara tentang implementasi suatu set kecuali kita tahu operasi apa yang ingin kita lakukan di atasnya.

Saya cenderung berpikir ini tidak dapat diputuskan:

Biarkan menjadi bilangan irasional yang dapat dihitung. Pertimbangkan TM . Anda dapat membangun fungsi yang menjalankan pada , dan secara paralel menghitung dengan presisi yang semakin besar. Jika berhenti, ia berhenti menghitung , jika tidak ia akan melanjutkan.M M ϵ x M $x$$M$$M$$\epsilon$$x$$M$$x$

Memutuskan apakah fungsi ini menghitung bilangan rasional setara dengan masalah penghentian.

Dengan asumsi nyata diberikan sebagai urutan perkiraan rasional dengan kesalahan yang dibatasi oleh beberapa fungsi yang diketahui dapat dihitung yang cenderung nol (semua perkiraan tersebut setara, dan sesuai dengan topologi biasa pada real).

Fungsi yang dapat dihitung kontinu. IsRational dan IsInteger tidak berkelanjutan dan karenanya tidak dapat dihitung.

IsInteger bersifat semi- komputasi: ada prosedur yang pada akhirnya akan menampilkan "false" jika inputnya bukan bilangan bulat, tetapi akan berjalan selamanya jika inputnya adalah bilangan bulat. Prosedur ini hanya melihat pada setiap perkiraan dan memeriksa apakah ada bilangan bulat dalam batas kesalahan. Fungsi ini kontinu ketika kita menggunakan topologi Sierpiński pada {true, false} (yaitu {false} adalah himpunan terbuka tetapi {true} tidak).

Tidak dapat dipastikan apakah angka yang dihitung sama dengan nol .

(Jadi oracle perkiraan Anda menghasilkan 0 untuk setiap ε yang Anda coba? Mungkin Anda belum memberikan ε yang cukup kecil.)

Dengan demikian, tidak dapat dipastikan apakah angka yang dapat dihitung antara -½ dan + ½ adalah bilangan bulat.

Fungsi yang dapat dihitung lebih kuat daripada fungsi yang berkelanjutan, artinya fungsi yang dapat dihitung harus kontinu dalam topologi informasi.

$F:\mathbb{R} \to \{Yes,No\}$

$$F(r) = \begin{cases} YES & r\in \mathbb{Q}\\ NO & o.w. \end{cases}$$

dapat dihitung.

$r$$\frac{k}{2^{n}}$$r \in [\frac{k}{2^n},\frac{k+1}{2^n}]$$n$

Maka fungsi Anda tidak kontinu dan karenanya tidak dapat dihitung.

$M$$0$$n$$[-\frac{1}{2^n},\frac{1}{2^n}]$$M$$M$$m$$M$$[-\frac{1}{2^m},\frac{1}{2^m}]$$M$$M$$NO$$YES$$M$$[-\frac{1}{2^m},\frac{1}{2^m}]$$M$$YES$$M$

Bukti bahwa setiap fungsi yang dikomputasi perlu kontinu adalah serupa.