¿Las pruebas pueden mostrar la ausencia de errores?

$(n + 1)$ se requieren puntos para determinar unívocamente un polinomio de grado $n$ ; Por ejemplo, dos puntos en un plano determinan exactamente una línea.

¿Cuántos puntos se requieren para determinar de manera única una función computable $f : N \rightarrow N$ , dada la longitud de un programa que computa $f$ en un lenguaje fijo? (es decir, un límite en la complejidad de Kolmogorov de $f$ ).

La idea es que, al menos teóricamente, uno podría probar la corrección de un programa haciendo suficientes pruebas.

Si uno tiene un programa $P$ de longitud $L$ que calcula $f$ , hay un límite en el número de funciones que pueden calcularse con una longitud de fuente de máximo $L$.

Por lo tanto, "solo" sería necesario demostrar que:

• $f$ sepuede calcular con una longitud de fuente$\leq L$
• $P$ no calcula ninguna otra función computable en$L$ bytes o menos (mediante prueba)

Esta idea probablemente no tiene consecuencias prácticas (los límites seguramente serán exponenciales).

(Esto fue un comentario, pero fue largo). Pregunta muy interesante Si está dispuesto a pensar en otras medidas de complejidad además de las de Kolmogorov, entonces hay algunas respuestas en la teoría del aprendizaje que podrían satisfacerlo. Lo dejo para los expertos en el área.

Por ejemplo, si no me equivoco, en "Una teoría de lo que se puede aprender", Valiant demostró que una función booleana se puede reconstruir dado un número polinómico de "puntos positivos" en el tamaño de su fórmula k-CNF (para cualquier k fijo , y quiero decir con "puntos positivos" los de la forma ).$(x_1,\ldots,x_n,1)$

En el TAOCP 7.2.1.6 de Knuth se muestra de una manera sorprendente (usando el patrón del árbol de Navidad) que para reconstruir una función booleana monote (es decir, no decreciente en cada variable) necesita exactamente puntos.${n+1 \choose \lfloor n/2\rfloor+1}$

Para continuar en la línea de la respuesta de Deigo, los límites de complejidad de la muestra estándar de la teoría del aprendizaje le dicen que si está satisfecho con encontrar un programa que sea "aproximadamente correcto", no necesita probar muchos puntos. Digamos que estamos codificando programas en binario, por lo que solo hay programas d de longitud d. Lets Supongamos también que hay una cierta distribución sobre ejemplos de entrada D . Quizás su objetivo es encontrar un programa que esté bastante seguro de que es casi correcto ("Probablemente aproximadamente correcto", es decir, como en el modelo de aprendizaje Valiants PAC). Es decir, desea ejecutar un algoritmo que tomará una pequeña cantidad de muestras x ∼ D junto con f ( x $2^d$$D$$x \sim D$$f(x)$, Y la voluntad con una probabilidad de al menos de salida de un programa P que está de acuerdo con f sobre al menos una ( 1 - ε ) fracción de entradas procedentes de D . $(1-\delta)$$P$$f$$(1-\epsilon)$$D$

Simplemente dibujaremos ejemplos x ∼ D , y sacaremos cualquier programa P de longitud ≤ d que coincida con f en todos los ejemplos. (Se garantiza que existe uno dado que suponemos que f tiene complejidad de Kolmogorov como máximo d ) ...$m$$x \sim D$$P$$\leq d$$f$$f$$d$

¿Cuál es la probabilidad de que un programa particular que no está de acuerdo con f en más de una fracción ϵ de ejemplos sea consistente con los m ejemplos que seleccionamos? Es como máximo ( 1 - ϵ ) m . Nos gustaría considerar que esta probabilidad es como máximo δ / 2 d para que podamos tomar una unión unida a todos los programas 2 d y decir que con una probabilidad de al menos 1 - δ , ningún programa "malo" es consistente con nuestros ejemplos dibujados . Resolviendo, vemos que es suficiente tomar solo m ≥ $P$$f$$\epsilon$$m$$(1-\epsilon)^m$$\delta/2^d$$2^d$$1-\delta$ ejemplos. (es decir, solo linealmente muchos en la complejidad de Kolmogorov def...)

Por cierto, argumentos como este se pueden usar para justificar "Navaja de Occam": dado un número fijo de observaciones, entre todas las teorías que las explican, debe elegir la que tenga la menor complejidad de Kolmogorov, porque hay menos posibilidades de sobreajuste.

Por supuesto, si solo desea verificar un solo programa fijo de esta manera, solo necesita ejemplos ...$O(\log(1/\delta)/\epsilon)$

Aquí hay una respuesta trivial: suponiendo que , entonces necesita saber el valor de f en absoluto | N | puntos para determinar de manera única f . Por lo tanto, el enfoque que bosqueje no le ayuda en absoluto, a menos que sepa de alguna manera que la longitud L del programa es extremadamente corta: mucho más corta que lg | N | bits$L \ge \lg |N|$$f$$|N|$$f$$L$$\lg |N|$

Considere la familia de funciones , donde f i se define como la función f i ( x ) = 1 si i = x y f i ( x ) = 0 si i ≠ x . Observe que la complejidad de Kolmogorov de la computación f i se trata de lg | N | bits, ya que puede codificar el valor de $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$en el código fuente y luego todo lo que necesita es una simple declaración condicional ( extra).$O(1)$

Sin embargo, no puede distinguir de la función todos ceros a menos que lo pruebe en la entrada i . No puede distinguir f i de f j a menos que pruebe en la entrada i o j . Por lo tanto, deberá evaluar f en absoluto | N | entradas, para determinar de forma única con qué f i estamos tratando. (OK, técnicamente, debe evaluarlo en las entradas | N | - 1 , pero lo que sea).$f_i$$i$$f_i$$f_j$$i$$j$$f$$|N|$$f_i$$|N|-1$

Puede hacer que el programa sea arbitrariamente largo. Entonces, dado cualquier programa, puede decidir si su idioma es equivalente al de este programa. No se puede hacer eso por el teorema de Rice.