Apa yang kita ketahui tentang versi terbatas dari masalah penghentian

( PEMBARUAN : pertanyaan yang terbentuk lebih baik diajukan di sini karena komentar untuk jawaban yang diterima di bawah menunjukkan bahwa pertanyaan ini tidak didefinisikan dengan baik)

Bukti klasik ketidakmungkinan masalah berhenti tergantung pada menunjukkan kontradiksi ketika mencoba menerapkan algoritma deteksi berhenti untuk dirinya sendiri sebagai input. Lihat latar belakang di bawah ini untuk informasi lebih lanjut.

Kontradiksi yang diperlihatkan berlaku karena paradoks referensi-diri (seperti kalimat "Kalimat ini tidak benar"). Tetapi jika kita benar-benar melarang referensi-diri semacam itu (yaitu menerima kenyataan bahwa referensi-diri semacam itu tidak dapat dihentikan), hasil apa yang tersisa? Apakah masalah penghentian untuk set mesin non-referensi diri yang tersisa dapat dihentikan atau tidak?

Pertanyaannya adalah:

Jika kita mempertimbangkan subset dari semua mesin Turing yang mungkin, yang tidak merujuk sendiri (yaitu tidak menganggap dirinya sebagai input), apa yang kita ketahui tentang masalah penghentian untuk subset ini?

MEMPERBARUI

Mungkin rumusan ulang yang lebih baik tentang apa yang saya kejar adalah pemahaman yang lebih baik tentang apa yang menentukan seperangkat yang dapat ditentukan. Saya mencoba untuk mengisolasi bukti keraguan klasik karena tidak menambah informasi tentang keraguan kecuali untuk kasus-kasus di mana Anda menjalankan HALT dengan sendirinya.

Latar Belakang: Mengasumsikan adanya kontradiksi bahwa ada mesin Turing yang dapat memutuskan input yang merupakan pengkodean untuk mesin Turing dan , apakah berhenti atau tidak . Kemudian pertimbangkan mesin Turing yang mengambil dan dan menggunakan untuk memutuskan apakah berhenti atau tidak, dan kemudian melakukan yang sebaliknya, yaitu berhenti jika tidak berhenti, dan tidak berhenti jika $Q$ $M$ $X$ $M(X)$ $K$ $M$ $X$ $Q$ $M(X)$ $K$ $M(X)$ $M(X)$ berhenti. Kemudian menunjukkan kontradiksi, karena harus berhenti jika tidak berhenti, dan tidak berhenti ketika berhenti. $K(K)$ $K$

Motivasi: Seorang kolega sedang mengerjakan verifikasi formal sistem perangkat lunak (khususnya ketika sistem sudah terbukti pada tingkat kode sumber dan kami ingin menegurnya untuk versi yang dikompilasi, untuk menetralkan masalah penyusun), dan dalam kasus ini ia peduli tentang set khusus program kontrol tertanam yang kami tahu pasti tidak akan merujuk sendiri. Salah satu aspek verifikasi yang ingin dia lakukan adalah apakah dijamin program yang dikompilasi akan berhenti jika kode sumber input terbukti berakhir.

MEMPERBARUI

Berdasarkan komentar di bawah ini saya mengklarifikasi makna mesin Turing yang tidak merujuk pada diri sendiri.

Tujuannya adalah untuk mendefinisikannya sebagai himpunan yang tidak mengarah pada kontradiksi yang diajukan dalam bukti (lih. "Latar Belakang" di atas). Ini dapat didefinisikan sebagai berikut:

Dengan asumsi bahwa ada mesin Turing yang memutuskan masalah penghentian untuk satu set mesin Turing , maka adalah non-referensi diri sehubungan dengan jika tidak termasuk semua mesin yang memanggil pada (langsung atau tidak langsung). (Jelas itu berarti tidak bisa menjadi anggota ) $Q$ $S$ $S$ $Q$ $Q$ $S$ $Q$ $S$

Untuk mengklarifikasi tentang apa yang dimaksud dengan menerapkan pada secara tidak langsung: $Q$ $S$

Meminta pada dilambangkan dengan mesin Turing dengan sekumpulan status dan input awal tertentu yang mungkin pada pita (sesuai dengan setiap anggota ), dengan head awalnya di awal input tersebut. Mesin memanggil pada "secara tidak langsung" jika ada urutan langkah (terbatas) yang akan diambil untuk membuat konfigurasinya "homomorfik" dengan konfigurasi awal . $Q$ $S$ $Q$ $S$ $W$ $Q$ $S$ $W$ $Q(S)$

PEMBARUAN 2

Dari jawaban di bawah ini dengan alasan bahwa ada banyak mesin Turing yang melakukan tugas yang sama, dan jadi tidak unik, kami mengubah definisi di atas dengan mengatakan bahwa bukan mesin Turing tunggal, tetapi set (tak terbatas) dari semua mesin komputasi fungsi yang sama (HALT), di mana HALT adalah fungsi yang memutuskan apakah mesin Turing berhenti pada input tertentu. $Q$ $Q$

