¿Es posible demostrar que una función es idempotente?

12

¿Es posible usar tipos estáticos o dependientes para demostrar que una función es idempotente?

He buscado en Google y en varios lugares en StackOverflow / StackExchange la respuesta sin suerte. Lo más cercano que encontré fue esta conversación sobre Idris: https://groups.google.com/forum/#!topic/idris-lang/yp7vrspChRg

Desafortunadamente, esa discusión está un poco sobre mi cabeza.

haskell bmaddy
fuente
3
No estoy publicando esto como respuesta porque no estoy 100% seguro, pero creo que esto es imposible debido al Teorema de Rice .
cabeza de jardín
44
Esta es una pregunta fascinante, y mi intuición indica que esto debería ser posible en un lenguaje restringido, no completo de Turing. Sin embargo, los programadores se centran en las preguntas relacionadas con el ciclo de vida del desarrollo de software (consulte el centro de ayuda para más detalles), mientras que esta parece ser una pregunta de informática. El sitio de Ciencias de la Computación puede ser más adecuado y generar mejores respuestas.
amon
2
El teorema de @gardenhead Rice establece que dada cualquier propiedad que pueda tener el comportamiento de un programa, a veces es imposible determinar si un programa tiene o no esa propiedad. Hay una gran diferencia entre "esto es a veces imposible" y "esto es imposible".
Tanner Swett
2
Mi último comentario fue bastante vago. En cualquier caso, esto es lo que tiene que decir el teorema de Rice: no existe un algoritmo que clasifique correctamente todas las funciones como idempotentes o no idempotentes. Sin embargo, todavía hay algoritmos útiles que clasifican algunas funciones como idempotentes o no.
Tanner Swett
2
El OP preguntó acerca de probar que una función es idempotente, no tener un algoritmo que clasifique las funciones como idempotente o no. La principal diferencia es que una prueba puede ser escrita por una persona. En cuanto a la integridad de Turing, de hecho no es un problema .
gallais

Respuestas:

3

Para ciertas funciones lo es. Especialmente cuando conoces la función ;-)

Si quiere decir con su pregunta "¿hay un algoritmo para decidir automáticamente si una función arbitraria es idempotente o no", la respuesta es no, debido a los teoremas ya mencionados en los comentarios. Sin embargo, para clases específicas de funciones, uno puede, en teoría, decidir muy fácilmente si la función es idempotente o no. Por ejemplo, si la función es pura (significa: sin efectos secundarios), y uno sabe que siempre devuelve un valor en una cantidad de tiempo finita para cualquier entrada dada, entonces la idempotencia se puede decidir simplemente probando si hay f(f(x))=f(x)alguna entrada posible xa la función. No es que esto sea muy eficiente, podría ejecutarse hasta el final del universo.

Entonces, si esa no es la respuesta que estaba buscando, escriba una pregunta mejor, actualmente no está claro qué es lo que realmente está buscando.

Doc Brown
fuente
Gracias por la respuesta. La capacidad de "decidir automáticamente" era exactamente lo que estaba buscando.
bmaddy
2
Para ampliar la declaración 'para ciertas funciones es' : la idempotencia se puede probar para cualquier función que solo acepte una cantidad finita de entradas (probándolas todas), o un tipo de entrada que se define de forma recursiva (como natural números o listas vinculadas), lo que significa que solo necesita probar que la idempotencia es verdadera para los casos base y los casos recurrentes.
Qqwy