Pertanyaan yang diberi tag ?undecidability?

Pertanyaan tentang masalah yang tidak dapat diselesaikan oleh mesin Turing.




2
Bingung dengan teorema Rice
Ringkasan: Menurut teorema Rice, semuanya tidak mungkin. Namun, saya melakukan hal - hal yang dianggap mustahil sepanjang waktu! Tentu saja, teorema Rice tidak hanya mengatakan "semuanya tidak mungkin". Itu mengatakan sesuatu yang lebih spesifik: "Setiap properti dari program komputer tidak dapat dikomputasi." (Jika Anda ingin membagi rambut, setiap properti "non-sepele". …

1
Teorema Rice untuk properti non-semantik
Teorema Rice memberi tahu kita bahwa satu-satunya sifat semantik dari Mesin Turing (yaitu sifat fungsi yang dihitung oleh mesin) yang dapat kita putuskan adalah dua sifat sepele (yaitu selalu benar dan selalu salah). Tetapi ada sifat-sifat lain dari Mesin Turing yang tidak dapat memutuskan. Misalnya, properti yang ada keadaan tidak …

7
Apakah ada bukti yang lebih intuitif tentang keraguan atas masalah penghentian daripada diagonalisasi?
Saya memahami bukti ketidaktentuan masalah penghentian (diberikan misalnya dalam buku teks Papadimitriou), berdasarkan diagonalisasi. Sementara buktinya meyakinkan (saya mengerti setiap langkahnya), itu tidak intuitif bagi saya dalam arti bahwa saya tidak melihat bagaimana seseorang akan mendapatkannya, mulai dari masalahnya sendiri. Dalam buku ini, buktinya seperti ini: "misalkan memecahkan masalah penghentian …

2
Adakah masalah khusus yang diketahui tidak dapat dipastikan karena alasan selain diagonalisasi, referensi-diri, atau reducibilitas?
Setiap masalah yang tidak dapat dipastikan yang saya ketahui termasuk dalam salah satu kategori berikut: Masalah yang tidak dapat dipastikan karena diagonalisasi (referensi diri tidak langsung). Masalah-masalah ini, seperti masalah penghentian, tidak dapat diputuskan karena Anda dapat menggunakan penentu yang konon untuk bahasa untuk membangun TM yang perilakunya mengarah pada …


4
Apakah bahasa yang tidak dapat ditentukan ada dalam logika konstruktivis?
Logika konstruktivis adalah sistem yang menghilangkan Hukum Tengah yang Dikecualikan, serta Negasi Ganda, sebagai aksioma. Ini dijelaskan di Wikipedia di sini dan di sini . Secara khusus, sistem tidak memungkinkan pembuktian dengan kontradiksi. Saya bertanya-tanya, apakah ada yang akrab dengan bagaimana ini mempengaruhi hasil mengenai Mesin Turing dan bahasa formal? …

1
Apa sistem tipe terkuat yang diketahui yang kesimpulannya dapat ditentukan?
Sudah diketahui bahwa inferensi tipe Hindley-Milner ( -kalkulus yang diketik sederhana dengan polimorfisme) memiliki inferensi tipe yang dapat decidable: Anda dapat merekonstruksi tipe prinsip untuk program apa pun tanpa anotasi apa pun.λλ\lambda Menambahkan typeclasses bergaya Haskell tampaknya mempertahankan decidability ini, tetapi penambahan lebih lanjut membuat kesimpulan tanpa anotasi tidak dapat …


1
Rasio masalah yang dapat diputuskan
Pertimbangkan masalah keputusan yang dinyatakan dalam beberapa bahasa formal yang "masuk akal". Katakanlah rumus dalam aritmetika Peano tingkat tinggi dengan satu variabel bebas sebagai kerangka acuan, tapi saya sama-sama tertarik pada model perhitungan lain: persamaan Diophantine, masalah kata dari aturan penulisan ulang menggunakan mesin Turing, dll. Jawaban dinyatakan dalam setiap …


5
Apakah mungkin untuk menyelesaikan masalah penghentian jika Anda memiliki input yang terbatas atau dapat diprediksi?
Masalah penghentian tidak dapat diselesaikan dalam kasus umum. Dimungkinkan untuk membuat aturan yang ditetapkan yang membatasi input yang diizinkan dan dapatkah masalah penghentian diselesaikan untuk kasus khusus itu? Misalnya, sepertinya bahasa yang tidak memungkinkan loop misalnya, akan sangat mudah untuk mengetahui apakah program akan berhenti atau tidak. Masalah yang saya …

1
Ekspresi reguler dengan referensi kembali di atas alfabet unary
Pengaturan: ekspresi reguler dengan referensi kembali bahasa unary (alfabet 1 simbol) Apakah masalah berikut ini dapat ditentukan dalam pengaturan ini: Diberi ekspresi reguler dengan referensi, apakah itu mendefinisikan bahasa biasa? Misalnya, (aa+)\1mendefinisikan bahasa reguler, sementara (aa+)\1+tidak. Bisakah kita memutuskan yang mana masalahnya? Untuk konkret, "ekspresi reguler dengan referensi-kembali" di sini …

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.
Judi bola