Tiga macam program
Ada tiga kategori program berdasarkan potensi berhenti maupun tidaknya.
Ada program yang akan berhenti. Program yang memberikan hasil pasti adalah program yang berhenti, karena program itu harus menyelesaikan tugasnya dan memberikan kita laporan. Ini seperti kasus pertama (selama bumi berputar) dan kasus kedua (selama x < 10). Program yang akan berhenti tidak tentu memuaskan kita. Mungkin program ini akan berhenti tetapi lama sekali sehingga kita tidak sabar menunggunya. Contohnya seperti browser pada koneksi internet yang lambat. Kamu tahu bahwa pada akhirnya halaman web akan ditampilkan, tetapi entah kapan. Program seperti ini disebut sebagai program yang decidable.
Jenis program yang lain adalah program yang tidak mungkin berhenti, seperti pada kasus ketiga. Program yang seperti ini tidak mungkin memberikan hasil yang diinginkan. Program seperti ini disebut sebagai undecidable.
Suatu program biasanya berjalan dengan diberi kondisi awal yang disebut sebagai input. Kadang-kadang untuk input yang berbeda, program akan masuk dalam kategori yang berbeda.
- Ada program yang untuk sebagian macam input akan berhenti, dan untuk input lainnya tidak akan berhenti. Program seperti ini disebut sebagai semi decidable.
Di bawah ini diberikan sejumlah contoh masing-masing tipe program di atas. Ada yang menggunakan mesin Turing langsung, ada yang menggunakan Python.
Selalu berhenti
Mencari akhir untai
Program pertama ini adalah program yang mencari akhir dari untai inputnya. Karena pendek, program akan cepat selesai dan langsung memberi tahumu letak akhir dari untai tersebut.
Kita dapat melihat dengan jelas bahwa program ini termasuk kategori decidable, karena setiap input berhingga pasti memiliki ujung.
Program di bawah ini juga masih sama dengan program sebelumnya, tetapi karena untainya sangat panjang, hati kita bisa dipenuhi ketidakpastian mengenai program ini akan berakhir atau tidak. Jadi walaupun program ini termasuk decidable, dan kita tahu pasti demikian untuk input yang panjangnya berhingga, tetapi perasaan kita bisa jadi berkata lain, karena kita tidak dengan cepat melihat ujung untainya.
Apakah n bilangan prima?
Contoh ini adalah program Python yang dapat menggolongkan suatu bilangan asli sebagai prima atau bukan.
Program ini sengaja dibuat tidak secara optimal, sehingga kamu dapat merasakan waktu yang dibutuhkan untuk menentukan bilangan sebagai prima.
Cobalah memberi input bilangan asli yang kecil seperti
Setelah itu coba memberi input bilangan besar, seperti
Program ini termasuk decidable, karena akan selalu berhenti walaupun bisa sangat lama.
Tidak akan berhenti
Program diam
Program Python di bawah ini tidak akan pernah berhenti kecuali kamu hentikan (atau listrik mati). Dari luar kamu melihatnya sebagai diam saja karena kamu tidak menerima output apapun. Namun sebenarnya yang terjadi di dalamnya adalah komputasi yang diulang terus menerus. Dalam kebanyakan komputer kipas CPU akan berjalan lebih kencang, menjadi tanda bahwa ada komputasi yang dilakukan sementara kamu tidak menerima respon.
Program seperti ini termasuk dalam kategori undecidable. Kalau kamu menggunakan komputer dan mengalami crash atau hang, yang terjadi adalah seperti ini. Komputer tidak memberikan jawaban, tetapi mengulang-ulang proses yang sama terus menerus.
Mesin Turing mondar-mandir
Program di bawah ini juga undecidable. Sangat jelas tidak akan berhenti karena head-nya selalu mondar-mandir. Walaupun lucu melihat program yang berjalan seperti ini, tetapi program ini tidak dapat dipakai untuk menjawab pertanyaan karena tidak pernah berhenti.
Apakah program yang tidak berhenti selalu tidak berguna?
Kita biasanya memerlukan output dari komputer. Ada program yang memang dirancang untuk tidak pernah berhenti, tetapi terus menerus dapat memberikan output kepada kita. Misalnya program pemutar video maupun musik mengulang proses yang sama terus menerus, tetapi kita dapat menikmati hasilnya karena setiap saat kita menerima output dari program tersebut berupa gambar atau suara.
Jika suatu program dirancang untuk melakukan perhitungan dan hasilnya baru berguna setelah program itu selesai, program seperti ini wajib untuk berhenti agar kita dapat menggunakan hasilnya. Misalnya program penentu bilangan prima, mesin pencari informasi, chatbot AI, dan sebagainya. Kamu akan menganggap mesin pencari sebagai tidak berguna jika mesin tersebut hanya menampilkan progres berputar-putar tanpa memberikan hasil pencarian.
Kadang berhenti, kadang tidak
10 untuk berhenti
Program di bawah ini semi-decidable: Bisa berhenti, bisa berulang, tergantung dari input yang ditemukan oleh program. Kalau program menemukan input 10, program akan berhenti. Kalau program menemukan input 01, program tidak akan berhenti. Ketika program sudah berhenti, kamu bisa mereset ulang status programnya dan memulainya kembali.
Berhenti hanya pada kelipatan 5.
Bisakah kita mendeteksi program akan berhenti atau tidak?
Dalam kategori decidable, kamu telah melihat bahwa kadang-kadang program bisa berjalan begitu lama, dan dalam kategori semi-decidable, program bisa berhenti atau tidak bergantung inputnya.
Permasalahannya adalah, bagaimana kita membedakan bahwa sebuah program tidak akan berhenti, atau jangan-jangan sekarang hanya belum berhenti? Jangan-jangan program tersebut suatu ketika akan berhenti tetapi setelah melalui waktu yang sangat lama?
Berikutnya: Halting Problem