Program
Mesin Turing dan instruksinya menjadi model bagi macam-macam program yang dapat dibuat.
Program adalah rangkaian instruksi untuk dilakukan secara berurutan oleh komputer. Konsepnya sebenarnya sederhana, seperti dalam kehidupan sehari-hari.
Bagaimanakah cara memasukkan gajah ke dalam kulkas?
Gampang, pertama-tama buka pintu kulkasnya.
Lalu?
Masukkan gajahnya.
Kemudian?
Kemudian tutup pintunya. Selesai.
Dalam dialog Bomi dan Mila di atas, Mila memberikan suatu rangkaian instruksi:
Buka pintu kulkas.
Masukkan gajah.
Tutup pintu kulkas.
What’s an Algorithm? - David J. Malan
Kadang suatu instruksi dapat diulang-ulang dalam syarat tertentu.
Maaf, Poki. Kamu telalu baik buat aku. Aku tidak bisa menganggapmu lebih dari teman.
Baiklah, Sinta. Selama bumi berputar, aku akan selalu menunggu perasaanmu terhadapku berubah.
Kalimat Poki sudah bisa disebut sebagai program untuk dirinya sendiri. Poki berjanji akan melakukan sebuah instruksi: menunggu Sinta, dengan syarat bumi berputar. Janji Poki sangatlah berbahaya. Ia harus tetap menunggu sampai pada waktu bumi berhenti berputar. Besar kemungkinan bumi belum berhenti berputar setelah Poki meninggal.
Anggaplah Poki adalah makhluk immortal, dan tetap akan hidup sekalipun bumi sudah berhenti berputar. Poki bisa berhenti menunggu suatu hari nanti, yaitu ketika bumi berhenti berputar, tetapi entah kapan.
Ini disebut konstruksi perulangan, yang bentuknya adalah:
Selama a benar, lakukan b.
Bandingkan kasus di atas dengan kasus berikut ini:
Maaf, Poki. Kamu telalu baik buat aku. Aku tidak bisa menganggapmu lebih dari teman.
Baiklah, Sinta. Hari ini x bernilai 1. Selama x <10, aku akan selalu menunggumu sambil menambah x dengan 1 setiap hari.
Dalam kasus ini, Poki tidak perlu menunggu terlalu lama. Hari ini nilai x adalah 1. Besok nilai x adalah 2. Berarti, pada hari kesepuluh, Poki sudah boleh berhenti menunggu.
Kemudian kasus ketiga:
Maaf, Poki. Kamu telalu baik buat aku. Aku tidak bisa menganggapmu lebih dari teman.
Baiklah, Sinta. Hari ini x bernilai 1. Selama x >0, aku akan selalu menunggumu sambil menambah x dengan 1 setiap hari.
Dalam kasus ini, janji Poki sungguh berbahaya. Jika dalam kasus bumi berputar masih ada kemungkinan Poki akan berhenti menunggu, tetapi dalam kasus ini Poki tidak akan mungkin berhenti menunggu, karena setiap hari x akan bernilai lebih besar dari nol. Artinya kondisi yang disebutkan akan selalu terpenuhi!
Jadi kita melihat di sini ada program dengan beberapa macam kategori:
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.
Contoh tiga macam program tersebut dalam mesin Turing
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.
Program di bawah ini 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.
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.
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.
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