Sebuah Bukti Bahwa Setidaknya Ada 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 Lainnya?" dan argumen Cantor Diagonal. Minggu ini saya ingin berbagi 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 bisa 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 dijalankan dengan input i, berikan output o.

Contohnya,

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, sebuah 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 Max Coutte, Co-Founder of Relativty.com, headset VR yang saya desain dari awal, yang saya gunakan dari sumber kode dan perangkat kerasnya. Ikuti saya di Twitter @maxcoutte.