Apakah ada bukti keraguan tentang masalah penghentian yang tidak bergantung pada referensi-diri atau diagonalisasi?

40

Ini adalah pertanyaan yang terkait dengan yang ini . Menempatkannya kembali dalam bentuk yang lebih sederhana setelah banyak diskusi di sana, yang rasanya seperti pertanyaan yang sama sekali berbeda.

Bukti klasik dari ketidakpastian masalah penghentian tergantung pada menunjukkan kontradiksi ketika mencoba menerapkan penentu HALT hipotetis untuk dirinya sendiri. Saya pikir ini hanya menunjukkan ketidakmungkinan memiliki penentu HALT yang memutuskan apakah itu sendiri akan berhenti atau tidak, tetapi tidak memberikan informasi lebih dari itu tentang kepantasan menghentikan kasus lain .

Jadi pertanyaannya adalah

Apakah ada bukti bahwa masalah penghentian tidak dapat diputuskan yang tidak bergantung pada menunjukkan bahwa HALT tidak dapat memutuskan sendiri, juga tidak bergantung pada argumen diagonalisasi?

Suntingan kecil: Saya akan berkomitmen pada ungkapan asli dari pertanyaan, yang meminta bukti yang sama sekali tidak bergantung pada diagonisasi (daripada hanya mengharuskannya untuk tidak bergantung pada diagonalisasi yang bergantung pada HALT).

M. Alaggan
sumber
Apakah Anda mencari yang tidak bergantung pada argumen diagonalisasi, atau hanya argumen yang tidak mendiagonalisasi dengan menggunakan HALT secara langsung? Saya tidak yakin apakah bukti yang diajukan Bjørn memuaskan yang pertama.
Mark Reitblatt
@ Mark: Saya sebenarnya tidak yakin. Jika argumen diagonalisasi tidak sesuai dengan referensi-diri, tetapi untuk aspek lain seperti kardinalitas tidak cocok, maka saya memang berharap itu akan memberikan beberapa wawasan tentang mengapa penghentian HALT (Q) (di mana Q! = HALT) tidak dapat diputuskan .
M. Alaggan
1
Nah, dalam hal ini, saya bisa memberikan argumen yang lebih sederhana. Mulailah dengan pengamatan bahwa ada masalah yang tidak dapat dipastikan (argumen kardinalitas sederhana), dan terlebih lagi bahwa ada masalah yang tidak dapat dipastikan P yang memiliki TM M yang mengenali anggotanya (tetapi mungkin tidak berakhir pada yang bukan anggota). Sekarang, menyelesaikan HALT (M) memberi Anda penentu untuk P. Kami pertama kali memeriksa apakah M berhenti di x. Jika ya, kita jalankan dan kembalikan sama dengan M. Kalau tidak, kita tolak, karena M berhenti pada setiap anggota P. Ini sekarang merupakan kontradiksi karena kami berasumsi bahwa P adalah bahasa tanpa penentu.
Mark Reitblatt
Argumen itu sebenarnya adalah bukti bahwa HALT adalah RE-complete.
Mark Reitblatt
1
Kena kau. Jika semua TM adalah penentu, maka HALT adalah sepele. Jika berhenti adalah non-sepele (pengenal ada), maka (dengan kontra-positif) keberadaan HALT non-sepele membuat penentu TMs penentu, yang berarti HALT adalah sepele, kontradiksi. Jadi HALT semacam itu tidak bisa ada untuk semua pengenal. Ini brilian, terima kasih atas komentar Anda yang luar biasa; Anda mungkin ingin mempostingnya kembali sebagai jawaban :)
M. Alaggan

Jawaban:

31

Ya, ada bukti seperti itu dalam teori komputabilitas (alias teori rekursi).

Anda pertama dapat menunjukkan bahwa penghentian masalah (set ) dapat digunakan untuk menghitung satu set G N yang 1-generik makna yang dalam arti masing-masing Σ 0 1 fakta tentang G ditentukan oleh awalan terbatas G . Maka mudah untuk membuktikan bahwa himpunan G seperti itu tidak dapat dihitung (yaitu, decidable).0GNΣ10GGG

