Masalah Tidak Terputuskan
Diperkenalkan| English | Makna |
|---|---|
| cannot/ˈkænɒt/ | tidak dapat |
| decidable/dɪˈsaɪdəbl/ | dapat diputuskan |
| undecidable/ˌʌndɪˈsaɪdəbl/ | tidak dapat diputuskan |
| limit/ˈlɪmɪt/ | batas |
| inefficient/ɪnɪˈfɪʃənt/ | tidak efisien |
Tidak semua masalah dapat diselesaikan
- Tidak semua masalah dapat diselesaikan oleh komputer, bahkan secara prinsip.
- Untuk melihat alasannya, kita mengelompokkan masalah menjadi dua jenis.
- Satu jenis yang selalu bisa dijawab komputer; yang lain tidak.
- Ini adalah fakta teruji dalam ilmu komputer, bukan kesenjangan yang mungkin akan kita isi suatu hari nanti.
Masalah terputus adalah masalah di mana:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
"Apakah n genap?" adalah terputus — selalu dapat dijawab.
Masalah yang dapat diputuskan
- Masalah dapat diputuskan memiliki algoritma yang selalu memberikan jawaban ya-tidak yang benar untuk setiap kasus.
- "Apakah bilangan ini genap?" dapat diputuskan — tes sederhana selalu memberikan jawaban yang benar.
- "Apakah bilangan ini prima?" juga dapat diputuskan, meskipun lambat untuk bilangan yang sangat besar.
- Jika algoritma yang benar ada untuk setiap kasus, masalah tersebut dapat diputuskan.
Terputus atau tidak terputus?
Masalah terputus memiliki algoritma yang selalu menjawab dengan benar untuk setiap kasus; masalah tidak terputus tidak memiliki algoritma semacam itu — hal itu mustahil, bukan sekadar lambat.
Masalah tidak terputus:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Beberapa kasus mengalahkan setiap program yang mungkin.
Memutuskan secara umum apakah program tertentu akan pernah berhenti berjalan adalah:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Tidak ada algoritma tunggal yang menjawab ini dengan benar untuk setiap program.
Ketidakterputusan menandai batas keras ______ pada apa yang dapat dicapai komputasi.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Beberapa pertanyaan memang tidak memiliki algoritma umum.
Masalah yang tidak dapat diputuskan
- Masalah yang tidak dapat diputuskan tidak memiliki algoritma yang dapat menyelesaikan setiap kasus dengan benar.
- Seberapa pun cerdasnya program tersebut, beberapa kasus akan tetap mengalahkannya.
- Contoh klasik: menentukan secara umum apakah suatu program tertentu akan pernah berhenti berjalan.
- Ketidakputuscan merupakan batas atas apa yang dapat dicapai komputasi — beberapa pertanyaan memang tidak memiliki algoritma umum.
Tidak terputus dan sekadar tidak efisien (lambat) berarti hal yang sama.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Tidak efisien dapat diselesaikan dengan lambat; tidak terputus tidak dapat diselesaikan untuk setiap kasus sama sekali.
Menguji apakah suatu bilangan prima adalah terputus, meskipun lambat untuk bilangan yang sangat besar.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Algoritma selalu menjawab; lambat bukan sama dengan mustahil.
Tidak dapat diputukan bukan sekadar lambat
- Jangan menyamakan ketidakputuscan dengan sekadar tidak efisien.
- Masalah yang tidak efisien dapat diselesaikan, hanya saja lambat. Masalah yang tidak dapat diputuskan tidak dapat diselesaikan untuk semua kasus sama sekali.
Prima vs berhenti. Menguji apakah sebuah bilangan prima adalah masalah yang dapat diputuskan — sebuah algoritma selalu memberikan jawaban, meskipun lambat untuk bilangan yang sangat besar. Namun, menentukan secara umum apakah semua program akan berhenti adalah masalah yang tidak dapat diputuskan: tidak ada satu algoritma tunggal yang menjawab dengan benar untuk setiap program. Lambat bukanlah hal yang sama dengan mustahil.
Masalah yang dapat diputuskan memiliki algoritma yang selalu memberikan jawaban yang benar ("apakah n genap?", "apakah n prima?"). Masalah yang tidak dapat diputuskan tidak memiliki algoritma semacam itu untuk semua kasus (akankah sebuah program berhenti?) — ini adalah batas nyata komputasi. Tidak dapat diputuskan berarti masalah tersebut tidak dapat diselesaikan sama sekali, bukan sekadar tidak efisien (lambat).