Menghentikan Masalah tanpa referensi-diri: mengapa argumen ini tidak cukup (atau bukan)?

Saya mencoba untuk menemukan cara untuk menjelaskan ide bukti Masalah terputus dengan cara yang dapat diakses (untuk mahasiswa CS sarjana). Argumen paling sederhana yang saya temukan adalah argumen ini ; inilah gaya perawatan yang saya tuju. Namun, referensi-diri (khususnya, memeriksa apakah suatu program terhenti dengan sendirinya) bukanlah yang paling didaktik.

Apa yang saya pikirkan, sebagai sketsa bukti, adalah mengapa kami tidak dapat menyederhanakan lebih jauh lagi dan berkata: jika kita mengasumsikan program H(P,I)untuk Menghentikan Masalah yang berhenti dengan benar jika P(I)berhenti, dan berhenti dengan false jika tidak, maka kita dapat membuat program dari bentuk:

def Q(J):
  if H(Q,J) then loop forever
  else halt

... yang merupakan program yang valid jika dan hanya jika Halting Problem adalah program yang valid. Kita kemudian dapat bertanya: apa yang harus H(Q,J)mengembalikan nilai sewenang-wenang untuk apa J? Kami melihat kontradiksi di kedua kemungkinan, dan kami menyimpulkan bahwa karena keberadaan Hmemungkinkan kita untuk membangun program kontradiktif Q, maka program bentuk Htidak dapat ada.

Masih ada beberapa referensi diri di sini bahwa program Qmemeriksa apakah ia berhenti pada input saat ini (dan melakukan sebaliknya), tetapi bagi saya, ini tampaknya jauh lebih intuitif daripada mengatur situasi di mana kita memerlukan panggilan dari bentuk P(P)atau H(P,P), dll. Namun, saya belum melihat argumen yang lebih sederhana ini digunakan, dan saya pikir itu akan menjadi valid. Karena itu pertanyaan saya adalah:

• Apakah argumen di atas cukup sebagai bukti (sketsa) dari Masalah Putus?
  • Jika demikian, mengapa begitu banyak argumen berjalan dengan langkah membingungkan P(P)atau H(P,P)? (Apakah hanya untuk menghapus "input" yang tidak penting dari persamaan?)
  • Jika tidak, apa yang hilang?

Ada berbagai pertanyaan terkait tentang topik ini, seperti:

• Menghentikan masalah tanpa referensi sendiri
• Apakah ada bukti yang lebih intuitif tentang keraguan atas masalah penghentian daripada diagonalisasi?

Saya juga menemukan penyebutan bukti berdasarkan paradoks Berry, yang cukup menarik. Namun, saya belum berhasil meyakinkan diri saya apakah argumen spesifik di atas berfungsi (bahkan jika hanya untuk pemahaman saya sendiri; saya merasa saya mungkin kehilangan sesuatu yang bodoh dan ingin tahu apa itu).

Saya tidak berpikir ini adalah cara yang baik untuk menyajikan masalah penghentian, karena menyapu masalah kritis di bawah selimut dengan cara yang licik. Saya sarankan tetap menggunakan presentasi yang lebih standar, seperti yang Anda tautkan. Jika Anda ingin menemukan cara untuk menjelaskannya dengan cara yang meminimalkan konten teknis, presentasi dalam video ini secara mengejutkan dapat diakses, dan tetap setia pada logika pembuktian standar.

Ke kesulitan dengan proposal Anda. Dalam proposal Anda, tidak sepele untuk menuliskan kode untuk a Q. Pikirkan tentang apa artinya memiliki garis itu

  if H(Q,J) then loop forever 

