Masalah keputusan dan bahasa hanyalah dua sisi dari mata uang yang sama: setiap masalah dapat diulang sebagai masalah keanggotaan beberapa bahasa. Masalah, katakanlah, menentukan apakah suatu bilangan prima adalah tepatnya masalah keanggotaan bahasa bilangan prima.
Secara formal, suatu bahasa adalah serangkaian string terbatas hingga beberapa alfabet terbatas tetap (kadang-kadang string diperbolehkan menjadi tak terbatas; itu skenario yang berbeda tetapi terkait). Masalah yang tidak secara langsung pertanyaan tentang string perlu dikodekan sebagai string sehingga, misalnya, akan lebih tepat untuk menulis kalimat terakhir dari paragraf sebelumnya sebagai, "Jika kita memperbaiki alfabet dan pengkodean bilangan alami sebagai string di atas alfabet itu, masalah, katakanlah, menentukan apakah suatu bilangan prima adalah masalah keanggotaan dari bahasa string yang menyandikan bilangan prima. "
Untuk menjalankan subquestions Anda dengan cepat,
Kita tahu bahwa himpunan semua bahasa tidak terhitung. Apakah serangkaian masalah juga tidak terhitung?
Ya, karena masalah dan bahasa pada dasarnya adalah hal yang sama.
Bisakah setiap masalah didefinisikan oleh suatu bahasa?
Masalah keputusan, ya. Masalah optimisasi (apa X terkecil dengan properti Y) dan menghitung masalah (berapa banyak X yang memiliki properti Y) dapat diulang sebagai masalah keputusan (apakah Z adalah X terkecil dengan properti Y?; Apakah ada NX dengan properti Y?), Meskipun itu biasanya bukan cara paling alami untuk merawat mereka.
Bisakah bahasa memecahkan lebih dari satu masalah dan sebaliknya?
Ya dan ya, karena Anda harus menggunakan penyandian untuk menerjemahkan antara masalah dan bahasa. Misalnya, bahasa dan keduanya menyandikan masalah primality (dalam biner dan desimal, masing-masing). Sebaliknya, meskipun mungkin sedikit secara artifisial, bahasa mengkodekan masalah menentukan apakah angka biner berbentuk untuk beberapa dan masalah penentuan apakah string 1 dan 0 memiliki tepat satu 0, yang merupakan karakter terakhirnya. (Mungkin seseorang dapat memberikan contoh bahasa yang lebih baik yang secara alami menyandikan dua masalah tanpa satu menjadi pengulangan sepele yang lain.){ 10 , 11 , 101 , 111 , 1011 , … }{ 2 , 3 , 5 , 7 , 11 , ... }{ 0 , 10 , 110 , 1110 , ... }2k- 2k
Apakah ada korespondensi satu-ke-satu antara masalah dan bahasa?
Tidak, karena pertanyaan ini hanya pelengkap dari yang sebelumnya. :-)
