Menghentikan masalah, set yang tidak dapat dihitung: bukti matematika umum?

29

Diketahui bahwa dengan seperangkat algoritma yang dapat dihitung (dicirikan oleh nomor Gödel), kita tidak dapat menghitung (membangun algoritma biner yang memeriksa kepemilikan) semua himpunan bagian dari N.

Sebuah bukti dapat diringkas sebagai: jika kita bisa, maka himpunan semua himpunan bagian N akan dihitung (kita dapat mengasosiasikan ke setiap subset jumlah Gödel dari algoritma yang menghitungnya). Karena ini salah, itu membuktikan hasilnya.

Ini adalah bukti yang saya suka karena menunjukkan bahwa masalahnya setara dengan himpunan bagian N yang tidak dapat dihitung.

Sekarang saya ingin membuktikan bahwa masalah penghentian tidak dapat dipecahkan hanya dengan menggunakan hasil yang sama ini (terhitung dari subset N), karena saya kira itu adalah masalah yang sangat dekat. Apakah mungkin membuktikannya dengan cara ini?

computability halting-problem Weier
sumber
Jelas kedua hasil tersebut dapat dibuktikan dengan menggunakan teknik yang sama (diagonalisasi). Namun, saya tidak berpikir bahwa adalah mungkin untuk membuktikan ketidakpastian dari masalah penghentian hanya dengan menggunakan tak terhitung dari keluarga subset dari ℕ, karena yang pertama adalah tentang perbandingan antara RE dan R , keduanya merupakan keluarga yang dapat dihitung dari himpunan bagian dari ℕ.
Tsuyoshi Ito
Hanya ada banyak program dengan akses ke oracle yang berhenti, sekali lagi ditandai dengan nomor Godel. Namun, masalah penghentian IS antara set yang dapat dihitung ini.
David Harris

Jawaban:

42

Teorem penghenti, teorema Cantor (non-isomorfisme suatu himpunan dan set kekuasaannya), dan teorema ketidaklengkapan Goedel adalah semua contoh teorema titik tetap Lawvere, yang mengatakan bahwa untuk setiap kategori tertutup kartesian, jika ada peta epimorfik maka setiap memiliki titik tetap.e:SEBUAH→(SEBUAH⇒B)f:B→B

Untuk pengantar yang bagus untuk ide-ide ini, lihat posting blog Andrej Bauer ini .

Neel Krishnaswami
sumber
7
itu cukup rapi. Saya tidak menyadari bahwa ada argumen formal yang sebenarnya menyatukan mereka.
Suresh Venkat
8
Saya telah belajar sekarang untuk mencurigai bahwa, jika kelihatannya sama dan baunya sama, ada argumen kategoris tentang arti di mana itu sama.
Vijay D
2
IMO, dua hal yang sangat baik tentang teorema Lawvere adalah bahwa (a) itu adalah pernyataan positif, bukan yang negatif, dan (b) buktinya adalah setengah lusin garis perhitungan kalkulus lambda sederhana.
Neel Krishnaswami
6
Ketika saya membaca pertanyaan itu, saya berpikir bahwa seseorang harus menyebutkan teorema titik tetap Lawvere. Bayangkan kegembiraan saya ketika saya membaca jawabannya :-)
Andrej Bauer
1
Menjadi epimorfik bukanlah kondisi yang tepat. Anda memerlukan titik-surjektivitas, yang tidak menyiratkan maupun tersirat oleh kondisi epimorfik. Lihat Catatan 2.3 ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem
fhyve