Ingat bahwa argumen pertama Hadalah bit-string yang berisi kode / algoritma / mesin Turing - itu bukan penunjuk ke fungsi, tetapi string. Naif, ini sepertinya berarti bahwa kami menyertakan string hardcoded yang berisi kode sumber untuk Q, di dalam kode Q. Tapi itu tidak mungkin. Misalkan kode untuk Qmengambil 100 karakter. Maka kita perlu men-hardcode konstanta string 100-karakter di dalam definisi Q, ditambah kita juga membutuhkan beberapa karakter lebih untuk sisa logika - dan itu menambahkan hingga lebih dari 100 karakter. Jika Anda memikirkannya, jelas bahwa kita tidak dapat memiliki string konstan di dalam kode Qyang merupakan kode Q, karena itu akan terlalu lama.

Mungkin Anda berpikir bukan itu yang ada dalam pikiran. Mungkin Anda berpikir bahwa bahasa pemrograman akan memiliki beberapa API bawaan untuk mendapatkan kode fungsi saat ini, jadi sebenarnya kode yang Anda pikirkan adalah sesuatu seperti:

def Q(J):
  if H(get_source_code_of_current_function(),J) then loop forever
  else halt

Baiklah. Ini membuktikan bahwa masalah penghentian tidak dapat dipecahkan untuk kode yang ditulis dalam bahasa pemrograman apa pun yang memiliki get_source_code_of_current_function()API. Namun, bahasa pemrograman favorit saya tidak memiliki API seperti itu. Jadi, bukti ini tidak membuktikan apa-apa tentang bahasa pemrograman favorit saya - mungkin masalah penghentian dapat dipecahkan untuk bahasa saya, siapa tahu? Demikian pula, mesin Turing tidak memiliki API seperti itu, jadi ini tidak membuktikan bahwa masalah penghentian untuk mesin Turing tidak dapat ditentukan.

Dan itu adalah kelemahan utama dalam bukti Anda. Dan itu cacat yang halus dan sama sekali tidak jelas. Saya tidak berpikir itu ide yang baik secara pedagogis untuk menyajikan bukti bahwa "terlihat valid" di permukaan tetapi sebenarnya, setelah Anda menggali lebih dalam, cacat.

Sekarang, adalah mungkin untuk menyelamatkan bukti yang Anda usulkan. Ini sebenarnya adalah mungkin untuk membangun fungsi Qyang bekerja dengan cara Anda mengatakan; Anda pada dasarnya membutuhkannya untuk menjadi quine . Saya kira pada prinsipnya Anda bisa menjelaskan gagasan quines, lalu menyajikan bukti Anda dan menjelaskan bagaimana menerapkan fungsi Q menggunakan ide-ide itu. Tapi itu sepertinya ide yang buruk bagiku, dari sudut pandang pedagogis. Quines sangat membekas, misterius, dan sulit dipahami. Seorang siswa yang tidak mengerti quines tidak akan mengerti bukti Anda. Dan itu membuat bukti keraguan untuk masalah penghentian terlihat jauh lebih misterius daripada yang seharusnya. Jadi bagi saya ini sepertinya bukan cara yang lebih mudah diakses untuk memahami masalah yang terjadi.

Saya tidak melihat bagaimana referensi-diri itu sulit secara pedagogis. The Barber Paradox sangat mudah dimengerti. Dan argumen Anda memiliki referensi diri implisit, dan saya merasa lebih sulit untuk dipahami daripada referensi diri sederhana. Selain itu, itu tidak koheren. Untuk mendefinisikan H (Q, J), Anda harus terlebih dahulu tahu apa itu Q, dan untuk mendefinisikan Q, Anda harus terlebih dahulu tahu apa itu H (Q, J). Itu tidak berhasil. Paling-paling Anda dapat menyatakan bahwa Q adalah titik tetap dari definisi referensial diri ini, tetapi kemudian jika Anda mencoba untuk mendapatkan sesuatu dari sifat kontradiktif Q, Anda hanya menunjukkan H tidak ada ATAU tidak ada titik tetap seperti itu ada ; Anda sekarang harus membuktikan bahwa jika H memang ada, titik tetap harus ada.