Kita dapat mengganti 1- generik di sini dengan 1-acak, yaitu, Martin-Löf acak , untuk efek yang sama. Ini menggunakan Teorema Dasar Rendah Jockusch-Soare .

(Peringatan: orang mungkin menganggap hanya menunjukkan bahwa menghitung Chaitin Ω , yang merupakan 1-acak, tetapi di sini kita harus berhati-hati tentang apakah bukti bahwa Ω adalah 1-acak bergantung pada masalah penghentian yang tidak dapat diputuskan! Oleh karena itu lebih aman untuk cukup gunakan Teorema Dasar Rendah).0ΩΩ

Bjørn Kjos-Hanssen
sumber
Sangat menarik! Bisakah Anda memberi saya referensi atau serangkaian kata kunci untuk dicari agar dapat lebih memahaminya? Terima kasih banyak!
M. Alaggan
6
@ M. Alaggan: Referensi terbaik mungkin adalah buku terbaru dari André Nies, Computability and Randomness , Oxford Logic Guides, Oxford University Press, 2009. Ada juga artikel Wikipedia tentang Teorema Dasar Rendah dan artikel Scholarpedia tentang Algoritma Acak keakuratan
Bjørn Kjos-Hanssen
@ M. Alaggan, Terserah Anda tetapi suara menyarankan bahwa ini harus menjadi jawaban yang diterima.
Mohammad Al-Turkistany
Saya memang bertanya pada meta (periksa meta.cstheory.stackexchange.com/questions/642/when-is-it-app-to-change-the-accepted-answer). Saya tahu jawaban ini memang hebat dan sangat berguna juga. Namun saya menerima yang lain, karena jauh lebih mudah bagi saya untuk memahami dengan pendekatan yang lebih intuitif. Namun, tampaknya ada diskusi di atas tentang kebenarannya (!). Jadi jika ternyata tidak benar saya akan mengubah jawaban ini. Kebingungan muncul dari saya yang tidak spesifik dalam pertanyaan awal yang saya ingin hindari diagonalisasi menggunakan HALT, daripada semua diagonalisasi.
M. Alaggan
Saya sangat bingung yang mana yang harus saya terima, sampai saat ini, karena saya memilih antara jawaban yang luar biasa dan jawaban yang mudah / intuitif (latar belakang saya tidak terlalu solid / dewasa). Jadi, tolong jangan ada perasaan sulit :) Kita bisa membahasnya dan mencapai keputusan yang memuaskan untuk semua. Terima kasih.
M. Alaggan
5

Diposting ulang dari komentar saya sesuai permintaan:

Mulailah dengan pengamatan bahwa ada masalah yang tidak dapat dipastikan (argumen kardinalitas sederhana), dan terlebih lagi bahwa ada masalah yang tidak dapat dipastikan P yang memiliki TM M yang mengenali anggotanya (tetapi mungkin tidak berakhir pada yang bukan anggota). Sekarang, menyelesaikan HALT (M) memberi Anda penentu untuk P. Kami pertama kali memeriksa apakah M berhenti di x. Jika ya, kita jalankan dan kembalikan sama dengan M. Kalau tidak, kita tolak, karena M berhenti pada setiap anggota P. Ini sekarang merupakan kontradiksi karena kami menganggap P tidak dapat ditentukan.

Catatan: Dia mengklarifikasi bahwa dia sedang mencari argumen yang menghindari diagonalisasi menggunakan HALT secara langsung, bukan argumen yang sepenuhnya menghindari diagonisasi.

EDIT: Argumen ini macet. Dapatkah Anda menunjukkan secara langsung bahwa RE - REC tidak kosong, selain untuk menunjukkan bahwa HALT ada di sana?

