Les tests peuvent-ils montrer l'absence de bogues?

$(n + 1)$ points sont nécessaires pour déterminer de façon unique un polynôme de degré ; par exemple, deux points dans un plan déterminent exactement une ligne.$n$

Combien de points sont nécessaires pour déterminer de manière unique une fonction calculable , étant donné la longueur d'un programme qui calcule dans un langage fixe? (ie une borne sur la complexité de Kolmogorov de ).f $f : N \rightarrow N$$f$$f$

L'idée est que, du moins théoriquement, on pourrait prouver l'exactitude d'un programme en faisant suffisamment de tests.

Si l' on dispose d' un programme d' une longueur qui calcule , il y a une limite sur le nombre de fonctions qui peuvent être calculées avec une longueur de source d'au plus .L f $P$$L$$f$$L$

Il suffirait donc "seulement" de prouver que:

• ≤ $f$ peut être calculé avec une longueur source$\leq L$
• $P$ ne calcule aucune autre fonction calculable en octets ou moins (en testant)$L$

Cette idée n'a probablement aucune conséquence pratique (les bornes sont sûrement forcément exponentielles).

(Cela était censé être un commentaire, mais s'est prolongé). Question très intéressante. Si vous êtes prêt à penser à d'autres mesures de complexité en plus de celles de Kolmogorov, alors il y a quelques réponses dans la théorie de l'apprentissage qui pourraient vous satisfaire. Je laisse cela aux experts du domaine.

Par exemple, si je ne me trompe pas, dans "Une théorie de l'apprentissage", Valiant a prouvé qu'une fonction booléenne peut être reconstruite étant donné un nombre polynomial de "points positifs" sur la taille de sa formule k-CNF (pour tout k fixe , et je veux dire avec "points positifs" ceux de la forme ).$(x_1,\ldots,x_n,1)$

Dans le TAOCP 7.2.1.6 de Knuth, il est montré de manière étonnante (en utilisant le modèle d'arbre de Noël) que pour reconstruire une fonction booléenne monote (c'est-à-dire non décroissante dans chaque variable), vous avez besoin exactement de points.${n+1 \choose \lfloor n/2\rfloor+1}$

Pour continuer dans le sens de la réponse de Deigo, les limites standard de complexité des échantillons de la théorie de l'apprentissage vous disent que si vous êtes satisfait de trouver un programme qui est "approximativement correct", vous n'avez pas besoin d'essayer beaucoup de points. Disons que nous encodons des programmes en binaire, de sorte qu'il n'y a que programmes de longueur d. Laisse supposer également qu'il ya une certaine distribution sur des exemples d'entrée . Peut-être que votre objectif est de trouver un programme dont vous êtes presque sûr qu'il a presque raison («Probablement approximativement correct», c'est-à-dire comme dans le modèle d'apprentissage PAC de Valiants). Autrement dit, vous voulez exécuter un algorithme qui prendra un petit nombre d'échantillons avec , et avec probabilité au moins D x ∼ D f ( x ) ( 1 - δ ) P f ( 1 - ϵ ) $2^d$$D$$x \sim D$$f(x)$$(1-\delta)$sortie un certain programme qui est en accord avec sur au moins une fraction d'entrées provenant de . $P$$f$$(1-\epsilon)$$D$

Nous allons simplement dessiner exemples , et sortir tout programme de longueur qui est d'accord avec sur tous les exemples. (Un est garanti d'exister puisque nous supposons que a une complexité de Kolmogorov au plus ) ...x ∼ D P ≤ d f f $m$$x \sim D$$P$$\leq d$$f$$f$$d$

Quelle est la probabilité qu'un programme particulier désaccord avec sur plus d'une fraction d'exemples soit cohérent avec les exemples que nous avons sélectionnés? C'est tout au plus . Nous aimerions prendre cette probabilité pour être au plus afin que nous puissions prendre une union liée sur tous les programmes et dire qu'avec une probabilité d'au moins , aucun "mauvais" programme n'est cohérent avec nos exemples dessinés. En résolvant, nous voyons qu'il suffit de prendre uniquement des exemples . (c.-à-d. seulement linéairement nombreux dans la complexité de Kolmogorov def ϵ m ( 1 - ϵ ) m δ / 2 d 2 d 1 - δ m ≥ $P$$f$$\epsilon$$m$$(1-\epsilon)^m$$\delta/2^d$$2^d$$1-\delta$

BTW, des arguments comme celui-ci peuvent être utilisés pour justifier "le rasoir d'Occam": étant donné un nombre fixe d'observations, parmi toutes les théories qui les expliquent, vous devez choisir celle avec la complexité de Kolmogorov la plus faible, car il y a le moins de chance de sur-ajustement.

Bien sûr, si vous ne voulez vérifier qu'un seul programme fixe de cette manière, vous n'avez besoin que d' exemples ...$O(\log(1/\delta)/\epsilon)$

Voici une réponse triviale: en supposant que, alors vous devez connaître la valeur de du toutindique une détermination unique . Par conséquent, l'approche que vous esquissez ne vous aide pas du tout, sauf si vous savez en quelque sorte que la longueur du programme est extrêmement courte: beaucoup plus courte quemorceaux.f | N | f L lg | N $L \ge \lg |N|$$f$$|N|$$f$$L$$\lg |N|$

Considérons la famille de fonctions , où est définie comme étant la fonction si et si . Notez que la complexité de Kolmogorov dans le calcul de est d'environbits, car vous pouvez coder en dur la valeur de dans le code source, puis tout ce dont vous avez besoin est une simple déclaration conditionnelle ( supplémentaire).f i f i ( x ) = 1 i = x f i ( x ) = 0 i ≠ x f i lg | N | i O ( 1 $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$$O(1)$

Cependant, vous ne pouvez pas distinguer de la fonction tous les zéros à moins de le tester à l'entrée . Vous ne pouvez pas distinguer de moins de tester à l'entrée ou . Par conséquent, vous devrez évaluer du toutentrées, pour déterminer de manière unique à quel nous avons affaire. (OK, techniquement, vous devez l'évaluer aux entrées , mais peu importe.) i f i f j i j f | N | f i | N | - $f_i$$i$$f_i$$f_j$$i$$j$$f$$|N|$$f_i$$|N|-1$

Vous pouvez rendre le programme arbitrairement long. Donc, étant donné n'importe quel programme, vous pouvez décider si sa langue est équivalente à celle de ce programme. Vous ne pouvez pas faire cela par le théorème de Rice.