himpunan bagian dari set rekursif tak terbatas

Pertanyaan ujian baru-baru ini adalah sebagai berikut:

adalah himpunan enumerable rekursif tak terbatas. Buktikan bahwa memiliki subset rekursif tak terbatas. $A$ $A$

Biarkan menjadi bagian rekursif tak terbatas . Haruskah memiliki subset yang tidak dapat dihitung berulang secara rekursif? $C$ $A$ $C$

Saya sudah menjawab 1. Mengenai 2., saya menjawab dengan tegas dan berdebat sebagai berikut.

Misalkan semua himpunan bagian secara berulang dihitung. Karena tidak terbatas, set daya tidak terhitung, sehingga dengan asumsi akan ada banyak set enumerable berulang secara berulang. Tetapi set enumerable rekursif berada dalam korespondensi satu-ke-satu dengan mesin Turing yang mengenalinya, dan mesin Turing enumerable. Kontradiksi. Jadi harus memiliki subset yang tidak dapat dihitung secara rekursif. $C$ $C$ $C$ $C$

Apakah ini benar?

computability check-my-proof pengguna1435
sumber

Itu tidak sepenuhnya benar pada akhirnya, karena masing-masing set ulang disebutkan oleh banyak mesin Turing, tidak hanya oleh satu. Anda dapat mengatasi ini.

Carl Mummert

@Carl: Ah, benar, terima kasih - kesalahan konyol. Tapi yang saya butuhkan adalah suntikan ke TMs, bukan sebuah bujukan, kan? Dan pada definisi Turing-computable yang digunakan kelas saya, masing-masing TM dikaitkan dengan satu dan hanya satu fungsi. Set yang berbeda -> fungsi pengenalan yang berbeda -> TM berbeda yang menghitungnya.

user1435

! user1435: Anda membalikkan hal-hal di kalimat terakhir. Setiap mesin Turing menghitung satu fungsi, tetapi setiap fungsi yang dapat dihitung diperoleh dari banyak mesin Turing.

Carl Mummert

Tetapi jika fungsi saya memetakan {fungsi pengenalan r} ke {TMs} via f (r) = salah satu dari banyak TM yang tak terhitung jumlahnya yang menghitungnya, saya punya injeksi, kan? Atau saya kira saya bisa mempartisi {TMs} dengan hubungan ekivalensi ~ yang mengidentifikasi infinity TMs yang menghitung fungsi yang sama, dan kemudian memetakan r ke kelas ekivalensi yang sesuai.

user1435

Carl benar, mereka tidak berada dalam korespondensi satu-ke-satu, masing-masing set sesuai dengan banyak TM. Mempertimbangkan set objek lain seperti yang Anda lakukan dalam komentar Anda tidak mengubah apa pun, mereka bukan set TM.

Kaveh

Itu benar.

$\aleph_0\leq C \implies \aleph_0 < 2^C$

$C$

$D = \{ i \in C \mid i \notin W_i \}$ $W_i$ $i$ $D \subseteq C$ $D$ $C$ $K = \{ i \mid i\notin W_i\}$ $C$ $D$

Kaveh
sumber

"Setiap set tanpa batas memiliki subset yang tidak dapat ditentukan." Ini lebih lemah dari klaim yang saya coba buktikan. Saya mencoba membuktikan C harus memiliki subset non-RE, bukan subset non-decidable. Apakah klaim saya masih benar?

user1435

Iya. Istilah "undecidable" agak kelebihan beban (Wikipedia memiliki diskusi yang bagus ). Jadi jawaban ini mungkin berarti apa yang Anda coba buktikan.

David Lewis

@ user1435, ya, argumen yang sama berfungsi untuk semua kelas bahasa yang dapat dihitung, saya memperbarui pertanyaan untuk memperjelasnya.

Kaveh

himpunan bagian dari set rekursif tak terbatas

Jawaban: