Gambar: cono0430 (Shutterstock)
Diberdayakan oleh teknologi kecerdasan buatan, komputer saat ini dapat melakukan percakapan yang meyakinkan dengan orang-orang, membuat lagu, melukis lukisan, bermain catur dan pergi, dan mendiagnosis penyakit, untuk menyebutkan beberapa contoh kehebatan teknologi mereka.
Keberhasilan ini dapat diambil untuk menunjukkan bahwa perhitungan tidak memiliki batas. Untuk melihat apakah itu masalahnya, penting untuk memahami apa yang membuat komputer kuat.
Ada dua aspek kekuatan komputer: jumlah operasi yang dapat dijalankan perangkat kerasnya per detik dan efisiensi algoritme yang dijalankannya. Kecepatan perangkat keras dibatasi oleh hukum fisika. Algoritma – pada dasarnya kumpulan instruksi – ditulis oleh manusia dan diterjemahkan ke dalam urutan operasi yang dapat dijalankan oleh perangkat keras komputer. Bahkan jika kecepatan komputer dapat mencapai batas fisik, rintangan komputasi tetap ada karena batas algoritme.
Rintangan ini termasuk masalah yang tidak mungkin dipecahkan oleh komputer dan masalah yang secara teoritis dapat dipecahkan tetapi dalam praktiknya berada di luar kemampuan bahkan versi paling kuat dari komputer saat ini yang dapat dibayangkan. Matematikawan dan ilmuwan komputer mencoba untuk menentukan apakah suatu masalah dapat dipecahkan dengan mencobanya pada mesin imajiner.
G/O Media dapat memperoleh komisi
Mesin komputasi imajiner
Gagasan modern tentang algoritme, yang dikenal sebagai mesin Turing, diformulasikan pada tahun 1936 oleh matematikawan Inggris Alan Turing. Ini adalah perangkat imajiner yang meniru bagaimana perhitungan aritmatika dilakukan dengan pensil di atas kertas. Mesin Turing adalah template yang menjadi dasar semua komputer saat ini.
Untuk mengakomodasi perhitungan yang membutuhkan lebih banyak kertas jika dilakukan secara manual, pasokan kertas imajiner dalam mesin Turing diasumsikan tidak terbatas. Ini setara dengan pita imajiner tanpa batas, atau “pita”, dari kotak, yang masing-masing kosong atau berisi satu simbol.
Mesin dikendalikan oleh seperangkat aturan terbatas dan dimulai pada urutan awal simbol pada pita. Operasi yang dapat dilakukan mesin adalah memindahkan ke kotak tetangga, menghapus simbol, dan menulis simbol di kotak kosong. Mesin menghitung dengan melakukan urutan operasi ini. Saat mesin selesai, atau “berhenti”, simbol yang tersisa di pita adalah keluaran atau hasil.
Apa itu mesin Turing?
Komputasi seringkali tentang keputusan dengan jawaban ya atau tidak. Dengan analogi, tes medis (jenis masalah) memeriksa apakah spesimen pasien (contoh masalah) memiliki indikator penyakit tertentu (jawaban ya atau tidak). Instance, yang direpresentasikan dalam mesin Turing dalam bentuk digital, adalah urutan simbol awal.
Suatu masalah dianggap “dapat dipecahkan” jika mesin Turing dapat dirancang yang berhenti untuk setiap contoh apakah positif atau negatif dan dengan benar menentukan jawaban mana yang dihasilkan contoh.
Tidak setiap masalah bisa diselesaikan
Banyak masalah dapat diselesaikan dengan menggunakan mesin Turing dan karenanya dapat diselesaikan di komputer, sementara banyak lainnya tidak. Misalnya, soal domino, variasi dari soal ubin yang dirumuskan oleh matematikawan Cina-Amerika Hao Wang pada tahun 1961, tidak dapat dipecahkan.
Tugasnya adalah menggunakan satu set domino untuk menutupi seluruh kotak dan, mengikuti aturan sebagian besar permainan domino, mencocokkan jumlah pips di ujung domino yang berbatasan. Ternyata tidak ada algoritma yang dapat dimulai dengan satu set kartu domino dan menentukan apakah set tersebut akan menutupi grid sepenuhnya atau tidak.
Menjaga itu masuk akal
Sejumlah masalah yang dapat dipecahkan dapat diselesaikan dengan algoritma yang berhenti dalam waktu yang wajar. “Algoritme waktu polinomial” ini adalah algoritme yang efisien, artinya praktis menggunakan komputer untuk menyelesaikan instance darinya.
Ribuan masalah lain yang dapat dipecahkan tidak diketahui memiliki algoritme waktu polinomial, meskipun upaya intensif terus dilakukan untuk menemukan algoritme semacam itu. Ini termasuk Traveling Salesman Problem.
The Travelling Salesman Problem menanyakan apakah sekumpulan titik dengan beberapa titik terhubung langsung, disebut graf, memiliki jalur yang dimulai dari titik mana pun dan melewati setiap titik lainnya tepat satu kali, dan kembali ke titik semula. Bayangkan seorang penjual ingin menemukan rute yang melewati semua rumah tangga di lingkungan tepat satu kali dan kembali ke titik awal.
Masalah Penjual Keliling dengan cepat menjadi tidak terkendali saat Anda melampaui beberapa tujuan.
Masalah-masalah ini, yang disebut NP-complete, dirumuskan secara independen dan terbukti ada pada awal 1970-an oleh dua ilmuwan komputer, Stephen Cook dari Amerika Kanada dan Leonid Levin dari Amerika Ukraina. Cook, yang karyanya didahulukan, dianugerahi Penghargaan Turing 1982, yang tertinggi dalam ilmu komputer, untuk karya ini.
Biaya mengetahui persis
Algoritme paling terkenal untuk masalah NP-complete pada dasarnya mencari solusi dari semua kemungkinan jawaban. Masalah Penjual Keliling pada grafik beberapa ratus poin akan memakan waktu bertahun-tahun untuk berjalan di superkomputer. Algoritme semacam itu tidak efisien, artinya tidak ada jalan pintas matematis.
Algoritme praktis yang mengatasi masalah ini di dunia nyata hanya dapat menawarkan perkiraan, meskipun perkiraan tersebut meningkat. Apakah ada algoritme waktu polinomial yang efisien yang dapat menyelesaikan masalah NP-complete adalah salah satu dari tujuh masalah terbuka milenium yang diposting oleh Institut Matematika Tanah Liat pada pergantian abad ke-21, masing-masing membawa hadiah sebesar US$1 juta.
Di luar Turing
Mungkinkah ada bentuk perhitungan baru di luar kerangka kerja Turing? Pada tahun 1982, fisikawan Amerika Richard Feynman, seorang peraih Nobel, mengemukakan gagasan perhitungan berdasarkan mekanika kuantum.
Apa itu komputer kuantum?
Pada tahun 1995, Peter Shor, seorang ahli matematika terapan Amerika, mempresentasikan algoritma kuantum untuk memfaktorkan bilangan bulat dalam waktu polinomial. Matematikawan percaya bahwa ini tidak dapat dipecahkan oleh algoritma waktu polinomial dalam kerangka Turing. Memfaktorkan bilangan bulat berarti menemukan bilangan bulat yang lebih kecil lebih besar dari 1 yang dapat membagi bilangan bulat tersebut. Misalnya, bilangan bulat 688.826.081 habis dibagi oleh bilangan bulat yang lebih kecil, 25.253, karena 688.826.081 = 25.253 x 27.277.
Algoritma utama yang disebut algoritma RSA, banyak digunakan dalam mengamankan komunikasi jaringan, didasarkan pada kesulitan komputasi memfaktorkan bilangan bulat besar. Hasil Shor menunjukkan bahwa komputasi kuantum, jika menjadi kenyataan, akan mengubah lanskap keamanan siber.
Bisakah komputer kuantum lengkap dibangun untuk memfaktorkan bilangan bulat dan memecahkan masalah lain? Beberapa ilmuwan percaya itu bisa terjadi. Beberapa kelompok ilmuwan di seluruh dunia sedang bekerja untuk membuatnya, dan beberapa telah membangun komputer kuantum skala kecil.
Namun demikian, seperti semua teknologi baru yang ditemukan sebelumnya, masalah dengan komputasi kuantum hampir pasti akan muncul yang akan memaksakan batasan baru.
Jie Wang adalah profesor Ilmu Komputer di UMass Lowell.
Artikel ini diterbitkan ulang dari The Conversation di bawah lisensi Creative Commons. Baca artikel aslinya.