Tandai Reitblatt
sumber
Argumen countability menggunakan diagonalisasi yang sangat mirip (hanya sedikit lebih sederhana) daripada bukti standar untuk masalah penghentian. (Yaitu, untuk menunjukkan bahwa kardinalitas bahasa lebih besar daripada TM menggunakan diagonalisasi.) :)
Joshua Grochow
@ Yosua Baca komentarnya. Saya bertanya apakah dia mencari bukti yang menghindari diagonalisasi, atau bukti yang hanya menghindari diagonalisasi menggunakan HALT. Dia mencari yang terakhir.
Mark Reitblatt
@ Mark: Ah, saya melewatkan itu. Terima kasih. +1
Joshua Grochow
4
@ Mark: Bisakah Anda mengklarifikasi sesuatu? Anda mulai dengan mengatakan bahwa ada masalah yang tidak dapat diputuskan P yang dapat dikenali, dan kemudian amati bahwa jika HALT dapat ditentukan, maka kita dapat membuat penentu untuk P. Namun, dalam teks yang telah saya baca, semuanya dibuktikan dalam urutan lain-- ketidakpastian HALT digunakan untuk menunjukkan keberadaan masalah tersebut P. Dapatkah Anda menunjukkan adanya masalah yang belum dapat diputuskan namun dapat dikenali tanpa menggunakan ketidakpastian HALT?
Kurt
2
Fakta bahwa ada masalah yang dapat dikenali tetapi tidak dapat dipastikan mungkin paling mudah dibuktikan dengan menunjukkan masalah yang berhenti adalah masalah seperti itu, dalam hal ini Anda kembali ke tempat Anda memulai. Hanya ada banyak bahasa yang dapat dikenali.
Bjørn Kjos-Hanssen
2

Poster lain menyinggung ini (dengan merujuk pada Chaitin), tetapi Anda dapat menggunakan paradoks Berry untuk membuktikan bahwa masalah penghentian tidak dapat diputuskan. Berikut ini sketsa buktinya:

Biarkan HALT menjadi mesin yang memutuskan jika ada mesin M yang berhenti pada input I. Kami akan menunjukkan bahwa HALT sendiri gagal menghentikan input tertentu, yang menunjukkan bahwa ia tidak dapat memutuskan bahasa.

Pertimbangkan fungsi berikut f:

f (M, n) = a, di mana a adalah bilangan bulat positif terkecil yang tidak dapat dihitung oleh mesin M pada input I apa pun dengan | I | <n

Dengan asumsi bahwa HALT adalah fungsi yang dapat dihitung, f juga merupakan fungsi yang dapat dihitung; cukup mensimulasikan HALT (M, I) untuk setiap mesin M dan input string I dengan panjang I kurang dari n. Jika simulasi berhenti, maka simulasikan M (I) dan catat apa outputnya, dan temukan output terkecil yang tidak dihasilkan oleh pasangan M, n.

Sekarang, kami menunjukkan bahwa f tidak dapat dihitung: pertimbangkan f (f, 10000000 * | f | +10000000). Apa pun outputnya, itu harus bilangan bulat (positif) yang tidak dapat dihitung oleh mesin yang menghitung f pada input I dengan panjang kurang dari yang diberikan ... namun kami baru saja mengeluarkan bilangan bulat seperti itu dengan f dan lebih singkat. memasukkan.

Jadi, f tidak dapat dihitung, dan asumsi kami bahwa HALT dapat dihitung adalah salah. Saya tidak percaya bukti ini menggunakan diagonalisasi.

Philip White
sumber
Whatever it outputs, it ought to be an integer that is not computable by the machine computing f on input I with length less than that given.>nn
5
Saya tidak berusaha bersikap kasar, tetapi keberatan Anda tidak masuk akal. Fungsi f didefinisikan sebagai fungsi yang menghasilkan bilangan bulat yang tidak dapat dihitung oleh M pada input apa pun dengan panjang kurang dari n. Dengan demikian, mengesampingkan banding ke aritmatika modular samping, Anda akan mengalami kesulitan menunjukkan bahwa kalimat yang Anda sorot tidak valid.
Philip White
@ Johnny aku setuju dengan Philip. Tidak ada asumsi tentang batas-batas representasi mesin. Ini adalah TM.
Mark Reitblatt
@Philip Koreksi teknis minor: Anda harus mengubah bilangan bulat ke bilangan bulat alami atau positif.
Mark Reitblatt
1
ff
0

{We}e=1feWe=Wf(e)0fe0We0eWe(0)Wf(e)(0)


sumber
6
Ini adalah bukti diagonalisasi standar.
Yuval Filmus