Apakah Memutuskan Decidability Decidable?

13

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.

sinkronkan
sumber
7
Yo, dawg, aku mendengarmu suka decidability jadi ...
David Richerby
Pertanyaan Anda tidak dapat dijawab dalam bentuk saat ini, seperti yang ditunjukkan oleh dua jawaban yang pada dasarnya mengatakan, "Sepele, tidak" dan "Sepele, ya" (dengan komentar bonus mengatakan "tidak" ke "tidak"). Anda telah bertanya apakah suatu masalah dapat ditentukan tetapi Anda belum menentukan apa masalahnya. Secara khusus, apa inputnya? Jika Anda ingin merancang sebuah mesin Turing yang akan memberitahu Anda apakah masalah adalah decidable, Anda harus memberikan masalah itu sebagai masukan untuk M . Tetapi bagaimana Anda melakukannya? M.M.
David Richerby
3
Diberikan jawaban saat ini, ada pertanyaan "Apakah Memutuskan Memutuskan Keputusan Dimenangkan Diputuskan?", Tapi saya tidak akan menanyakannya :-)
Mark Hurd

Jawaban:

10

Pengeditan utama dokumen asli saya:

Pembacaan yang naif terhadap pertanyaan Anda tampaknya, misalkan adalah masalahnyaP

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 sebagaiL(M.)M.P

Mengingat deskripsi,M dari TM sebuah, M adalah L ( M ) decidable?P=M.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.PPP

{M.M. adalah TM dan L(M.) decidable}
Rick Decker
sumber
1
Terima kasih! Memahami, setidaknya secara dangkal, kedua jawaban memberi saya informasi yang saya cari, yaitu sekitar: "Bisakah kita membuat mesin yang bisa memutuskan apa yang bisa dan tidak bisa memutuskan secara umum?" (Saya tahu, tidak bisa menggunakan frase yang baik, tapi saya tidak bisa memikirkan ungkapan yang lebih baik.) Sangat membantu, terutama karena Anda mengakui kedua interpretasi itu.
sinkronisasi
Saya pikir menunjukkan bahwa untuk setiap masalah yang dapat diputuskan ada sertifikat (algoritma dengan bukti) dan untuk setiap masalah yang tidak dapat ditentukan ada juga sertifikat (pengurangan dari masalah yang tidak dapat ditentukan) sudah cukup.
rus9384
9

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 : NN iff (untuk semua m , n N ) f ( m ) = n F ( m _ , n _ ) benar, di mana m _ adalah bilangan mewakili angka m .ΨF(m,n)f:NNm,nNf(m)=n F(m_,n_)m_m

Saya mengutip:

ΦNNff

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

Φ

Hendrik Jan
sumber
4

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.

DW
sumber
1
Saya pikir interpretasi Ricky Decker tentang pertanyaan lebih unggul. Diberikan beberapa penyandian masalah, putuskan apakah masalah itu dapat ditentukan.
Yuval Filmus
1
@YuvalFilmus, oke, itu masuk akal. Apakah Anda memiliki penyandian terbatas untuk masalah (yaitu, bahasa) yang menurut Anda masuk akal, dan tidak membuat masalah sepele? Pengodean hingga alami untuk bahasa adalah sebagai mesin Turing yang mengenali bahasa itu, tetapi itu membuat masalah itu sepele, seperti yang diilustrasikan oleh komentar Anda pada jawaban Ricky Decker. Jadi kita perlu beberapa pengkodean yang masuk akal lainnya, yang tidak menderita masalah seperti ini. Apakah Anda punya saran untuk itu?
DW
Anda dapat menggunakan logika tingkat pertama dalam beberapa bahasa yang sesuai. Atau input bisa berupa mesin dalam 0 '(misalnya), yaitu mesin Turing dengan akses ke oracle yang terputus-putus.
Yuval Filmus
Dengan teorema Rice, kita tahu bahwa menentukan R di alam semesta RE tidak dapat diputuskan. Bukankah itu cukup? (Tidak semua TM adalah penentu.)
Raphael
Terima kasih! Walaupun, bukan interpretasi yang saya maksudkan, ini membantu saya melihat mengapa pertanyaan yang saya ajukan mungkin tidak cukup baik untuk mencerminkan niat saya.
sinkronisasi