Apakah meta-undecidability mungkin?

Ada masalah yang dapat diputuskan, ada beberapa yang tidak dapat diputuskan, ada yang dapat diputuskan, dll.

Dalam hal ini saya bertanya-tanya apakah masalah dapat menjadi meta-diputuskan. Ini berarti (setidaknya di kepala saya) kita tidak bisa mengatakan apakah itu dapat ditentukan atau tidak.

Mungkin diketahui bahwa decidability tidak dapat ditentukan (semuanya adalah meta-undecidable) dan tidak ada algoritma untuk membuktikan decidability untuk apa pun, sehingga decidability harus dibuktikan secara langsung berdasarkan kasus per kasus.

Mungkin pertanyaan saya tidak masuk akal. Mungkin saya berasumsi bahwa kita adalah mesin karbon yang menjalankan algoritma yang sangat kompleks dan itulah sebabnya pertanyaan itu masuk akal hanya di kepala saya.

Tolong beri tahu saya jika pertanyaan perlu klarifikasi lebih lanjut Saya mungkin membutuhkannya sendiri saat ini.

Terima kasih.

Berikut ini sketsa cepat untuk menunjukkan bahwa tidak ada mesin Turing untuk memutuskan apakah kelas masalah yang arbitrer dapat ditentukan.

Saya harus mengklarifikasi apa yang saya maksud dengan kelas masalah: kelas masalah $T$adalah mesin Turing yang menghitung elemen (bilangan alami, katakanlah) dari himpunan enumerable berulang satu demi satu, sehingga setiap elemen dalam himpunan akhirnya dicetak. Masalahnya secara intuitif ditangkap oleh$T(n)$ adalah: "adalah nomornya $n$ di set ini? ". Ini menangkap masalah yang biasa terjadi di bidang komputabilitas, seperti" apakah saya indeks mesin Turing yang berhenti pada input kosong? ".

Misalkan ada mesin $M$ yang, diberikan sebagai input kelas masalah $T$ dijawab $\mathit{true}$ jika kelas itu decidable dan $\mathit{false}$ jika tidak.

Sekarang ambil mesin Turing yang sewenang-wenang $T$. Kami membangun kelas masalah berikut$T'$ dengan cara berikut:

1. Simulasikan $T$.
2. Jika $T$ berhenti, sebutkan indeks mesin Turing yang berhenti pada input kosong.

Sekarang jelas kalau $T$ berhenti, lalu $M(T')$ kembali $\mathit{false}$, karena kumpulan indeks yang menghentikan mesin Turing bukanlah perangkat yang dapat ditentukan (rekursif).

Jika $T$tidak tidak menghentikan, maka$T'$tidak menyebutkan angka apa pun , yang membuatnya persis kelas masalah yang tidak mengandung indeks! Karena itu$M(T')$ jawaban $\mathit{true}$, karena kelas itu decidable (oleh mesin yang selalu menolak).

Karena itu, $M(T')$ kembali $\mathit{true}$ iff $T$ tidak berhenti, dan $\mathit{false}$jika tidak. Demikianlah keberadaan$M$ memungkinkan kita untuk memecahkan masalah penghentian untuk mesin sewenang-wenang $T$, yang merupakan kontradiksi.

Ide yang sangat keren!

Ide: Kita dapat mengeksploitasi aksioma pemahaman dalam teori himpunan ZF untuk mendefinisikan bahasa yang bergantung pada pernyataan independen.

Langkah 1: Ambil pernyataan favorit Anda yang tidak tergantung pada ZF seperti AC - aksioma pilihan.

Langkah 2: Tentukan bahasa L = {x dalam {0,1} | x = 0 jika AC dan x = 1 jika TIDAK AC}. Perhatikan bahwa L adalah {0} atau {1}. Sekarang, L dapat ditentukan, namun kami tidak dapat menyediakan dengan pasti suatu program yang memutuskan L. Kami dapat menyediakan program yang memutuskan {0} atau kami dapat menyediakan program yang memutuskan {1}, tetapi kami tidak tahu dengan pasti mana yang memutuskan L.

Langkah 3: Gunakan ide ini untuk menentukan bahasa yang dapat dipilih jika AC dan tidak dapat ditentukan jika TIDAK AC. Biarkan H menjadi set penghentian yang tidak dapat diputuskan. Tentukan L = {x | x adalah string jika AC dan x adalah dalam H jika TIDAK AC}. Jika AC, maka L = himpunan semua string dan L dapat dipilih. Jika BUKAN AC, maka L = H dan L tidak dapat ditentukan. Apakah L dapat ditentukan atau tidak, tidak tergantung pada ZF.