¿Son dos funciones iguales?

Question

[Editar]

La pregunta general parece increíblemente difícil de resolver. Aquí hay una restricción significativa de version de esta pregunta.

---

¿Cómo puedo determinar la igualdad de funciones?

digamos que tenemos

function f() { 
    // black box code. 
} 

function g() { 
    // black box code. 
} 

tomamos una definición matemática de una función. Así

if for all x in domain, f(x) === g(x) then f === g

• ¿Cómo manejamos dominios?
• ¿Cómo podemos determinar si de lo contrario f === g

cheques de código fuente es tonta porque

function f(i) { 
    return i % 2; 
} 

function g(i) { 
    var returnVal = i % 2; 
    return returnVal; 
} 

son obvouisly iguales. Estos son ejemplos triviales, pero se puede imaginar que las funciones más complejas son iguales pero no idénticas.

Puede suponer que f y g no tienen efectos secundarios que nos importen.

---

[Editar]

Como se mencionó @Pointy es probablemente lo mejor para limitar el dominio. En lugar de tener la función de igualdad, intente adivinar el dominio, el usuario de la función de igualdad debería proporcionar un dominio.

No tiene sentido preguntar si dos funciones son iguales sin definir su dominio en alguna parte.

Para simplemente el problema podemos asumir al dominio es el conjunto de todos los enteros o un subconjunto de que lo que necesitamos una función:

function equal (f, g, domain) { 

} 

La estructura del dominio es irrelevante y puede ser hecho para hacer el problema es lo más fácil posible También puede suponer que f y g actúan muy bien en el dominio de los enteros y no bloquean & burn.

¡Usted puede suponer que f y g se detienen!

Una vez más @Pointy señala un buen ejemplo de funciones no deterministas

¿Y si nos limitamos f & g a ser determinista.

Answer 1

Esto es imposible de acuerdo a Rice's theorem:

En teoría de la computabilidad, teorema de Rice que, para cualquier propiedad no trivial de funciones parciales, no hay general y método eficaz para decidir si un algoritmo calcula una función parcial con esa propiedad.

Si se restringe el dominio de las funciones a ser finito, entonces se puede verificar trivialmente si ∀x: f (x) = g (x) utilizando la fuerza bruta, pero esto no es posible con un dominio infinito.

Answer 2

Es imposible crear un mecanismo que, dadas dos funciones, siempre pueda determinar si siempre devolverá los mismos valores.

Esto se debe al problema que está tratando de resolver que es equivalente al Halting problem. ^{(source; página 4)}

Por supuesto, usted podría hacer que la heurística para hacer esto, pero siempre habría casos en los que no serían capaces de determinarla.

Suponiendo que se limite a las funciones de detención en dominio limitado, todavía no es trivial para determinar rápidamente. Si suponemos que la entrada está en {1, ..., n} y la salida está en {1, ..., m}, hay m ⁿ posibles funciones (para cada entrada, hay n salidas posibles). Si muestras k puntos, lo reduces, y haces que la probabilidad de que sean iguales es mayor, pero todavía hay m ^(n-k) diferentes funciones que podría ser. Por lo tanto, podría determinar si es probable que son iguales con bastante rapidez, pero para estar seguro, debería verificar todos los posibles valores de entrada.

Si desea hacerlo de otra manera que por muestreo, creo que tendrá que hacer algún tipo de static analysis en el código fuente de las funciones, que es casi trivial.

Además, si el dominio no es finito, Rice's theorem impide que exista dicho algoritmo.

Answer 3

No hay forma de hacerlo en general. Puede probar ambas funciones para obtener una muestra aleatoria de entradas y verificar que sean iguales en esos valores específicos, pero en general no es factible probar todas las entradas posibles.

Answer 4

sistemas de verificación de prueba como Coq y Agda pueden ser capaces de hacer lo que estás buscando.

Answer 5

Suponiendo que está hablando de una familia de funciones de JavaScript que están limitadas a un argumento entero, y que no tienen efectos secundarios externos visibles, todavía creo que generalmente no será posible determinar la igualdad. Considere esto:

function a(n) { 
    var today = new Date(); 
    if (today.getFullYear() === 2012 && today.getMonth() === 1 && today.getDate() === 3) 
    return 0; 
    return n * n; 
} 

Esa función se ve un poco como

function b(n) { return n * n; } 

Excepto el 3 de febrero de 2012, cuando se verá exactamente igual:

function c(n) { return 0; } 

Si usted está realmente hablando acerca de una pieza práctica de software real para realizar dicho análisis, y si realmente no tiene mucho control sobre los detalles de las funciones que se probarán, no parece posible. Quizás pueda construir un conjunto de "reglas" que las funciones deben seguir, pero aun así la perspectiva de determinar la igualdad sin probar cada valor en el dominio parece bastante remota.

editar — Acabo de pensar en algo: ¿y si sus dos funciones devuelven funciones? Ahora, para determinar si f == g, primero tiene que averiguar si las funciones devueltos por f (n) para todos n son iguales a las funciones devueltos por g (n) para todos n. Hmm ...