PEMBARUAN 3

Definisi Mesin Turing homomorfisme:

A TM A adalah homomorfik ke TM B jika grafik transisi A adalah homomorfik dengan B, dalam arti standar homomorfisme grafik dengan label berlabel DAN tepian. Grafik transisi (V, E) dari TM sedemikian rupa sehingga V = status, E = transisi busur antar negara. Setiap busur diberi label dengan (S, W, D), S = simbol membacakan rekaman dan W = simbol yang akan ditulis untuk itu, dan D = arah kepala menunjukkan pindah ke.

computability lo.logic M. Alaggan
sumber

"set non-referensi diri yang tersisa" Sebelum saya dapat dengan bijaksana membahas set ini, saya ingin definisi "referensi-diri". Namun, saya pikir itu akan sulit untuk didefinisikan?

Sam Nead

Ada studi tentang program penghentian yang terbukti (kelas ini tidak mencakup semua program penghentian,). Pada dasarnya mereka adalah sepasang program dan bukti bahwa itu berhenti. Misalnya, jika saya tidak salah, Agda hanya mengizinkan program yang berhenti. Saya pikir orang-orang yang bekerja dengan logika dan bahasa pemrograman memiliki lebih banyak bicara tentang ini.

Tsuyoshi Ito

@ M. Alaggan. Sekarang saya ingin definisi "memanggil

pada

secara tidak langsung," yang saya curigai sulit untuk didefinisikan sebagai "referensi-diri" asli :) :)

Q

$Q$

S

$S$

Rob Simmons

Ini menimbulkan pertanyaan yang menarik: Apakah semua bukti yang tidak dapat diperhitungkan (tidak dapat dipungkiri) dapat dilacak ke metode diagonalisasi Cantor? Apakah ada bukti keraguan yang tidak bergantung langsung atau tidak langsung pada metode diagonalisasi?

Mohammad Al-Turkistany

Pertanyaan yang mungkin terkait: adakah teori kompleksitas analog dengan teorema beras dalam teori komputabilitas? , MO: kelengkapan masalah tersulit yang paling sulit .

Kaveh

Jawaban:

Saya pikir itu akan membutuhkan sedikit lebih banyak pekerjaan untuk sampai ke pertanyaan yang "jelas". Secara khusus, ini bermasalah:

Meminta Q pada S dilambangkan dengan mesin Turing Q dengan sekumpulan status dan input awal tertentu yang mungkin pada pita (sesuai dengan setiap anggota S), dengan head awalnya di awal input tersebut. Mesin W memanggil Q pada S "secara tidak langsung" jika ada urutan langkah (terbatas) yang akan diambil W untuk membuat konfigurasinya "homomorfik" dengan konfigurasi awal Q (S).

Satu masalah adalah bahwa ada banyak mesin Turing tanpa batas yang menghitung fungsi yang sama. Dalam argumen diagonalisasi standar, saya bisa mengganti subrutin Q dengan penentu lain untuk HALT, karena ada banyak sekali dari mereka. Atau fungsi yang setara dengan HALT. Jadi tidak sepenuhnya jelas bagi saya bagaimana mendefinisikan gagasan Anda tentang "doa tidak langsung".

Sebuah pertanyaan yang berbeda mungkin: untuk set mesin Turing apa masalah terputusnya decidable? Di sini ada banyak jawaban: TM yang terbatas sumber daya (mis. Gunakan hanya ruang f (n), di mana f adalah beberapa fungsi yang dapat dihitung spesifik), TM yang secara operasional dibatasi dalam beberapa cara tertentu (mis. Head read hanya bergerak satu arah), dll Tapi, pertanyaan menarik lainnya adalah apakah keanggotaan dalam set terbatas itu dapat ditentukan, atau apakah Anda harus membatasi diri pada "janji masalah", di mana Anda hanya menjamin jawaban yang benar pada beberapa subset input yang "dijanjikan", tetapi jangan memverifikasi keanggotaan.

Tandai Reitblatt
sumber

Q

$Q$

H

$H$

Tidak sesederhana itu. Definisi Anda paradoks sekarang, karena Anda mencari HALT yang dapat dihitung. Tetapi jika ini dapat dihitung, setiap fungsi yang dapat dihitung setara dengan itu. Tetapi jika set input Anda mengandung masalah semi-komputer (TM), Anda akan memiliki kontradiksi karena memutuskan masalah penghentian untuk TM seperti itu akan memberi Anda prosedur keputusan untuk masalah itu.

Mark Reitblatt

