Sebuah Bukti Bahwa Ada Setidaknya Satu Program Komputer Sepele Yang Tidak Dapat Ada

Bukti Matematika Paling Indah, vol. 2, Maxime Coutte.

Artikel minggu lalu adalah tentang "Apakah Beberapa Infinitas Lebih Besar Dari Yang Lain?" Dan argumen Cantor Diagonal. Minggu ini saya ingin membagikan salah satu Masalah Ilmu Komputer Teoritis favorit saya.

Saya ingat kembali di sekolah menengah ketika saya mulai melakukan Ilmu Komputer, saya berpikir bahwa saya secara teoritis dapat menyelesaikan Masalah Komputasi dengan alat dan Pemrograman Matematika yang tepat. Saya salah. Ada batasan teoretis untuk Mesin Komputasi dan di sini kita akan melihat bukti bahwa setidaknya ada satu masalah logika yang tidak akan dapat dipecahkan oleh Program Komputer.

Mendefinisikan H, Program Komputer Yang Tidak Mungkin

Kami mendefinisikan Program Komputer P (i) sebagai daftar instruksi P yang ketika dieksekusi dengan input i, berikan output o.

Misalnya,

adalah program yang menjumlahkan dua angka yang Anda berikan sebagai input, dan,

adalah program yang menggunakan program lain - P_add - sebagai input, dan melewati program ini dua input lainnya. Ia melakukan apa yang dilakukan P_add (a, b) dan menggandakannya.

Ketika sebuah program dieksekusi, ia dapat macet, berjalan selamanya dan tidak pernah menghasilkan apa pun, misalnya, program P_sum yang melanjutkan ke jumlah semua bilangan alami akan terus menambahkan bilangan alami selamanya tanpa pernah selesai menjalankan (yaitu, berhenti) dan mengeluarkan hasilnya.

Sekarang misalkan ada program H (P, i) yang mengambil sebagai input daftar instruksi P dari program P (i) dan saya input dari P (i), dan menghasilkan 1 jika P (i) berhenti di beberapa titik dan 0 jika P (i) macet dan berjalan selamanya. Untuk membuatnya lebih sederhana,

Mengapa Daftar Instruksi Logika H Tidak Mungkin Ada

Berdasarkan bukti Alan Turing di koran "Pada angka yang dapat dihitung, dengan aplikasi ke Entscheidungsproblem" -1937, kami akan membuktikan bahwa H tidak ada.

Berdasarkan asumsi bahwa H ada, kami membuat program X (P) yang berjalan selamanya jika dan hanya jika H (P, P) = 1 dan berhenti jika dan hanya jika H (P, P) = 0. Dengan kata lain,

Kita sekarang dapat mempertimbangkan untuk memberikan X (i) daftar instruksi X sendiri sebagai input: X (X).

Karenanya X (X) berjalan selamanya jika dan hanya jika H (X, X) = 1 dan X (X) berhenti jika dan hanya jika H (X, X) = 0. Dengan kata lain,

Kami memiliki kontradiksi! Kami telah ditunjukkan oleh Reductio ad absurdum bahwa H tidak dapat ada karena keberadaannya mengarah pada kesimpulan yang absurd.

Oleh karena itu, Program Komputer yang dapat menentukan apakah Program Komputer yang diberi input apa pun akan macet dan berjalan selamanya atau selesai berjalan tidak mungkin. Setidaknya ada satu Program Komputer memecahkan masalah logika yang tidak mungkin ada.

Referensi, Alan Turing. "Pada angka yang dapat dihitung, dengan aplikasi ke Entscheidungsproblem". 1937.

Saya Maxime Coutte, Co-Founder of Relativty.com, headset VR yang saya desain dari awal, yang mana saya buka-bersumber kode dan perangkat keras. Saya suka belajar dan saya tertarik dengan beragam subjek.
Anda dapat saya ikuti saya di Twitter @maximecoutte.