Jika Anda memiliki bahasa L, tanpa melakukan bukti apa pun, adakah cara untuk mengetahui apakah itu dapat dikenali atau dikenali bersama atau dapat dipilih?

Pada dasarnya ada petunjuk atau trik yang bisa digunakan untuk menceritakannya. Atau mungkin pola umum untuk mencari tahu jenis apa itu?

L dikenali

Bahasa dapat dikenali jika dan hanya jika ada verifier untuk , di mana verifier adalah mesin Turing yang berhenti pada semua input dan untuk semua , . Umumnya, dianggap sebagai "sertifikat" atau "bukti" yang$L$$L$$w \in \Sigma^*$$w \in L \leftrightarrow \exists c \in \Sigma^*. V\text{ accepts }\langle w, c\rangle$$c$$w$ adalah di$L$ dan verifikasi $V$ memeriksa apakah $c$ adalah bukti valid dari $w$ berada di $L$. (Perhatikan bahwa definisi ini setara dengan definisi pengenal karena kita dapat membuat pengenal untuk suatu bahasa dari sebuah verifier untuk bahasa itu). Sekarang untuk menentukan apakah suatu bahasa dalam RE atau tidak kita dapat mengajukan pertanyaan berikut:

Diberi string $w \in L$, Bisa Anda membuktikan bahwa$w \in L$?

Sebagai contoh, pertimbangkan $HALT = \{\langle M, w\rangle\ |\ M\text{ is a TM that halts on }w\}$. $HALT$ dikenali karena untuk membuktikan kepada Anda itu $M$ berhenti $w$, Saya hanya bisa memberi tahu Anda jumlah langkah yang harus Anda jalankan $M$ untuk dan jika $M$ tidak berhenti setelah banyak langkah, Anda akan yakin itu $\langle M, w\rangle \in HALT$.

L bisa dikenali bersama

Demikian pula bahasa $L$ dikenali bersama jika dan hanya jika komplemennya dikenali, atau dengan kata lain jika ada verifier untuk $\overline{L}$. Jadi untuk melihat apakah suatu bahasa dalam co-RE, kita dapat bertanya:

Diberi string $w \not\in L$, Bisa Anda membuktikan bahwa$w \not\in L$?

Mengambil kembali contoh $HALT$, kita bisa menggunakan intuisi ini untuk menunjukkan itu $HALT$tidak dikenali bersama. Ini karena jika saya katakan itu mesin$M$ tidak berhenti pada input $w$, sebenarnya tidak ada yang bisa saya katakan untuk meyakinkan Anda tentang fakta itu. Saya bisa lari$M$ di $w$ tetapi bahkan jika kita sudah menonton $M$ lari dan belum melihatnya berhenti, kita tidak tahu bahwa itu tidak akan berhenti dan kapan-kapan di masa depan.

L adalah decidable

Akhirnya, sebuah bahasa $L$ decidable jika keduanya $L$ dan $\overline{L}$dikenali. Jadi jika jawaban untuk kedua pertanyaan di atas adalah ya, maka bahasanya dapat dipilih.

Sebagai contoh, pertimbangkan $L = \{a^nb^n\ |\ n \in \mathbb{N}\}$. Diberi string$w \in L$, bisakah saya membuktikan kepada Anda bahwa $w \in L$? Tentu, saya bisa menghitung jumlahnya$a$dan jumlah $b$dan menunjukkan bahwa mereka setara, jadi $L$dikenali. Bagaimana kalau$w \not\in L$? Saya dapat membuktikan bahwa sebuah string tidak ada$L$ dengan menunjukkan bahwa itu bukan dari formulir $a^nb^m$ atau bahwa ada ketidakcocokan dalam jumlah $a$dan $b$s. Jadi,$L$dikenali bersama. Karena keduanya dikenali dan dikenali bersama,$L$ juga decidable.

Referensi: Saya seorang TA untuk kelas teori komputabilitas / kompleksitas intro di universitas saya dan profesor saya membuat panduan animasi yang sangat membantu ini untuk alasan tentang bahasa yang teratur, dapat dipercaya, dan dapat dikenali.

Ide utama

Menjadi dikenali berarti Anda dapat membangun proses otomatis (kami akan kembali lagi nanti) yang menggunakan kata sebagai parameter

• Jika proses otomatis berakhir, ia mengembalikan YA atau TIDAK.
• Proses otomatis ini tidak harus berakhir pada setiap input, tetapi harus berakhir jika kata input dalam bahasa.

