Bisakah pengujian menunjukkan tidak adanya bug?

( N + 1 ) $(n + 1)$ poin diperlukan untuk secara unik menentukan polinomial derajat ; misalnya, dua titik di pesawat menentukan dengan tepat satu garis.$n$

Berapa banyak poin yang diperlukan untuk secara unik menentukan fungsi yang dapat dihitung , mengingat lamanya program yang menghitung dalam bahasa tetap? (Yaitu terikat pada kompleksitas Kolmogorov dari ).$f : N \rightarrow N$$f$$f$

Idenya adalah bahwa, setidaknya secara teoritis, seseorang dapat membuktikan kebenaran suatu program dengan membuat tes yang cukup.

Jika seseorang memiliki program panjang yang menghitung , ada terikat pada jumlah fungsi yang dapat dihitung dengan panjang sumber paling .$P$$L$$f$$L$

Karena itu seseorang "hanya" perlu membuktikan bahwa:

• $f$ dapat dihitung dengan panjang sumber$\leq L$
• $P$ tidak menghitung fungsi lain yang dapat dihitung dalam byte atau kurang (dengan pengujian)$L$

Gagasan ini mungkin tidak memiliki konsekuensi praktis (batas-batasnya pasti bersifat eksponensial).

(Ini dimaksudkan sebagai komentar, tetapi berlangsung lama). Pertanyaan yang sangat menarik. Jika Anda bersedia untuk memikirkan langkah-langkah kompleksitas lain selain Kolmogorov, maka ada beberapa jawaban dalam teori Belajar yang mungkin memuaskan Anda. Saya meninggalkannya untuk para ahli di daerah.

Misalnya, jika saya tidak salah, dalam "Sebuah teori yang dapat dipelajari" Valiant membuktikan bahwa fungsi boolean dapat direkonstruksi dengan jumlah polinomial "titik positif" pada ukuran rumus k-CNF-nya (untuk setiap k , dan maksud saya dengan "poin positif" yang ada dalam formulir ).$(x_1,\ldots,x_n,1)$

Dalam TAOCP 7.2.1.6 Knuth ditunjukkan dengan cara yang menakjubkan (menggunakan pola pohon Natal) bahwa untuk merekonstruksi fungsi monote boolean (yaitu tidak menurun pada setiap variabel) Anda membutuhkan tepat poin.${n+1 \choose \lfloor n/2\rfloor+1}$

Untuk melanjutkan jawaban Deigo, kompleksitas sampel standar yang dibatasi oleh teori belajar memberi tahu Anda bahwa jika Anda puas menemukan program yang "kira-kira benar", Anda tidak perlu mencoba banyak poin sama sekali. Katakanlah kita meng-encode program dalam biner, sehingga hanya ada program dengan panjang d. Mari kita misalkan juga bahwa ada beberapa distribusi lebih contoh masukan . Mungkin tujuan Anda adalah untuk menemukan program yang Anda yakini hampir benar ("Kemungkinan Sekitar Tepat" yaitu seperti dalam model pembelajaran Pali Valiants). Artinya, Anda ingin menjalankan algoritma yang akan mengambil sejumlah kecil sampel bersama dengan , dan akan dengan probabilitas setidaknya$2^d$$D$$x \sim D$$f(x)$$(1-\delta)$Output program beberapa yang setuju dengan pada setidaknya sebagian kecil dari input diambil dari . $P$$f$$(1-\epsilon)$$D$

Kami hanya akan menggambar contoh , dan menampilkan program dengan panjang yang sesuai dengan pada semua contoh. (Satu dijamin ada karena kami menganggap memiliki kompleksitas Kolmogorov paling banyak ) ...$m$$x \sim D$$P$$\leq d$$f$$f$$d$

Berapa probabilitas bahwa suatu program tertentu yang tidak setuju dengan pada lebih dari fraksi contoh konsisten dengan contoh kami pilih? Paling banyak . Kami ingin menjadikan probabilitas ini paling banyak sehingga kami dapat mengambil ikatan serikat atas semua program dan mengatakan bahwa dengan probabilitas setidaknya , tidak ada program "buruk" yang konsisten dengan contoh menarik kami. Memecahkan, kita melihat bahwa itu cukup untuk mengambil contoh hanya . (Yaitu hanya banyak linear dalam kompleksitas Kolmogorov dari$P$$f$$\epsilon$$m$$(1-\epsilon)^m$$\delta/2^d$$2^d$$1-\delta$

BTW, argumen seperti ini dapat digunakan untuk menjustifikasi "Occam's Razor": mengingat sejumlah pengamatan, di antara semua teori yang menjelaskannya, Anda harus memilih teori dengan kompleksitas Kolmogorov terendah, karena ada sedikit peluang untuk overfitting.

Tentu saja, jika Anda hanya ingin memeriksa satu program tetap dengan cara ini, Anda hanya perlu contoh ...$O(\log(1/\delta)/\epsilon)$

Inilah jawaban yang sepele: dengan asumsi L ≥ lg | N | , maka Anda perlu tahu nilai f sama sekali | N | poin untuk menentukan secara unik f . Oleh karena itu, pendekatan yang Anda buat sketsa sama sekali tidak membantu, kecuali Anda entah bagaimana tahu bahwa panjang L dari program ini sangat pendek: jauh lebih pendek daripada lg | N | bit.$L \ge \lg |N|$$f$$|N|$$f$$L$$\lg |N|$

Pertimbangkan sekumpulan fungsi F = { f i : i ∈ N } , di mana f i didefinisikan sebagai fungsi f i ( x ) = 1 jika i = x dan f i ( x ) = 0 jika i ≠ x . Perhatikan bahwa kompleksitas Kolmogorov komputasi f i adalah tentang lg | N | bit, karena Anda dapat meng-hardcode nilai $F=\{f_i:i\in N\}$$f_i$$f_i(x) = 1$$i=x$$f_i(x)=0$$i\ne x$$f_i$$\lg |N|$$i$dalam kode sumber dan kemudian yang Anda butuhkan hanyalah pernyataan kondisional sederhana ( O ( 1 ) ekstra).$O(1)$

Namun, Anda tidak dapat membedakan f i dari fungsi all-zero kecuali Anda mengujinya di input i . Anda tidak dapat membedakan f i dari f j kecuali Anda menguji pada input i atau j . Karena itu, Anda harus mengevaluasi f sama sekali | N | input, untuk secara unik menentukan f i kita hadapi. (OK, secara teknis, Anda perlu mengevaluasinya di | N | - 1 input, tapi apa pun.)$f_i$$i$$f_i$$f_j$$i$$j$$f$$|N|$$f_i$$|N|-1$

Anda bisa membuat program ini panjang dan sewenang-wenang. Jadi dengan program apa pun, Anda dapat memutuskan apakah bahasanya setara dengan program ini. Anda tidak dapat melakukannya dengan teorema Rice.