Masalah penghentian yang dibatasi dapat dipilih. Mengapa ini tidak bertentangan dengan teorema Rice?

Satu pernyataan teorema Rice diberikan pada halaman 35 dari "Kompleksitas Komputasi: Pendekatan Modern" (Arora-Barak):

Fungsi parsial dari $\{0,1\}^*$ hingga $\{0,1\}^*$ adalah fungsi yang tidak harus didefinisikan pada semua inputnya. Kita mengatakan bahwa TM $M$ menghitung fungsi parsial $f$ jika untuk setiap $x$ di mana $f$ didefinisikan, $M(x) = f(x)$ dan untuk setiap $x$ di mana $f$ tidak didefinisikan $M$ masuk ke loop tak terbatas ketika dieksekusi pada input $x$ . Jika $S$adalah satu set fungsi parsial, kita mendefinisikan $f_S$ menjadi fungsi boolean yang di masukan $\alpha$ output 1 IFF $M_\alpha$ Toedjoe menghitung fungsi parsial di $S$ . Teorema Rice mengatakan bahwa untuk setiap nontrivial $S$, fungsi $f_S$ tidak dapat dihitung.

Wikipedia menyatakan bahwa bahasa mesin turing waktu terbatas sudah EKSPTIM lengkap. Saya berharap bahasa ini terlihat seperti menerima x kurang dari n langkah } . Jadi biarkan M menjadi beberapa DTM yang memutuskan bahasa terikat ini dalam waktu eksponensial. Sepertinya DTM ini memutuskan beberapa properti untuk SEMUA mesin turing, jadi intuisi saya mengatakan bahwa teorema Rice menghalangi keputusan semacam itu. Tapi jelas M menghitung fungsi total.$\{(\alpha,x,n) : M_\alpha$$x$$n$$\}$$M$$M$

Apa yang saya lewatkan tentang hubungan antara bahasa ini dan teorema Rice?

Bahasa

$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$

bukan kumpulan indeks, itu bukan dari formulir

$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$

untuk beberapa set (parsial rekursif) fungsi , dengan fungsi (parsial) dihitung dengan TM . Teorema Rice membuat pernyataan hanya sekitar seperti ; banyak gambar ulang "intuitif" tidak membantu. Lihat juga di sini .f M M L $P$$f_M$$M$$L_P$

Perhatikan bahwa ini bukan hanya detail teknis di sini. Teorema Rice tidak berlaku untuk

$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$ ,

antara. Bisakah kamu melihat mengapa?

Untuk setiap mesin di Anda dapat dengan mudah membangun banyak mesin yang menerima bahasa yang sama tetapi berjalan selama lebih dari langkah, dan dengan demikian tidak dalam . Jadi, bukan kumpulan indeks.⟨ M ⟩ L $L$$\langle M \rangle$$L$$L$

$L$ adalah decidable, menggunakan argumen yang sama dengan bahasa asli yang kita diskusikan.

Teorema Padi mengatakan bahwa Anda tidak dapat memberi tahu apa pun tentang perilaku utama suatu program ketika dibiarkan berjalan hingga tak terbatas - tidak peduli bagaimana Anda mengklasifikasikan program, akan ada dua program yang akan menyatu dengan perilaku utama yang sama (fungsi yang dikomputasi) ) meskipun Anda mengklasifikasikannya secara berbeda.

Tetapi membiarkan program berjalan hingga tak terbatas sangat penting. Untuk mengetahui apa yang mereka lakukan di langkah pertama , Anda bisa mensimulasikannya untuk langkah pertama dan kemudian mengakhiri memberikan vonis Anda tentang bagaimana program berperilaku. Simulasi serupa hingga tak terbatas tidak berfungsi karena jika program simulasi tidak pernah berhenti pada input yang disimulasikan, classifier Anda akan berbeda juga, alih-alih memberikan klasifikasi.$n$$n$

Pertama, kata-kata dalam bahasa Anda bukan penyandian mesin, kata-kata itu mengandung lebih banyak informasi, sehingga Anda tidak dapat langsung menerapkan teorema Padi. Yang mengatakan, teorema Rice berbicara tentang ketidakmungkinan penalaran tentang fungsi yang dihitung oleh mesin Turing (yaitu, apakah itu terletak pada beberapa set ). Ini tidak terjadi di sini, karena seperti yang disebutkan Raphael, ada dua mesin yang menghitung fungsi yang sama, tetapi satu terletak pada bahasa Anda dan yang lainnya tidak (di sini saya mengabaikan masalah sintaksis, dan melupakan fakta bahwa adalah bagian dari input). Intinya adalah bahwa properti yang Anda lihat di sini adalah mekanis, dan bukan semantik (mesin dapat menghitung fungsi yang sama, tetapi dengan cara yang berbeda).M , M ′ x , $S$$M,M'$$x,n$

Teorema Rice mengatakan bahwa, untuk setiap set nontrivial bahasa, set mesin Turing yang mengenali bahasa dalam  tidak dapat diputuskan. Wikipedia mengatakan bahwa bahasa tertentu dapat dipilih. Jadi tidak ada kontradiksi.$\mathcal{L}$$\mathcal{L}$