Apakah bukti keraguan terhadap Masalah Pemutusan curang dengan membalikkan hasil?

Saya kesulitan memahami masalah berhenti Turing.

Buktinya mengasumsikan bahwa ada mesin ajaib yang dapat menentukan apakah komputer akan berhenti atau berputar selamanya untuk input yang diberikan. Kemudian kami memasang mesin lain yang membalikkan output dan kami memiliki kontradiksi dan oleh karena itu H tidak bisa ada.$H$$H$

Kekhawatiran saya adalah sepertinya kita mengatakan jawaban salah karena kita membalikkannya. Sebagai analogi, jika ada mesin yang disebut sedemikian sehingga menghasilkan jawaban yang benar pada input tertentu dan jawaban yang salah pada yang lain. Kemudian kita lampirkan mesin lain yang membalikkan hasil A sehingga kombinasi kedua mesin memiliki kontradiksi dengan bagaimana A didefinisikan. Kedua mesin sekarang menghasilkan jawaban yang salah untuk input yang A didefinisikan untuk menghasilkan jawaban yang benar dan menghasilkan jawaban yang benar untuk input yang A didefinisikan untuk menghasilkan jawaban yang salah. Apakah ini disebut kontradiksi, dan karena itu tidak ada mesin yang mengeluarkan jawaban yang benar pada beberapa input dan jawaban yang salah pada yang lain?$A$$A$$A$$A$$A$

Versi singkat: Output dari mesin tidak benar atau salah, mereka hanya bertentangan, yang membuktikan bahwa mesin awal yang memutuskan apakah mesin input berhenti pada string yang diberikan atau tidak tidak dapat ada.

Versi panjang : Pertama kita akan membuat sketsa buktinya (atau setidaknya satu versi - ada banyak).

1. Asumsikan bahwa kita memiliki Turing Machine yang memutuskan apakah Turing Machine M perhentian pada input $\mathrm{HALT}(\langle M\rangle, x)$$M$$x$ atau tidak.
2. Menggunakan kita membangun sebuah mesin F L I P ( ⟨ M ⟩ , x ) yang menggunakan H A L T untuk memeriksa apakah M perhentian pada x atau tidak, kemudian melakukan sebaliknya, yaitu jika M perhentian pada x , F L I P loop, jika M tidak berhenti di x , F L I $\mathrm{HALT}$$\mathrm{FLIP}(\langle M\rangle, x)$$HALT$$M$$x$$M$$x$$\mathrm{FLIP}$$M$$x$$\mathrm{FLIP}$ berhenti.
3. Akhirnya kami membuat TM (Aku berlari keluar dari nama-nama yang baik), yang mengambil deskripsi TM dan berjalan F L I P dengan masukan ( ⟨ M ⟩ , ⟨ M ⟩ ) , keluaran apapun F L I Output $\mathrm{C}(\langle M \rangle)$$\mathrm{FLIP}$$(\langle M \rangle, \langle M \rangle)$$\mathrm{FLIP}$

Penting untuk dicatat bahwa selama penentu ada, masing-masing langkah ini mudah diterapkan; F L I P hanya harus menggunakan H A L T untuk memeriksa apa yang harus dilakukan, dan C hanya menggandakan inputnya untuk diteruskan ke F L I $\mathrm{HALT}$$\mathrm{FLIP}$$\mathrm{HALT}$$\mathrm{C}$$\mathrm{FLIP}$ .

Kontradiksi muncul ketika kita melihat apa yang terjadi ketika kita menjalankan . Entah C berhenti ketika diberikan sendiri sebagai input atau tidak. H A L T akan memutuskan ini:$\mathrm{C}(\langle\mathrm{C}\rangle)$$\mathrm{C}$$\mathrm{HALT}$

• Jika perhentian masukan ⟨ C ⟩ , H A L T akan mengatakan Y e s , tapi kemudian F L I P akan loop, sehingga C akan lingkaran, bertentangan H A L $\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{Yes}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$ .
• Jika loop pada input ⟨ C ⟩ , H A L T akan mengatakan N o , tapi kemudian F L I P akan menghentikan, sehingga C juga akan berhenti, bertentangan H A L T .$\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{No}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$

Karena setiap langkah dalam konstruksi jelas-jelas terdengar, kita hanya dapat menyimpulkan bahwa tidak dapat eksis; kami telah membangun sebuah kasus di mana tidak peduli apa yang dikatakannya, H A L T tidak mungkin memutuskan apa yang akan dihasilkan, yaitu masalahnya tidak dapat diputuskan. Hanya untuk benar-benar palu pada titik sedikit, H A L T tidak dapat ada - yaitu tidak mungkin ada TM yang memutuskan Masalah Henti - karena setidaknya ada satu kasus kami telah secara eksplisit dibangun di mana tidak ada secara logis jawaban yang mungkin. Ingatlah bahwa seorang penentu tidak diperbolehkan untuk mengeluarkan jawaban yang salah dan harus mengeluarkan sesuatu, tetapi dalam kasus yang kami buat, kedua kemungkinan jawaban itu salah.$\mathrm{HALT}$$\mathrm{HALT}$$\mathrm{HALT}$

Anda sedang mendiskusikan dua arti "kontradiksi" yang berbeda.

Dalam analogi Anda, mesin A dan modifikasi terbalik saling bertentangan hanya dalam arti bahwa output mereka selalu berbeda. (Misalnya, mereka mungkin menerapkan dua fungsi tes pada bilangan bulat, " x ≤ 5?" Dan " x > 5?") Itu tentu saja satu hal "bertentangan" dapat berarti dalam penggunaan sehari-hari, tetapi bukan itu yang dimaksud dengan logika. bukti.

Dalam bukti logis, itu berarti sesuatu yang lebih kuat: sesuatu yang tidak mungkin. Misalnya fungsi yang mengembalikan "true" pada semua input lebih dari 5, dan "false" pada semua input kurang dari 10 - itu bertentangan dengan pengertian yang lebih kuat ini, karena untuk, katakanlah, 7, outputnya harus "benar" dan "salah", tetapi itu tidak sama. Argumen Turing menunjukkan bahwa program penghentian itu bertentangan dalam arti yang lebih kuat: menganggapnya mengarah pada sesuatu yang tidak mungkin, atau sudah diketahui salah.

$x$$x$$f(n)$$n$

$f(m)$

$m$$m$

$m$$P_m$$f(m)+1$$P_m$$P_m$$m$$m$$|m|$$|m|$$m$$|m| \approx \log_{10} m$$T$$P_m$$T + \log_{10} m$$m$$m=2T$$T + \log_{10} m \leq m$$f(m)$$P_m$$f(m) \geq f(m) + 1$. Kami telah mencapai kontradiksi.