Mengenali bersama berarti bahasa ${w\in \Sigma^*, w\not\in L}$ (atau, dalam bahasa Inggris, himpunan semua kata yang tidak ada $L$, yaitu komplementernya) dapat dikenali.

Menjadi decidable berarti Anda dapat membangun proses otomatis yang menggunakan kata sebagai input, seperti itu

• Proses otomatis selalu berakhir
• Itu menjawab YA atau TIDAK. Jika itu menjawab YA, kata itu dalam bahasa, jika itu menjawab TIDAK, kata itu tidak dalam bahasa.

Satu hasil penting adalah itu $L$ dapat ditentukan jika dan hanya jika $L$ dikenali dan dikenali bersama.

Gagasan untuk membuktikan hasil ini, adalah bahwa Anda dapat membangun proses otomatis dari proses yang dapat dikenali dan dikenali bersama Anda, dengan bergantian langkah dari kedua proses, hingga salah satu dari itu memberi Anda jawaban YA. Salah satu dari mereka harus melakukannya, karena setiap kata dalam atau tidak dalam bahasa)

Proses otomatis

Tanpa terlalu formal, banyak jenis mesin telah dirancang, dan pada dasarnya semuanya telah dikaitkan dengan jenis bahasa (tipe-tipe itu bergantung pada alat yang diperlukan untuk mendefinisikan bahasa tersebut. Untuk informasi lebih lanjut, Hierarki Chomsky dapat membantu).

Arti biasa dari proses otomatis, sehubungan dengan decidability, adalah Mesin Turing. Anda dapat mendefinisikan Mesin Turing sedemikian rupa sehingga dapat:

• Terima nilai dari input
• Simpan nilai
• Baca nilai yang disimpannya
• Hitung operasi matematika dasar pada nilai-nilai
• Tes properti matematika dasar pada nilai-nilai itu, dan bertindak sesuai, akhirnya berulang.

Pada dasarnya, Mesin Turing dapat melakukan semua yang Anda bisa mendefinisikan dalam suatu program, kecuali itu adalah objek matematika, dengan memori tak terbatas dan waktu untuk dihabiskan pada perhitungan. Itu tidak selalu berakhir.

Properti penting lainnya dari Mesin Turing, adalah Anda dapat menggambarkan mesin Turing sebagai satu kata (ini adalah encoding), dan ada mesin Turing yang, diberikan sebagai input pengkodean mesin $M$, dan sebuah kata $w$, dapat mensimulasikan perhitungan $M$ pada input $w$. Ini akan menjadi penting dalam sedikit.

Mari kita tunjukkan bahwa bahasa biasa - yang (hampir) merupakan jenis bahasa paling sederhana yang dapat Anda pikirkan dari sudut pandang matematika - memiliki sifat khusus yang ditutup dengan pelengkap. Ini pada dasarnya berarti bahwa pada bahasa-bahasa tersebut, pengertian tentang dapat diakui dan decidability adalah setara. Ini tidak berlaku ketika Anda naik di Chomsky Hierarchy.

Contoh bahasa yang tidak dapat ditentukan

Kami akan mempelajari masalah Hentikan . Pertanyaannya adalah, bisakah kita membangun Mesin Turing itu, mengingat penyandian Mesin Turing lain$M$ dan sebuah kata $w$, memutuskan apakah$M$ berakhir pada input $w$ ?

Jelas, ini dapat dikenali , karena kita hanya perlu mensimulasikan$M$ di $w$sampai itu berakhir, dan ketika itu terjadi, katakan YA. Namun, jika$M$tidak pernah berakhir, kami tidak akan mengatakan TIDAK, jadi kami mengenali bahasa ini, tetapi tidak memutuskannya. Telah terbukti bahwa bahasa ini tidak dapat diputuskan oleh Mesin Turing. Ini melibatkan skema matematika yang biasa: argumen diagonal, yang tidak saya sebut intuitif. Anda dapat memeriksa sketsa bukti ini untuk membiasakan diri dengannya.

Untuk menyimpulkan

Anda tidak akan bisa, diberi bahasa, untuk hanya menyatakan apakah itu decidable atau tidak. Tidak ada algoritma yang dapat melakukan itu, dan membuktikan bahwa suatu bahasa tidak dapat diputuskan membutuhkan pemikiran, dan dapat memerlukan beberapa pengetahuan tentang Mesin Turing, argumen Diagonal, dll ...

