Apakah ada hubungan tersembunyi antara keberadaan perangkat yang tidak terhitung dan ketidakpastian masalah penghentian?

9

Karena kedua bukti menggunakan argumen diagonal, saya bertanya-tanya apakah ada hubungan yang tidak jelas antara keberadaan himpunan tak terbatas yang tak terhitung dan ketidakpastian masalah penghentian. Apakah masalah penghentian bisa ditentukan jika semua set dapat dihitung?

halting-problem Lenar Hoyt
sumber
10
Ya, argumen diagonal!
Mahdi Cheraghchi
1
@MCH Pemikiran saya adalah bahwa mungkin ada karakterisasi yang berbeda selain argumen diagonal yang menghubungkan keduanya. Pertanyaan ini mungkin terlalu buram untuk SE.
Lenar Hoyt
4
Ini mungkin sebagian tautan: jelas, himpunan semua bahasa di atas alfabet yang diberikan tidak dapat dihitung. Namun, himpunan semua mesin Turing dapat dihitung. Ini secara langsung menyiratkan adanya masalah yang tidak dapat ditentukan. Namun, alasan ini tidak menyiratkan apa pun tentang masalah penghentian.
042
9
Tentu saja ada model set-teori ZFC di mana semua set dapat dihitung (meskipun tidak dalam model), tetapi masalah penghentian selalu tidak dapat diputuskan. Lihat pertanyaan MathOverflow ini .
Peter Shor
4
Tolong, tolong katakan tidak dapat dipastikan mulai sekarang.
Vijay D

Jawaban:

14

Ini bukan tautan tersembunyi tetapi tautan yang dibuat eksplisit menggunakan bahasa teori kategori dan juga pertanyaan yang sangat wajar untuk ditanyakan dan dipelajari. Ada sedikit materi yang adil pada subjek.

Vijay D
sumber