Halting Problem
Sampai di sini, kamu telah melihat bahwa ada program yang bisa berhenti (decidable), dan yang kadang berhenti kadang tidak (semi-decidable).
Seandainya saja ada program yang dapat memeriksa program lain apakah program tersebut dapat berhenti atau tidak, tentunya hidup kita akan lebih mudah bukan?
Ketika kita punya program P dan input n, yang kita tidak tahu akan berhenti atau tidak, kita tinggal minta program tersebut memeriksa apakah P(n) akan berhenti atau tidak, dan program tersebut akan menjawab kita Ya
atau Tidak
.
Mungkinkah program seperti itu dibuat?
Program TAMTAM
Permasalahan ini disebut sebagai masalah keterhentian (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?
Program NCEK
Sekarang mari kita berandai-andai terdapat program lain yang bernama NCEK yang diberi input program, dan akan memeriksa apakah program tersebut akan hang untuk input tertentu atau tidak.
Berarti ketika NCEK memeriksa sebuah program beserta inputnya, ia akan menjawab kita:
- Ya, program itu akan berhenti, tidak akan hang, jika program itu memang akan berhenti.
- Tidak, program itu akan hang, jika program itu tidak akan berhenti.
Asumsinya program NCEK ini selalu bisa menjawab kita, sehingga program NCEK termasuk sebagai program decidable.
Percobaan 1
Sekarang NCEK diberikan input TAMTAM untuk x=1 dan y=1. NCEK harus memberikan output tidak akan hang
.
Sementara jika NCEK diberikan input TAMTAM dengan x=1 dan y=0, NCEK akan menyimpulkan bahwa TAMTAM akan hang.
Tampaknya NCEK adalah program yang sangat berguna. Sekarang kita modifikasi sedikit program NCEK ini.
Percobaan 2: Modifikasi NCEK
Jika program yang dibaca oleh NCEK akan hang, NCEK akan berhenti dan melaporkan, Akan hang.
Tetapi jika program yang dibaca NCEK dapat berhenti, alih-alih menjawab NCEK sendiri yang akan hang.
Percobaan 3: Memperlihatkan NCEK pada bayangannya
Apa yang terjadi jika NCEK diberi input dirinya sendiri? Seolah-olah kita memberikan robot NCEK memeriksa bayangan cerminnya sendiri.
Apa yang akan dikatakan oleh NCEK?
- Jika dirinya akan hang, berarti ia harus mengatakan,
akan hang,
yang berarti ia tidak hang. - Jika dirinya tidak akan hang, berarti ia harus hang.
NCEK tidak akan sanggup memutuskan apa yang harus ia lakukan, karena jika ia akan hang, ia tidak boleh hang. Karena tidak boleh hang, berarti ia harus hang. Tetapi karena harus hang, ia tidak boleh hang. Dan seterusnya.
Sekarang kita akan kembali pada pertanyaan ini: Adakah persoalan yang tak dapat dijawab oleh komputer?
NCEK sudah menunjukkan kepada kita bahwa tidak semua hal dapat dilakukan oleh komputer. Ternyata tidak semua persoalan dapat dijawab menggunakan program. Karena inti dari komputer adalah proses komputasi, permasalahan yang dapat dikerjakan oleh komputer disebut permasalahan yang komputabel, dan yang tidak dapat dikerjakan oleh komputer disebut sebagai non-komputabel.
Lihat juga:
- Proof That Computers Can’t Do Everything (The Halting Problem) - udiprod
- Impossible Program (The Halting Problem) - Undefined Behavior
Berikutnya: Halting Problem dengan Pembuktian Diagonal