Namun, inilah cara pribadi saya menangani pertanyaan ini. Biasanya, ketika mempelajari suatu bahasa, saya menganggap itu dapat dipilih, kecuali jika itu menunjukkan beberapa bentuk referensi tentang cara kerja Mesin Turing. Dalam hal ini, saya mulai waspada, dan mencoba mendefinisikan algoritma yang menentukan bahasa. Jika ini tidak terlihat mudah, kadang-kadang membantu untuk membagi pekerjaan baik dalam algoritme mengenali, maupun mengenali bersama. Jika saya masih tidak bisa melakukannya, saya akan mencoba untuk membuat hubungan antara bahasa ini, dan yang lain yang tidak dapat ditentukan, seperti "Jika saya dapat memutuskan bahasa itu, saya dapat memutuskan masalah penghentian". Ini adalah pengurangan Turing ke masalah yang tidak dapat diputuskan, sehingga masalah pertama tidak dapat diputuskan. Jika semua itu gagal, saya bisa mencoba menggunakan argumen diagonal, tetapi ini bisa sedikit rumit.

Salah satu triknya adalah jika bahasa tersebut terbatas, maka Anda tahu pasti bahwa itu dapat dipilih - karena Anda dapat "meng-hardcode" mesin untuk menerima apa pun dalam bahasa itu. Namun saya menemukan cara termudah adalah dengan hanya mengurangi dari bahasa lain

Seperti yang saya sebutkan di komentar saya di atas, saya merasa terbantu untuk memikirkan ruang solusi dari masalah tersebut.

Pikirkan sesuatu seperti $SAT$. Kita tahu bahwa itu dapat ditentukan, karena untuk mengujinya ada sejumlah solusi terbatas yang harus kita coba. Jika ada beberapa kondisi yang terbatas untuk diperiksa, di mana salah satu dari ini berhasil menjamin ya, dan tidak ada dari mereka yang berhasil menjamin tidak, maka masalahnya dapat diputuskan, karena kami hanya memeriksa kondisi secara berurutan. Perhatikan bahwa rangkaian kondisi ini bisa sangat besar (seperti dalam kasus masalah NP-complete).

Pertimbangkan sekarang ketika ruang solusi tak terhingga tak terbatas, dan kami dapat menghasilkan setiap solusi yang mungkin secara berurutan, dan menguji setiap solusi dapat ditentukan. Dalam hal ini kita tahu bahwa masalahnya dapat dikenali. Misalnya, masalah menanyakan "apakah ada bilangan asli sehingga ..." dapat dikenali, karena kita dapat mulai dari 0, dan terus mencoba setiap angka secara berurutan. Jika ada solusi, kami dijamin akan menemukannya, tetapi belum tentu ada batas waktu yang diperlukan untuk menemukannya. Juga, algoritma ini tidak akan pernah berhenti jika tidak ada bilangan bulat seperti itu, jadi itu tidak membuktikan bahwa masalah dapat diputuskan.

Anda dapat menerapkan teknik yang sama untuk set semua string, semua integer, semua grafik, atau struktur hingga apa pun yang dapat kami sebutkan. Ini tidak akan berhasil untuk menemukan bilangan real, atau serangkaian string (mungkin tak terbatas).

Namun perlu dicatat, bahwa beberapa masalah mungkin memiliki ruang solusi yang tak terhingga jumlahnya dan masih dapat ditentukan.

Trik untuk melihat apakah suatu bahasa tidak dapat diputuskan adalah dengan bertanya pada diri sendiri pertanyaan "dapatkah saya membuat kode perhitungan mesin Turing menggunakan bahasa ini"? Atau lebih umum, "apakah itu menjadi serumit apa yang terjadi dalam perhitungan?". Tentu saja terkadang pengkodean ini sulit, dan ini membantu untuk mengetahui daftar masalah yang tidak dapat diputuskan untuk dikurangi menjadi (seperti masalah Post korespondensi). Jika Anda tidak menemukan pengurangan seperti itu, coba pikirkan algoritma untuk memutuskan bahasa Anda. Misalnya bahasa daftar bilangan bulat dalam meningkatkan pesanan tidak terbatas, tetapi mudah untuk merancang pengujian algoritma apakah daftar diurutkan dalam peningkatan pesanan, sehingga bahasa ini dapat dipilih. Dan untuk banyak bahasa, kita tidak tahu tentang kepantasannya, jadi ini pertanyaan yang sulit.