masalah yang tidak dapat dipastikan dan negasinya tidak dapat ditentukan

Banyak masalah "terkenal" tidak dapat diputuskan setidaknya dapat diputuskan, dengan komplemen mereka tidak dapat diputuskan. Salah satu contoh di atas semua bisa menjadi masalah penghentian dan pelengkapnya.

Namun, adakah yang bisa memberi saya contoh di mana masalah dan komplemennya tidak dapat ditentukan dan tidak dapat ditentukan? Saya berpikir tentang bahasa diagonalisasi Ld, tetapi bagi saya kelihatannya komplemen tidak dapat diputuskan.

Dalam hal itu, apakah itu berarti bahwa Mesin Turing M dapat "kehilangan" beberapa string yang seharusnya dikenali, karena mereka adalah bagian dari bahasa yang kami coba identifikasi?

Pertimbangkan bahasa berikut:

$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

$L_2$ tidak dapat ditentukan dan tidak semi-decidable, dan hal yang sama berlaku untuk komplemennya. Mengapa? Intuisi adalah " tidak berhenti pada input " tidak semi-decidable, jadi tidak semi-decidable; dan ketika Anda melihat komplemen , hal yang sama terjadi pada . Ini dapat diformalkan lebih hati-hati menggunakan reduksi.$M_2$$x_2$$L_2$$L_2$$M_1$

Lebih umum, jika adalah bahasa yang tidak dapat diputus dan tidak semi-decidable, maka$L$

$$L' = \{(x,y) : x \in L, y \notin L\}$$

memenuhi persyaratan Anda: tidak dapat diputuskan dan tidak semi-decidable, dan hal yang sama berlaku untuk komplemen .$L'$$L'$

Perhatikan bahwa sebagian besar masalah sesuai dengan kriteria yang Anda cari: masalah dan pelengkapnya tidak semi-decidable. Ini karena hanya ada banyak masalah semi-decidable tetapi ada banyak masalah.

Sebagai contoh, biarkan menjadi masalah terputus-putus untuk mesin Turing dan membiarkan menjadi kelas mesin Turing dengan oracle untuk  . Biarkan menjadi masalah penghentian untuk  . Saya mengklaim bahwa baik maupun  semi-decidable$H$$\cal{M}$$H$$H_2$$\cal{M}$$H_2$$\overline{H_2}$

Kami dapat menunjukkan bahwa tidak diputuskan oleh mesin apa pun di  : argumennya sama dengan argumen bahwa mesin Turing biasa menghentikan masalah  tidak diputuskan oleh mesin Turing biasa. Sekarang, misalkan untuk kontradiksi yang  adalah semi-diputuskan oleh beberapa biasa mesin Turing  . Nah, dengan oracle untuk  , kita dapat menguji apakah  berhenti untuk input tertentu, bertentangan dengan kenyataan bahwa tidak ada mesin di  memutuskan  . Jadi  tidak semi-decidable.$H_2$$\cal{M}$$H$$H_2$$T$$H$$T$$\cal{M}$$H_2$$H_2$

Tetap menunjukkan bahwa tidak semi-decidable. Pertama, perhatikan bahwa itu semi-diputuskan oleh mesin di  : sekali lagi, argumennya sama dengan  sedang diputuskan oleh mesin Turing biasa.  tidak dapat setengah-diputuskan oleh beberapa mesin di  karena, jika ya, dan  keduanya akan diputuskan oleh mesin dalam  , jadi kedua bahasa akan ditentukan oleh mesin di  . Tapi kita sudah tahu bahwa  tidak ditentukan oleh mesin apa pun di  . Karenanya,$\overline{H_2}$$\cal{M}$$H$$\overline{H_2}$$\cal{M}$$H_2$$\overline{H_2}$$\cal{M}$$\cal{M}$$H_2$$\cal{M}$$\overline{H_2}$ tidak semi-diputuskan oleh mesin apa pun di  . Lebih lanjut, tidak semi-ditentukan oleh mesin Turing biasa, karena  berisi setiap mesin Turing biasa. (Mesin Turing biasa adalah mesin Turing dengan oracle untuk  yang tidak pernah menggunakan oracle itu.)$\cal{M}$$\overline{H_2}$$\cal{M}$$H$

Berikut ini beberapa contoh alami:

• Bahasa semua mesin Turing yang berhenti pada semua input, kadang-kadang dilambangkan dengan TOT. Bahasa ini adalah -lengkap.$\Pi_2^0$

• Bahasa semua mesin Turing yang berhenti pada input yang tak terhingga banyaknya , kadang-kadang dilambangkan dengan INF. Bahasa ini juga -lengkap.$\Pi_2^0$

• Bahasa semua mesin Turing yang berhenti pada input panjang yang sewenang-wenang , kadang-kadang dilambangkan dengan COF. Bahasa ini adalah -lengkap.$\Sigma_3^0$

dan Σ 0 3 adalah levelhirarki aritmatika. Hasil kelengkapan menyiratkan, khususnya, bahwa bahasa-bahasa ini tidak dapat ditentukan atau ditentukan bersama.$\Pi_2^0$$\Sigma_3^0$