Masalah penghentian
Masalah Halting adalah masalah dalam ilmu komputer. Masalahnya adalah melihat sebuah program komputer dan mencari tahu apakah program tersebut akan berjalan selamanya atau tidak. Kita mengatakan bahwa sebuah program "memecahkan masalah halting" jika program tersebut dapat melihat program lain dan mengetahui apakah program lain itu akan berjalan selamanya atau tidak.
Contohnya, program seperti ini:
sementara Benar: lanjutkan;akan berputar selamanya, tetapi program
sementara False: lanjutkan;berhenti dengan sangat cepat.
Apakah ada program yang memecahkan masalah halting? Ternyata tidak ada. Kita buktikan fakta ini dengan menunjukkan bahwa jika ada program yang memecahkan masalah halting maka sesuatu yang mustahil terjadi. Jadi, untuk saat ini kita akan bertindak seolah-olah benar-benar ada program yang memecahkan masalah halting. Di sini, P adalah sebuah fungsi yang akan mengevaluasi fungsi F (dipanggil dengan argumen I) dan mengembalikan nilai benar jika berjalan selamanya dan salah jika tidak.
def P(F, I): if F(I) berjalan selamanya: return True; else: return False;P dapat melihat program apapun dan mencari tahu apakah program itu akan berjalan selamanya atau tidak. Kita menggunakan P untuk membuat program baru yang akan kita sebut Q. Apa yang dilakukan Q adalah melihat program lain dan kemudian menjawab pertanyaan berikut: "Jika kita menjalankan program ini dan membuatnya melihat salinan dari program itu sendiri, apakah program itu akan berjalan selamanya?". Kita bisa membuat Q karena kita memiliki P. Yang perlu kita lakukan adalah memerintahkan Q untuk membuat program baru yang merupakan program lama yang melihat dirinya sendiri, dan kemudian menggunakan P untuk mengetahui apakah program baru itu berjalan selamanya atau tidak.
def Q(F): mengembalikan P(F, F);Sekarang kita membuat program lain R. R melihat program lain dan menanyakan jawaban Q tentang program itu. Jika Q menjawab "ya, jika kita menjalankan program ini dan membuatnya melihat salinan dari dirinya sendiri, program ini akan berjalan selamanya", maka R berhenti. Jika Q menjawab "tidak, jika kita menjalankan program ini dan membuatnya melihat salinan dari dirinya sendiri, maka program ini tidak akan berjalan selamanya", maka R memasuki perulangan tak hingga dan berjalan selamanya.
def R(F): if Q(F): return; //terminate else: while True: continue; //loop foreverSekarang kita lihat apa yang terjadi jika kita membuat R melihat salinan dari dirinya sendiri. Dua hal yang bisa terjadi: ia akan berhenti atau berjalan selamanya.
Jika menjalankan R dan membuatnya melihat salinan dirinya sendiri tidak berjalan selamanya, maka Q menjawab "ya, jika kita menjalankan program ini dan membuatnya melihat salinan dirinya sendiri maka akan berjalan selamanya". Tetapi Q mengatakan ini ketika melihat R itu sendiri. Jadi apa yang sebenarnya Q katakan adalah: "ya, jika kita menjalankan R dan membuatnya melihat salinan dari dirinya sendiri maka akan berjalan selamanya". Jadi: Jika R yang berjalan pada salinan dirinya sendiri tidak berjalan selamanya, maka R akan berjalan selamanya. Ini mustahil.
Jika menjalankan R dan membuatnya melihat salinan dirinya sendiri berjalan selamanya, maka Q menjawab "tidak, jika kita menjalankan program ini dan membuatnya melihat salinan dirinya sendiri, program ini tidak akan berjalan selamanya". Tetapi Q mengatakan ini ketika melihat R itu sendiri. Jadi apa yang sebenarnya Q katakan adalah: "tidak, jika kita menjalankan R dan membuatnya melihat salinan dari dirinya sendiri maka tidak akan berjalan selamanya". Jadi: Jika R yang berjalan pada salinan dirinya sendiri berjalan selamanya, maka R tidak berjalan selamanya. Ini juga mustahil.
Tidak peduli apa yang terjadi, kita mendapatkan situasi yang mustahil. Kita melakukan sesuatu yang salah, dan kita perlu mencari tahu apa itu. Sebagian besar hal yang kita lakukan tidak salah. Kita tidak bisa mengatakan "membuat program melihat salinan dirinya sendiri adalah salah", atau "melihat apa yang dikatakan program lain dan kemudian masuk ke dalam loop jika program itu mengatakan satu hal, dan berhenti jika program itu mengatakan hal lain" adalah salah. Tidak masuk akal untuk mengatakan bahwa kita tidak diperbolehkan melakukan hal-hal tersebut. Satu-satunya hal yang kita lakukan yang kelihatannya salah adalah bahwa kita berpura-pura bahwa program seperti P itu ada sejak awal. Dan karena ini adalah satu-satunya hal yang bisa salah, dan sesuatu pasti salah, maka inilah dia. Inilah bukti bahwa program seperti P tidak ada. Tidak ada program yang memecahkan masalah halting.
Bukti ini ditemukan oleh Alan Turing pada tahun 1936.
Pertanyaan dan Jawaban
T: Apa yang dimaksud dengan masalah Halting?
J: Masalah Halting adalah masalah dalam ilmu komputer yang melihat sebuah program komputer dan menentukan apakah program tersebut akan berjalan selamanya atau tidak.
T: Bagaimana kita tahu jika sebuah program memecahkan masalah halting?
J: Kita mengatakan bahwa sebuah program "memecahkan masalah penghentian" jika program tersebut dapat melihat program lain dan mengetahui apakah program tersebut akan berjalan selamanya atau tidak.
T: Apakah ada cara untuk membuktikan bahwa tidak ada program seperti itu?
A: Ya, dengan menunjukkan bahwa jika ada program seperti itu maka sesuatu yang mustahil akan terjadi. Bukti ini ditemukan oleh Alan Turing pada tahun 1936.
T: Apa yang dilakukan oleh P?
J: P adalah sebuah fungsi yang mengevaluasi fungsi lain F (yang disebut dengan argumen I) dan mengembalikan nilai benar jika fungsi tersebut berjalan selamanya dan salah jika tidak.
T: Apa yang dilakukan Q?
J: Q melihat program lain dan kemudian menjawab pertanyaan apakah menjalankan program yang sama dengan sendirinya akan menghasilkan perulangan yang tak terbatas atau tidak. Hal ini dilakukan dengan menggunakan P untuk melakukan evaluasi terhadap fungsi F yang diberikan.
T: Apa yang dilakukan oleh R?
J: R melihat program lain dan meminta jawaban dari Q untuk program tersebut. Jika Q menjawab "ya, jika kita menjalankan program ini dan membuatnya melihat salinan dari dirinya sendiri, program ini akan berjalan selamanya", maka R akan berhenti; tetapi jika Q menjawab "tidak, jika kita menjalankan program ini dan membuatnya melihat salinan dari dirinya sendiri, program ini tidak akan berjalan selamanya", maka R akan masuk ke perulangan tak hingga dan berjalan selamanya.
T: Apa yang terjadi jika Anda membuat R melihat dirinya sendiri?
J: Dua hal dapat terjadi - R berhenti atau berjalan selamanya - tetapi kedua hasil tersebut tidak mungkin terjadi menurut apa yang telah dibuktikan bahwa program seperti P tidak ada, jadi pasti ada sesuatu yang salah di suatu tempat di sepanjang jalan yang mengarah ke membuat R melihat dirinya sendiri.
