Apa penjelasan awam untuk pencarian universal?

Saya membaca buku tentang topik ilmu komputer tetapi tidak memiliki beberapa latar belakang prasyarat. Biasanya ketika saya mengalami istilah yang saya tidak mengerti, saya hanya mencarinya, tetapi untuk Pencarian Universal saya belum bisa menemukan penjelasan yang cocok untuk pembaca tanpa latar belakang statistik / ilmu komputer.

Saya telah membaca artikel ini di Pencarian Universal dari Scholarpedia , yang tampaknya mencakup topik. Saya menghargai penjelasan untuk arti dari Pencarian Universal (atau Pencarian Levin ).

Pikirkan seperti ini. Anda memiliki masalah, dengan input dan Anda tahu cara memverifikasi solusi jika Anda pernah menemukan satu (seperti kebalikan dari matriks atau apa pun yang ingin Anda bayangkan).$x$

Sekarang, ambil bahasa pemrograman favorit Anda (katakanlah Python), dan buat setiap program Python tunggal yang terdiri dari paling banyak 10 karakter! Kemudian Anda menjalankan semua program tersebut dengan input Anda masing-masing selama 10 detik, masing-masing pada input . Jika tidak ada yang memberikan jawaban kepada Anda, lanjutkan ke 11. Jalankan setiap program dengan maksimal 11 karakter (termasuk yang sudah Anda coba, tentu saja) masing-masing selama 11 detik, pada input x . Jika tidak ada yang memberikan jawaban yang benar, Anda melanjutkan ke 12 dan seterusnya.$x$$x$

Secara lebih formal, dalam iterasi , Anda menjalankan semua program dengan panjang paling banyak i (banyak, tetapi tentu saja eksponensial di i ), masing-masing selama i detik (atau langkah-langkah).$i$$i$$i$$i$

Ada sebuah program, mengatakan yang memberikan output yang benar di s detik. Ketika Anda datang ke iterasi, i = max { | P | , S } , program ini akan berjalan selama setidaknya s detik, dan Anda akan menampilkan kedua P dan solusinya.$P$$s$$i = \max\{|P|, s\}$$s$$P$

Hanya untuk menambah apa yang dikatakan Pål GD, ingatlah bahwa Anda menjalankan semua program panjang atau kurang, dan membiarkan mereka berjalan selama paling i detik. Jadi mungkin ada program yang mendapatkan jawaban yang tepat yaitu 100 karakter, tetapi butuh 120 detik untuk berjalan. Sebut bahwa program P . Pada i = 100 Anda akan memeriksa program ini, tetapi terlalu lama untuk dijalankan sehingga Anda membuangnya. Setelah memeriksa semua program dengan panjang 100, Anda menemukan tidak ada yang memberikan jawaban yang benar, jadi Anda mencoba program dengan panjang 101 dan semua program yang Anda coba sebelumnya . Jadi Anda coba lagi $i$$i$$P$$i=100$$101$ $P$, program yang (kami tahu) akan memberikan jawaban yang tepat, tetapi masih terlalu lama sehingga Anda membuangnya. Kami teruskan proses itu, sampai kami mendapatkan . Kemudian kita mencoba semua program dengan panjang ≤ 120 , dan ketika kita sampai ke P kita membiarkannya berjalan cukup lama untuk itu untuk memberikan jawaban yang benar. Lalu kami berhenti - kami telah menemukan algoritma yang kami inginkan. Iterasi yang kita jalani adalah i = 120 , karena walaupun panjang program P lebih kecil (kita akan menulis | P | = 100 ), kita harus menunggu sampai waktu yang diperlukan adalah 120 detik ( s = $i=120$$\leq 120$$P$$i = 120$$P$$|P|=100$$s=120$). Jadi berarti maksimum dari panjang program P dan jumlah waktu yang dibutuhkan untuk menjalankan s .$i=\mathrm{max}\{|P|,s\}$$P$$s$

Cara lain untuk melihat itu adalah untuk program yang mengambil s detik untuk menghasilkan jawaban yang benar, kita harus memeriksa setidaknya | P | iterasi, dan setidaknya s iterasi sebelum kita akan menemukannya, karena jika saya < | P | maka kita belum memeriksa program yang belum, dan jika saya < s maka kita tidak membiarkan program berjalan cukup lama.$P$$s$ $|P|$ $s$$i < |P|$$i < s$

Perhatikan bahwa metode pencarian ini hanya dijamin untuk memberi Anda jawaban jika ada; itu tidak dijamin untuk menemukan jawaban tersingkat atau tercepat. Alasan untuk itu harus jelas jika Anda menganggap bahwa proses berakhir segera setelah menemukan program yang memberikan jawaban yang benar.