Czy testy mogą wykazać brak błędów?

$(n + 1)$ punkty są wymagane do jednoznacznego określenia wielomianu stopnia ; na przykład dwa punkty na płaszczyźnie określają dokładnie jedną linię.$n$

Ile punktów jest wymaganych do jednoznacznego określenia funkcji obliczeniowej , biorąc pod uwagę długość programu, który oblicza w ustalonym języku? (tj. związany ze złożonością Kołmogorowa ).$f : N \rightarrow N$$f$$f$

Chodzi o to, że przynajmniej teoretycznie można udowodnić poprawność programu, wykonując wystarczającą liczbę testów.

Jeśli ma się programu o długości , który oblicza nie jest związana z liczbą funkcji, które mogą być obliczone przy długości źródła co najwyżej .$P$$L$$f$$L$

Dlatego należałoby „tylko” udowodnić, że:

• $f$ można obliczyć na podstawie długości źródła$\leq L$
• $P$ nie oblicza żadnej innej funkcji obliczalnej w bajtach lub mniejszej (przez testowanie)$L$

Pomysł ten prawdopodobnie nie ma praktycznych konsekwencji (granice z pewnością będą miały charakter wykładniczy).

(To miało być komentarzem, ale trwało długo). Bardzo interesujące pytanie. Jeśli chcesz pomyśleć o innych miarach złożoności poza Kołmogorowem, w teorii uczenia się znajdziesz odpowiedzi, które mogą cię zadowolić. Zostawiam to ekspertom w tej dziedzinie.

Na przykład, jeśli się nie mylę, w „Teorii uczenia się” Valiant udowodnił, że funkcję boolowską można odtworzyć, biorąc pod uwagę wielomianową liczbę „punktów dodatnich” wielkości jej wzoru k-CNF (dla dowolnego ustalonego k , i mam na myśli z „dodatnimi punktami” te formy ).$(x_1,\ldots,x_n,1)$

W TAOCP 7.2.1.6 Knutha pokazano w zadziwiający sposób (przy użyciu wzoru choinki), że do rekonstrukcji monotycznej funkcji boolowskiej (tj. Nie zmniejszania się w każdej zmiennej) potrzebujesz dokładnie punktów.${n+1 \choose \lfloor n/2\rfloor+1}$

Aby kontynuować zgodnie z odpowiedzią Deigo, standardowe granice złożoności próby z teorii uczenia się mówią ci, że jeśli jesteś zadowolony ze znalezienia programu, który jest „w przybliżeniu poprawny”, nie musisz próbować zbyt wielu punktów. Powiedzmy, że kodujemy programy w formacie binarnym, więc są tylko programy o długości d. Pozwala przypuszczać, że istnieje jakiś podział na przykłady wejściowe D . Być może Twoim celem jest znalezienie programu, co do którego masz pewność, że jest prawie odpowiedni („Prawdopodobnie w przybliżeniu poprawny”, tj. Jak w modelu uczenia się Valiants PAC). Oznacza to, że chcesz uruchomić algorytm, który pobierze niewielką liczbę próbek x ∼ D razem z f ( x $2^d$$D$$x \sim D$$f(x)$I z prawdopodobieństwem będzie co najmniej wyjściu pewien program P , która zgadza się z F na co najmniej ( 1 - ε ) frakcji wejść sporządzonych z D . $(1-\delta)$$P$$f$$(1-\epsilon)$$D$

Po prostu narysujemy przykładów x ∼ D i wyprowadzimy dowolny program P o długości ≤ d, który zgadza się zf na wszystkich przykładach. (Istnieje jedna gwarancja, że ​​istnieje, ponieważ zakładamy, że f ma złożoność Kołmogorowa co najwyżej d ) ...$m$$x \sim D$$P$$\leq d$$f$$f$$d$

Co jest prawdopodobieństwo tego, że dany program , który jest przeciwny f o więcej niż ε frakcji przykładach są zgodne z m przykładach wybranych? To jest większość ( 1 - ε ) m . Chcielibyśmy przyjąć to prawdopodobieństwo za najwyżej δ / 2 d , abyśmy mogli wziąć związek związany we wszystkich programach 2 d i powiedzieć, że z prawdopodobieństwem co najmniej 1 - δ żaden „zły” program nie jest zgodny z naszymi narysowanymi przykładami . Po rozwiązaniu widzimy, że wystarczy wziąć tylko m ≥ $P$$f$$\epsilon$$m$$(1-\epsilon)^m$$\delta/2^d$$2^d$$1-\delta$ przykłady. (tj. tylko liniowo wielu w złożoności Kołmogorowaf...)

BTW, takie argumenty mogą być wykorzystane do uzasadnienia „brzytwy Ockhama”: biorąc pod uwagę stałą liczbę obserwacji, spośród wszystkich teorii, które je wyjaśniają, powinieneś wybrać tę o najniższej złożoności Kołmogorowa, ponieważ jest najmniejsza szansa na przeregulowanie.

Oczywiście, jeśli chcesz sprawdzić tylko jeden stały program w ten sposób, potrzebujesz tylko przykładów ...$O(\log(1/\delta)/\epsilon)$

Oto banalna odpowiedź: zakładając, że , musisz w ogóle znać wartość f | N | wskazuje na jednoznaczne określenie f . Dlatego podejście, które szkicujesz, wcale ci nie pomaga, chyba że w jakiś sposób wiesz, że długość L programu jest wyjątkowo krótka: znacznie krótsza niż lg | N | bitów$L \ge \lg |N|$$f$$|N|$$f$$L$$\lg |N|$

Rozważ rodzinę funkcji , gdzie f i jest zdefiniowane jako funkcja f i ( x ) = 1, jeśli i = x oraz f i ( x ) = 0, jeśli i ≠ x . Zauważ, że złożoność obliczeń F i Kołmogorowa dotyczy lg | N | bitów, ponieważ można na stałe zakodować wartość $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$w kodzie źródłowym, a następnie wystarczy prosta instrukcja warunkowa (dodatkowa ).$O(1)$

Jednakże, nie można odróżnić z funkcji all-zer chyba go przetestować na wejściu í . Nie można odróżnić f I od f j chyba przetestować na wejściu I lub j . Dlatego trzeba ocenić f wcale | N | Wejścia, aby jednoznacznie określić, które f I mamy do czynienia. (OK, technicznie, trzeba ocenić go na | N | - 1 wejść, ale co tam).$f_i$$i$$f_i$$f_j$$i$$j$$f$$|N|$$f_i$$|N|-1$

Możesz ustawić program dowolnie długo. Biorąc pod uwagę każdy program, możesz zdecydować, czy jego język jest równoważny z językiem tego programu. Nie możesz tego zrobić według twierdzenia Rice'a.