Apakah Memutuskan Decidability Decidable?

Saya bertanya-tanya apakah memutuskan masalah decidability adalah masalah decidable. Saya kira tidak, tetapi setelah pencarian awal saya tidak dapat menemukan literatur tentang masalah ini.

Pengeditan utama dokumen asli saya:

Pembacaan yang naif terhadap pertanyaan Anda tampaknya, misalkan adalah masalahnya$P$

Diberi bahasa, L , apakah itu bisa digunakan?$P=$$L$

Lalu kamu bertanya

Apakah decidable?$P$

Seperti yang dicatat DW dan David, jawabannya adalah, "ya, benar", meskipun kita tidak tahu yang mana dari dua penentu sepele itu yang benar. Untuk membingkai masalah Anda sehingga tidak terlalu sepele, saya sarankan ini. Pertama, mari kita membatasi hal-hal yang sedikit dengan mempertimbangkan hanya mereka bahasa yang merupakan bahasa diterima oleh beberapa TM M . Alasan untuk melakukan ini adalah bahwa jika suatu bahasa tidak diterima oleh TM mana pun, maka itu tidak dapat dikenali kembali (dikenali) dan dengan demikian tidak dapat bersifat rekursif (decidable). Maka kita dapat menyusun kembali P sebagai$L(M)$$M$$P$

Mengingat deskripsi, ⟨ M ⟩ dari TM sebuah, M adalah L ( M ) decidable?$P'=$$\langle M\rangle$$M$$L(M)$

Sekarang adalah bahasa deskripsi TM, daripada bahasa bahasa sebagai P tampaknya (di bawah interpretasi murah hati), dan sekarang masuk akal untuk bertanya apakah bahasa P ' adalah decidable. Di bawah membaca ini, bahasa { ⟨ M ⟩ | M  adalah TM dan  L ( M )  adalah decidable } yang terdiri dari deskripsi TM tidak decidable. Ini adalah konsekuensi mudah dari Teorema Rice . Jadi sekarang kita memiliki dua jawaban: "tidak" dan "ya" dari DW saya, tergantung pada interpretasinya.$P'$$P$$P'$

Seperti yang telah kita lihat dalam jawaban yang berbeda, bagian dari jawabannya adalah dalam merumuskan masalah yang tepat.

Pada tahun 1985, Joost Engelfriet menulis "Ketidakmampuan komputabilitas" (Buletin EATCS nomor 26, Juni 1985, halaman 36-39) sebagai jawaban atas pertanyaan yang diajukan oleh siswa yang pandai. Sayangnya, BEATCS pada waktu itu hanya kertas dan artikel itu tidak meninggalkan jejak elektronik.

Penulis menganggap kita memiliki formalisme (logis) dengan operator dan variabel boolean yang biasa. Definisi yang tepat tidak penting. Rumus F ( m , n ) menetapkan fungsi f : N → N iff (untuk semua m , n ∈ N ) f ( m ) = n ⇔ F ( m _ , n _ ) benar, di mana m _ adalah bilangan mewakili angka m .$\Psi$$F(m,n)$$f:\Bbb N \to \Bbb N$$m,n\in \Bbb N$$f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$$\underline m$$m$

Saya mengutip:

$\Phi$$\Bbb N \to \Bbb N$$f$$f$

Bagian yang menyenangkan adalah dalam pengamatan berikut yang dibuat di koran:

$\Phi$

Iya. Itu selalu decidable.

Untuk setiap masalah P, misalkan Q adalah masalah menentukan apakah P dapat dipilih atau tidak. Saya mengklaim bahwa Q dapat dipilih. Inilah sebabnya. Secara tautologis, P dapat dipilih, atau tidak. Jadi, salah satu dari dua program itu benar: (1) print "yup P is decidable"atau (2) print "nope P is not decidable". Mungkin tidak sepele untuk mengetahui mana dari dua program yang benar, salah satunya benar, sehingga penentu untuk Q pasti ada . Oleh karena itu, masalah Q adalah decidable.

Ini mengingatkan kita pada pertanyaan klasik berikut: Apakah pantas untuk mengatakan apakah dugaan Collatz itu benar? Jawabannya iya. Ini mungkin terlihat aneh, karena tidak ada yang tahu apakah dugaan Collatz itu benar (itu masalah terbuka yang terkenal). Namun, yang kita tahu adalah bahwa dugaan Collatz itu benar atau tidak. Dalam kasus sebelumnya, program print "yup it's true"ini adalah penentuan. Dalam kasus terakhir, program print "nope it's not true"ini adalah penentuan. Kami tidak tahu mana yang merupakan penentu yang valid, tetapi ini cukup untuk membuktikan bahwa penentu yang valid ada. Karena itu, masalahnya bisa diputuskan.