Halting Problem

Bayangkan ada sebuah program TAMTAM yang diberi input tertentu x dan y, dan akan menambah terus x dengan y sampai pada batas tertentu. Pada gambar di bawah ini, program TAMTAM digambarkan sebagai robot.

Mari kita simulasikan program TAMTAM. Ketika kita memberikan input x = 1, y = 1, maka program akan menambah x dengan 1 terus menerus selama x belum bernilai 100. Dapat kamu periksa bahwa setelah program selesai, x akan bernilai 100.

Namun apa yang akan terjadi jika kita memberikan input x = 1 dan y = -1? Nilai x bukannya bertambah tetapi berkurang. Karena selalu berkurang, akibatnya nilai x selalu lebih kecil dari 100. Program ini tak akan pernah berhenti!

Jadi program TAMTAM ini akan memberikan output ketika input y yang diberikan lebih besar dari nol.

Program TAMTAM tidak akan memberikan output, karena tidak pernah berhenti (disebut sebagai hang), ketika y yang diberikan kurang dari atau sama dengan nol.

Jadi terdapat dua kategori input bagi program TAMTAM. Input yang menyebabkan program tidak pernah berhenti menghitung, dan input yang dapat diproses hingga berhenti.

Untuk kasus program TAMTAM, kita dengan mudah mengetahui input apa yang akan membuat program hang. Namun ada banyak program yang tidak dapat dengan mudah diprediksi kapan program tersebut akan hang. Karena itulah aplikasi terbaik apapun perlu terus menerus di-update.

Selain itu, seperti pada kasus Bomi sebelumnya, bagaimana kita membedakan bahwa suatu program hang atau akan selesai dalam waktu sangat lama?

Sekarang andaikan terdapat program lain yang bernama NCEK yang diberi input program, dan akan memeriksa apakah program tersebut akan hang untuk input tertentu atau tidak.

Berikutnya: Percobaan 1