Masalah Penghentian dan Ketidakterpecahan

Masalah penghentian, yaitu memutuskan apakah suatu program yang diberikan berhenti pada masukan tertentu, adalah contoh kanonis dari masalah yang secara algoritmik tidak dapat dipecahkan, dan reduksi dari masalah ini membuktikan ketidakterpecahan banyak masalah lainnya.

Definition

Suatu masalah keputusan tidak dapat dipecahkan jika tidak ada mesin Turing yang dapat memecahkannya dengan benar pada semua masukan; masalah penghentian menanyakan apakah suatu mesin arbitrer berhenti pada masukan arbitrer, dan ini adalah masalah prototipe yang tidak dapat dipecahkan dari mana masalah-masalah lain ditunjukkan tidak dapat dipecahkan melalui reduksi.

Scope

Topik ini mencakup pernyataan yang tepat mengenai masalah penghentian, bukti ketidakterpecahannya melalui diagonalisasi, teknik reduksi banyak-ke-satu untuk mentransfer ketidakterpecahan, teorema Rice tentang properti nontrivial program, dan masalah-masalah klasik yang tidak dapat dipecahkan seperti Entscheidungsproblem dan masalah kata untuk grup.

Core questions

• Mengapa tidak ada algoritma yang memutuskan apakah program berhenti?
• Bagaimana reduksi digunakan untuk membuktikan ketidakterpecahan suatu masalah dari masalah lain?
• Apa yang dikatakan teorema Rice tentang memutuskan properti program?
• Masalah matematika terkenal apa saja yang ternyata tidak dapat dipecahkan?

Key theories

Ketidakterpecahan masalah penghentian

Argumen diagonal menunjukkan bahwa mengasumsikan pemutus penghentian mengarah pada kontradiksi, sehingga tidak ada algoritma yang dapat memutuskan penghentian untuk semua program dan masukan.

Reduksi dan transfer ketidakterpecahan

Jika masalah yang diketahui tidak dapat dipecahkan direduksi menjadi masalah target, masalah target juga tidak dapat dipecahkan, menjadikan reduksi sebagai alat standar untuk menetapkan ketidakterpecahan.

Teorema Rice

Setiap properti nontrivial dari fungsi yang dihitung oleh suatu program tidak dapat dipecahkan, sehingga pada dasarnya tidak ada properti perilaku program yang menarik yang dapat diputuskan secara algoritmik.

Clinical relevance

Hasil ketidakterpecahan menetapkan batasan keras pada penalaran otomatis dan analisis program: hasil ini menunjukkan bahwa alat serbaguna yang sempurna untuk memverifikasi penghentian atau properti program tidak dapat ada, dan hasil ini menjelaskan mengapa banyak masalah dalam logika, aljabar, dan teori bilangan tidak memiliki solusi algoritmik.

History

Turing dan Church menunjukkan pada tahun 1936 bahwa Entscheidungsproblem, pertanyaan tentang algoritma yang memutuskan validitas orde pertama, tidak dapat dipecahkan, dengan masalah penghentian menjadi inti argumen Turing. Rice menggeneralisasi fenomena tersebut pada tahun 1953, dan ketidakterpecahan kemudian ditetapkan untuk masalah-masalah konkret seperti masalah kata untuk grup oleh Novikov dan masalah kesepuluh Hilbert oleh Matiyasevich.

Key figures

• Alan Turing
• Alonzo Church
• Henry Gordon Rice
• Pyotr Novikov

Seminal works

• sipser2013
• turing1936
• rogers1987

Frequently asked questions

Mengapa komputer yang lebih cepat tidak dapat memecahkan masalah penghentian?

Ketidakterpecahan tidak bergantung pada kecepatan atau memori: argumen diagonal menyingkirkan algoritma apa pun, tidak peduli berapa banyak waktu yang diberikan. Masalah penghentian pada prinsipnya tidak dapat dipecahkan, bukan hanya tidak praktis.

Bisakah kita mengetahui apakah suatu program berhenti?

Seringkali ya untuk program tertentu, melalui analisis atau dengan menjalankannya. Yang tidak mungkin adalah satu algoritma yang secara akurat menjawab pertanyaan untuk setiap program dan masukan. Oleh karena itu, pemeriksa penghentian praktis hanya berhasil pada kelas-kelas terbatas atau mungkin gagal memberikan jawaban.