Mengapa kita tidak bisa hanya menjalankan program untuk melihat apakah itu berhenti?

Menjalankannya hanya memberi tahu Anda bahwa itu berhenti jika memang demikian; jika akan berjalan selamanya, tidak ada penantian terbatas yang mengungkapkan hal itu. Masalah penghentian menuntut metode yang selalu memberikan jawaban yang benar dalam waktu terbatas untuk setiap program dan masukan, dan Turing membuktikan bahwa metode semacam itu tidak ada.

Apakah ketidakterpecahan membuat analisis program menjadi tanpa harapan?

Tidak, tetapi ini menjelaskan mengapa analisis yang sempurna tidak mungkin. Alat mengatasinya dengan bersikap konservatif, menandai apa pun yang tidak dapat mereka buktikan aman, dengan menangani kelas program terbatas secara tepat, atau dengan memecahkan banyak kasus praktis sambil mengakui bahwa mereka mungkin gagal pada kasus yang merugikan atau patologis.

Ketidakterpecahan dan Masalah Penghentian

Masalah penghentian menanyakan apakah suatu program tertentu pada akhirnya berhenti pada masukan tertentu, dan bukti Turing bahwa tidak ada algoritma yang dapat menjawab ini untuk semua kasus adalah contoh dasar dari masalah yang tidak terpecahkan.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Masalah keputusan tidak dapat dipecahkan ketika tidak ada algoritma yang dapat menjawabnya dengan benar untuk setiap masukan; masalah penghentian, yang memutuskan apakah suatu program arbitrer berhenti pada masukan arbitrer, adalah masalah kanonik yang tidak dapat dipecahkan, yang dibuktikan demikian oleh argumen diagonal yang mereferensikan diri sendiri.

Scope

Topik ini mencakup argumen diagonalisasi yang menetapkan ketidakterpecahan masalah penghentian, perbedaan antara masalah yang dapat dipecahkan (decidable), dapat dikenali (recognizable), dan dapat dikenali bersama (co-recognizable), teorema Rice yang menunjukkan bahwa semua properti semantik program yang tidak trivial tidak dapat dipecahkan, dan katalog masalah tidak terpecahkan alami di seluruh logika, matematika, dan ilmu komputer.

Core questions

Mengapa tidak ada satu algoritma pun yang dapat memutuskan apakah setiap program berhenti?
Apa perbedaan antara masalah yang dapat dipecahkan dan hanya dapat dikenali?
Mengapa pada dasarnya semua properti menarik dari perilaku program tidak dapat dipecahkan?
Bagaimana ketidakterpecahan menyebar dari masalah penghentian ke masalah lain?

Key theories

Ketidakterpecahan masalah penghentian: Mengasumsikan algoritma yang memutuskan penghentian mengarah pada kontradiksi melalui program yang berhenti tepat ketika diprediksi tidak akan berhenti, sehingga algoritma semacam itu tidak dapat ada.
Teorema Rice: Setiap properti nontrivial dari fungsi yang dihitung oleh suatu program — apa pun yang berlaku untuk beberapa program dan gagal untuk yang lain berdasarkan perilaku — tidak dapat dipecahkan, menggeneralisasi hasil penghentian ke semua properti semantik.

Clinical relevance

Karena penghentian dan, menurut teorema Rice, semua properti perilaku program yang tidak trivial tidak dapat dipecahkan, tidak ada alat yang dapat secara sempurna mendeteksi perulangan tak terbatas, memverifikasi kebenaran arbitrer, atau menganalisis sepenuhnya setiap program; oleh karena itu, penganalisis statis dan verifikator harus melakukan perkiraan, menerima alarm palsu, atau membatasi cakupannya.

History

Turing menetapkan ketidakterpecahan masalah penghentian dan masalah keputusan untuk logika pada tahun 1936 menggunakan argumen diagonal yang terinspirasi oleh Cantor dan Gödel. Rice membuktikan generalisasi menyeluruhnya pada tahun 1953, dan selama dekade-dekade berikutnya banyak masalah alami, termasuk masalah kesepuluh Hilbert tentang persamaan Diophantine, terbukti tidak dapat dipecahkan.

Key figures

Alan Turing
Henry Gordon Rice
Emil Post
Alonzo Church

Seminal works

turing1937
sipser2013

Frequently asked questions

Mengapa kita tidak bisa hanya menjalankan program untuk melihat apakah itu berhenti?: Menjalankannya hanya memberi tahu Anda bahwa itu berhenti jika memang demikian; jika akan berjalan selamanya, tidak ada penantian terbatas yang mengungkapkan hal itu. Masalah penghentian menuntut metode yang selalu memberikan jawaban yang benar dalam waktu terbatas untuk setiap program dan masukan, dan Turing membuktikan bahwa metode semacam itu tidak ada.
Apakah ketidakterpecahan membuat analisis program menjadi tanpa harapan?: Tidak, tetapi ini menjelaskan mengapa analisis yang sempurna tidak mungkin. Alat mengatasinya dengan bersikap konservatif, menandai apa pun yang tidak dapat mereka buktikan aman, dengan menangani kelas program terbatas secara tepat, atau dengan memecahkan banyak kasus praktis sambil mengakui bahwa mereka mungkin gagal pada kasus yang merugikan atau patologis.