Program sintesis, decidability dan masalah penghentian

Saya sedang membaca jawaban untuk pertanyaan baru-baru ini, dan semacam pemikiran fana yang aneh muncul di benak saya. Saya bertanya ini mungkin mengkhianati bahwa teori saya kurang serius (sebagian besar benar) atau terlalu dini bagi saya untuk membaca situs ini. Sekarang, dengan disclaimer keluar dari jalan ...

Ini adalah hasil yang terkenal itu teori komputasi bahwa masalah penghentian tidak dapat diputuskan untuk TM. Namun, ini tidak mengecualikan kemungkinan bahwa ada mesin yang dapat memecahkan masalah penghentian untuk kelas-kelas mesin tertentu (hanya tidak semuanya).

Pertimbangkan serangkaian semua masalah yang dapat diputuskan. Untuk setiap masalah, ada banyak TM yang menentukan bahasa itu. Mungkinkah yang berikut ini dimungkinkan

• Ada TM yang memutuskan masalah penghentian untuk subset dari mesin Turing; dan$S$
• Semua masalah yang dapat diputuskan diputuskan oleh setidaknya satu mesin Turing di ?$S$

Tentu saja, menemukan mesin Turing di mungkin tidak dapat dihitung sendiri; tapi kami mengabaikan masalah itu.$S$

EDIT: Berdasarkan jawaban Shaull di bawah ini, tampaknya salah satu (a) ide ini terlalu tidak jelas untuk menjadi bermakna atau (b) usaha saya sebelumnya tidak tepat sasaran. Seperti yang saya mencoba untuk menguraikan di komentar untuk jawaban Shaull ini, niat saya adalah tidak bahwa kita dijamin bahwa masukan TM adalah di . Apa yang saya maksudkan dengan pertanyaan saya adalah apakah ada huruf S , sehingga keanggotaan di huruf S adalah masalah yang dapat diperhitungkan . Program untuk memecahkan masalah penghentian untuk S , mungkin, menulis "input tidak valid" pada kaset atau sesuatu ketika diberi input yang diakui tidak dalam $S$$S$$S$$S$$S$. Ketika saya merumuskannya seperti itu, saya tidak yakin apakah ini memungkinkan kita untuk menyelesaikan masalah penghentian atau tidak, atau apakah teorema Rice berlaku (apakah kepantasan sebagai properti semantik dari sebuah bahasa dengan teorema Rice?)

Saya pikir mungkin ada masalah dengan rumusan masalah.

$S=\{M: M$$\}$$S$

$S$

$S$$S$$S\neq \emptyset$$S$$S$$S$