Apa yang Anda impikan saat berusia 16 tahun? Saya ingin mengendarai mobil dan berkeliling dunia. Namun ahli matematika Amerika, Ray Solomonoff, mempunyai tujuan yang lebih ambisius pada usia tersebut. Dia ingin menemukan metode untuk memecahkan setiap masalah ilmiah yang mungkin terjadi.
Ini bukan sekedar angan-angan saja—remaja tersebut mempunyai ide terobosan yang akan menciptakan bidang penelitian yang benar-benar baru. Selama beberapa tahun berikutnya, Solomonoff mengembangkan sebuah konsep yang memungkinkan Anda mencari pola di data secara sistematis—dan dengan demikian mengungkap proses tersembunyi yang mendasari dunia kita.
Saat ini, hal ini mungkin mengingatkan kita pada cara kerja kecerdasan buatan. Namun Solomonoff merumuskan ide pertamanya pada tahun 1942—jauh sebelum algoritma AI ada. Pendekatan Solomonoff didasarkan pada prinsip pisau cukur Occam, yang menyatakan bahwa penjelasan paling sederhana atas suatu fenomena biasanya adalah penjelasan yang benar. (Fisikawan menggunakan logika yang sama; mereka mencari rumus paling sederhana untuk mencoba menjelaskan sebanyak mungkin proses fisika.)
Tentang mendukung jurnalisme sains
Jika Anda menikmati artikel ini, pertimbangkan untuk mendukung jurnalisme pemenang penghargaan kami berlangganan. Dengan membeli langganan, Anda membantu memastikan masa depan cerita yang berdampak tentang penemuan dan ide yang membentuk dunia kita saat ini.
Solomonoff mencari seperangkat aturan atau algoritma yang akan mengungkap hubungan tersembunyi dalam data. Dengan begitu, ia berharap segala sesuatu yang ada di dunia bisa dijelaskan dengan mudah. Misalnya, jika Anda mencatat lintasan bola bisbol yang dilempar, Anda dapat menemukan sejumlah rumus matematika—beberapa di antaranya sangat rumit—yang mereproduksi jalur lintasan tersebut. Untuk mendapatkan hukum yang tepat dari semua kemungkinan ini, Anda harus mencari penjelasan yang paling sederhana. Jawabannya kemungkinan besar sesuai dengan hukum gerak Newton, yang menggambarkan interaksi dua gaya: gaya yang digunakan seseorang untuk melempar bola dan gaya gravitasi yang membawa bola ke tanah.
Solomonoff sedang mencari aturan yang akan memilih deskripsi yang paling sederhana dari semua kemungkinan deskripsi. Aturan-aturan tersebut dapat diterjemahkan ke dalam program komputer. Data apa pun dapat dikirim ke program ini, dan setelah jangka waktu tertentu, penjelasan paling sederhana tentang asal usul nilai ini dapat diperoleh. Ini akan menjadi mesin ajaib yang nyata.
Bagaimana Mendefinisikan “Mudah”
Hal pertama yang pertama: Pencari deskripsi Solomonoff yang paling sederhana tidak ada—dan tidak akan pernah ada. Namun demikian, dengan ide-idenya, remaja berusia 16 tahun ini berdiri di ambang bidang penelitian baru yang berhubungan dengan sifat sebenarnya dari peluang dan kompleksitas. Dan seperti yang sering terjadi dalam ilmu pengetahuan alam, dua orang lainnya mempunyai gagasan serupa pada waktu yang sama.
Salah satunya adalah matematikawan Soviet Andrey Kolmogorov, yang perhatian utamanya adalah pada probabilitas dan bilangan acak. Secara khusus, ia tertarik untuk menentukan apakah deskripsi fenomena tersebut sederhana atau kompleks.
Katakanlah saya menunjukkan angka 25.041.903. Pada pandangan pertama, tampaknya cukup acak. Ada berbagai cara untuk menjelaskan bagaimana saya mendapatkan nilai ini. Misalnya, saya dapat menggunakan generator angka acak dan mendapatkan angka 2, 5, 0, 4, 1, 9, 0 dan 3, dalam urutan itu. Tampaknya ini tidak terlalu memuaskan—tidak ada alasan di baliknya untuk membantu Anda mengingat nilainya. Tapi saya malah bisa mengatakan bahwa bilangan ini sama dengan hasil kali tiga bilangan prima 3 x 61 x 136.841. Atau saya dapat memberitahu Anda bahwa barisan angka dimulai dari angka desimal 40.122.575 pi atau saya memilih angka ini karena Kolmogorov lahir pada tanggal 25 April 1903. Penjelasan manakah yang paling mudah bagi Anda? Beda orang mungkin akan punya jawaban berbeda.
Kolmogorov berhasil mengembangkan a tujuan metode untuk menentukan kompleksitas suatu objek. Kompleksitas Kolmogorov suatu bilangan sesuai dengan panjang program komputer terpendek yang menghitung bilangan tersebut. Semakin pendek programnya, semakin sederhana angkanya.
Jadi, kompleksitas Kolmogorov bergantung pada bahasa pemrograman yang digunakan. Program tertentu mungkin lebih pendek di Python dibandingkan di C++ dan sebaliknya. Setiap program komputer dapat dinyatakan dalam kode mesin, yang pada gilirannya terdiri dari urutan 0s dan 1s. Panjang urutan terpendek 0s dan 1s yang komputer menghitung hasil yang diinginkan sesuai dengan kompleksitas Kolmogorov.
Jadi, jika Anda ingin menentukan kompleksitas Kolmogorov dari 25.041.903, Anda dapat menerjemahkan berbagai penjelasannya (yang merupakan hasil penghitungan angka atau faktorisasi prima, posisi dalam pi atau tanggal lahir Kolmogorov) ke dalam program komputer dan menghitungnya. karakter yang diperlukan dalam kode mesin yang sesuai.
Dan contoh saya sebelumnya mungkin mengecualikan penjelasan yang lebih sederhana untuk 25.041.903. Kolmogorov mengembangkan cara sistematis untuk mengidentifikasi program terpendek. Untuk melakukan ini, Anda memberi nomor pada komputer, misalnya 25.041.903. Komputer kemudian menjalankan semua algoritma yang mungkin satu per satu—dimulai dari yang terkecil, yang diberi kode 0 atau 1. Komputer melakukan hal ini hingga program yang dirumuskan menghasilkan hasil yang diinginkan. Program pertama yang mengembalikan nilai 25.041.903, misalnya, adalah yang terpendek. Panjang karakternya sesuai dengan kompleksitas Kolmogorov sebesar 25.041.903.
Paradoks yang Mengganggu dalam Menghancurkan Mimpi
Sekilas, impian Solomonoff kini tampaknya telah terwujud. Dengan kompleksitas Kolmogorov, tampaknya pola apa pun dalam data apa pun dapat terungkap.
Namun paradoks membuat pekerjaan menjadi sulit. Filsuf Bertrand Russell mengaitkan masalah tersebut dengan pustakawan GG Berry pada tahun 1908 — jauh sebelum Solomonoff dan Kolmogorov menerbitkan gagasan mereka. Contoh eksperimen pemikiran Berry adalah sebagai berikut: Misalkan Anda memiliki kamus yang hanya berisi 20 kata, dan Anda mencoba mendeskripsikan angka-angka berbeda menggunakan kata-kata tersebut—sangat mirip dengan apa yang ada dalam pikiran Kolmogorov tentang program komputer. Anda dapat secara bertahap mulai mendefinisikan angka menggunakan 20 kata ini. Hanya ada sejumlah cara yang terbatas untuk menggabungkan 20 kata, jadi Anda hanya dapat mendeskripsikan sejumlah angka yang terbatas. Namun, karena jumlah bilangannya tak terhingga, beberapa di antaranya luput dari definisi tersebut; Anda pada akhirnya akan sampai pada angka yang tidak dapat dijelaskan hanya dalam 20 kata. Namun bagaimana jika Anda menggunakan bagian dari 20 kata untuk merumuskan deskripsi “angka terkecil yang tidak dapat dijelaskan dalam 20 kata atau kurang”?
Definisi ini hanya terdiri dari 12 kata sehingga menimbulkan kontradiksi. Apa yang terjadi? Ternyata Anda tidak dapat menghitung berapa banyak kata yang diperlukan untuk mendefinisikan suatu angka. Ini tampak seperti alasan murahan pada awalnya, namun kenyataannya, paradoks Berry dan kompleksitas Kolmogorov terkait dengan salah satu fitur matematika yang paling tidak intuitif: beberapa kebenaran tidak dapat dibuktikan. Atau dengan kata lain: matematikanya tidak lengkap.
Misalkan memang ada program komputer K yang menghitung kompleksitas Kolmogorov yang terkait dengan setiap masukan. Program ini berisi satu juta karakter. Tidak harus cepat atau efisien; itu hanya harus berhasil.
Sekarang uji programnya dan masukkan semua masukan yang mungkin sampai Anda akhirnya menemukan sejumlah besar X yang kompleksitasnya dua juta. Kemudian lanjutkan dengan cara yang sama seperti paradoks Berry. Anda menulis program komputer baru P yang melakukan tugas berikut: secara sistematis menelusuri semua string dan menggunakan program K untuk menghitung kompleksitas Kolmogorov sebuah string hingga menemukan string dengan kompleksitas dua juta.
Program baru P tergantung langsung pada K dan karena itu tidak akan mengandung lebih banyak karakter daripada K. (Bagaimanapun, ini berisi kurang dari dua juta karakter.) Namun ini berarti bahwa telah ditemukan program komputer dengan kurang dari dua juta karakter yang menghitung angka dengan kompleksitas dua juta—sebuah kontradiksi.
Jika argumen logis menghasilkan kontradiksi, setidaknya salah satu premisnya harus salah. Dalam hal ini, kami berasumsi bahwa ada sebuah program K yang menghitung kompleksitas Kolmogorov untuk setiap masukan. Oleh karena itu, hanya ada satu kemungkinan kesimpulan: sebagai a K tidak bisa ada. Tidak mungkin menemukan program terpendek yang menghasilkan masukan ini untuk setiap masukan yang mungkin.
Akhir yang Bahagia Masih Mungkin
Jadi impian Solomonoff yang berusia 16 tahun tidak menjadi kenyataan. Meskipun kompleksitas Kolmogorov tidak dapat dihitung untuk setiap masukan, gagasan ini terbukti berguna dalam banyak penerapan. Kebanyakan kasus khusus tidak memerlukan a tepat Kompleksitas Kolmogorov—perkiraan saja sudah cukup. Para ahli biasanya menggunakan program kompresi untuk ini. Dalam situasi yang memerlukan kompleksitas Kolmogorov, “sebaliknya Anda dapat memasukkan data Anda ke dalam program kompresi, misalnya menggunakan gzip atau menyimpan gambar Anda sebagai file .gif dan menggunakannya sebagai perkiraan kasar,” ilmuwan komputer Scott Aaronson dari University of Texas di kata Austin Lebih-lebih lagi.
Misalnya, jika Anda ingin mengetahui apakah dua barisan bilangan, X Dan kamu (yang bisa sesuai dengan data pengukuran, misalnya), terkait, Anda dapat mengompresnya terlebih dahulu X Dan kamu satu per satu lalu tambahkan kedua urutan tersebut dan kompres xy. Jika kompresi xy hampir tidak lebih besar dari kompresi individu X atau kamumaka harus ada korelasi antara urutan angka-angka itu—dan Anda mempunyai petunjuk mengenai pola yang tersembunyi.
Kompleksitas Kolmogorov juga dapat digunakan untuk menentukan seberapa acak suatu rangkaian angka tertentu. Misalnya, tiga angka delapan digit 25.041.903, 47.395.929, dan 10.101.010 mungkin dihasilkan oleh generator angka acak—meskipun tidak semuanya terlihat sama acaknya. Peluang munculnya ketiga angka ini secara kebetulan adalah sama: dalam kisaran angka dari 00000000 hingga 99,999,999, terdapat probabilitas 1 dalam 108 bahwa Anda akan menemukan salah satu dari nilai-nilai ini. Namun 10.101.010 memiliki pola yang jelas, begitu pula 25.041.903 yang sesuai dengan tanggal lahir. Dengan menghitung kompleksitas suatu bilangan Kolmogorov, kita dapat menilai apakah bilangan tersebut mengikuti pola tertentu—dan apakah penghasil bilangan acak bekerja dengan andal.
Sayangnya, kompleksitas Kolmogorov tidak menjawab pertanyaan tentang “kehidupan, alam semesta, dan segalanya”. Jika kita mempercayai penulis fiksi ilmiah Douglas Adams, maka jawaban atas pertanyaan tersebut adalah 42. Namun anehnya, angka 42 tidaklah terlalu rumit—angka tersebut dapat dihitung menggunakan kompleksitas Kolmogorov.
Artikel ini awalnya muncul di Spektrum der Wissenschaft dan telah direproduksi dengan izin.