1) Bukankah HALT yang tidak dapat diperhitungkan berarti keraguan? Saya mengasumsikan HALT yang dapat dihitung seperti itu ada, berharap kontradiksi. 2) Saya tidak akrab dengan konsep bahwa semua fungsi yang dapat dihitung setara satu sama lain, saya mengutip Anda, dan artinya adalah fungsi yang memecahkan masalah HALT. Rupanya λx.1 dapat dihitung tetapi tidak memutuskan HALT. Perbaiki saya jika saya salah. Tentang masalah semi-komputabel, HALT dapat mengambil langkah-langkah yang tak terbatas, yang masih tidak akan mengarah pada kontradiksi dalam bukti asli bahwa HALT tidak dapat ditentukan.

M. Alaggan

1) Benar. Tetapi masalahnya adalah mencoba untuk mendefinisikan gagasan Anda tentang "referensi-sendiri". Entah itu pembatasan yang lemah, yang memungkinkan diagonalisasi seperti yang saya katakan, atau itu adalah pembatasan kuat yang menghilangkan segalanya. 2) Sederhana. "Setara yang dapat dihitung" secara kasar berarti ada pemetaan yang dapat dihitung dari satu ke yang lain yang mempertahankan jawaban. Tetapi jika saya bisa menghitung jawaban, saya bisa menipu dan membuat pemetaan sepele. 3) Jika TM memutuskan HALT itu sendiri tidak berakhir, itu bukan penentu untuk HALT.

Tandai Reitblatt

Hal lain yang agak membingungkan adalah penggabungan TM dengan masalah keputusan yang dihitung oleh mereka. Tidaklah normal untuk berbicara tentang TM yang secara komputasi setara satu sama lain. Sebaliknya, fungsi yang dihitung oleh mereka dapat setara (atau sama). Masalahnya adalah bahwa mencoba mengatakan TM tidak mensimulasikan TM lain sulit untuk didefinisikan secara umum, tanpa memberikan sesuatu yang konkret untuk memisahkan fungsi yang dikomputasi oleh mereka. Misalnya, Log-space TM tidak dapat mensimulasikan TM memecahkan masalah EXP-space.

Mark Reitblatt

Jika saya memahami motivasi Anda dengan benar, sepertinya ini adalah masalah "kebenaran kompiler" lebih dari masalah "masalah berhenti terbatas". Anda memiliki properti (terminasi) bahwa Anda telah terbukti untuk beberapa program yang tingkat sumber Prog yang Anda inginkan untuk kemudian meluas ke kode dikompilasi untuk mendapatkan properti yang sama dari dikompilasi (Prog) . Tetapi kompiler dapat (secara umum) melakukan hal-hal konyol seperti menerapkan runtime turing-complete (katakanlah JVM), kompilasi program terminating Anda menjadi bytecode JVM dan kemudian buang executable yang menjalankan JVM dan berikan bytecode yang Anda kompilasi.

Dalam praktek mungkin sangat mungkin untuk menggunakan pengetahuan implisit yang Anda miliki tentang bagaimana kompiler Anda bekerja untuk mengimplementasikan beberapa prosedur verifikasi yang cukup banyak membuktikan program yang dikompilasi dengan benar mengingat program sumber yang benar (memang, banyak alat verifikasi otomatis untuk program menggunakan pengetahuan implisit dari algoritma-to-code "kompiler" di otak programmer). Namun, secara umum Anda mungkin melihat masalah ketepatan kompiler. Seperti yang saya pahami, ada dua cara klasik untuk melakukannya.

Salah satu opsi adalah memiliki kompiler yang digunakan sebagai input program Prog dan pembuktian berakhir (Prog) dan output dikompilasi (Prog) dan berakhir (dikompilasi (Prog)) - yang terakhir adalah bukti yang kemudian dapat diperiksa ulang secara independen dari kompiler. Makalah klasik tentang ini adalah Necula dan Lee . Desain dan implementasi kompiler sertifikasi , saya percaya.

Atau, Anda dapat membuktikan fakta tentang kompilasi fungsi () - bahwa setiap kali kompilasi () memberikan input terminating, ia menghasilkan output terminating. Pengantar yang dapat diakses tentang cara berpikir tentang kebenaran kompiler ini adalah artikel CACM Xavier Leroy, Verifikasi formal kompiler realistis .

(PS Saya harap jawaban ini membantu - saya tahu ini agak berbeda dari pertanyaan yang Anda ajukan, jadi beri tahu saya jika saya tidak sopan dan / atau mengulangi sesuatu yang sudah Anda ketahui.)

Rob Simmons
sumber

Terima kasih atas jawabannya. Ini jelas akan bermanfaat bagi rekan saya. Namun saya (secara independen dari kolega saya) lebih tertarik pada implikasi teoretis pada bukti masalah penghentian, bahwa jika kita menyingkirkan kasus yang menunjukkan kontradiksi, lalu apa lagi yang kita ketahui tentang kesesuaian masalah penghentian?

M. Alaggan