El combinador Y es un concepto de la programación funcional, tomado del cálculo lambda. Es un combinador de punto fijo. Un combinador de punto fijo GG es una función de orden superior (un funcional, en lenguaje matemático) que, dada una función ff devuelve un punto fijo de ff . En lenguaje matemático,
f(G(f))=G(f)f(G(f))=G(f)
Esto puede considerarse la ecuación definitoria de un combinador de punto fijo.
Tenga en cuenta que ff puede ser una función cuyo rango y dominio son a su vez espacios de funciones -- de hecho este es el uso más común de un combinador de punto fijo: se puede definir una función αα especificando que es el punto fijo de otra función ff y, a continuación, calcular αα como G(f)G(f) .
Como matemáticos estamos acostumbrados a que las funciones tengan nombres, por ejemplo f:x↦x2f:x↦x2 es la función llamada ff que mapea xx a x2x2 . Pero no hay ninguna razón por la que no se pueda tener una función anónima. Como el cálculo lambda trata mucho con ellas, hay una notación especial para ellas:
λx.x2λx.x2
es la función que toma xx a x2x2 para que, por ejemplo (λx.x2)(2)=4(λx.x2)(2)=4 . Cuando no hay ambigüedad, podemos escribir la aplicación de la función por concatenación: (λx.x2)2=4(λx.x2)2=4 y si definimos f=λx.x2f=λx.x2 entonces f2=4f2=4 .
Bien, ahora llegamos al meollo de la cuestión. El combinador Y es una función de orden superior (funcional) definida como
Y=λf.(λx.f(xx))(λx.f(xx))Y=λf.(λx.f(xx))(λx.f(xx))
Puedo seguir a través del álgebra y ver que esto es efectivamente un combinador de punto fijo:
Yg=(λf.(λx.f(xx))(λx.f(xx)))g=(λx.g(xx))(λx.g(xx))=(λy.g(yy))(λx.g(xx))=g(λx.g(xx))(λx.g(xx))=g(Yg)
pero no tengo ninguna intuición en cuanto a por qué funciona, o cómo se le podría haber ocurrido a alguien. Más aún, no veo cómo se puede utilizar en la práctica para calcular funciones como puntos fijos de funcionales.
¿Alguien tiene una buena explicación "intuitiva"?
0 votos
En realidad yo diría x↦x2 está perfectamente bien como función sin nombre. De hecho, personalmente la considero más legible que λx.x2 .
1 votos
Una pregunta sobre la historia de Y combinator: mathoverflow.net/questions/31893/
3 votos
El combinador Y es informalmente bastante similar a la demostración del teorema de recursión de Kleene y a la demostración del teorema del punto fijo en aritmética formal. Aquí hay una pregunta en la que la gente trató de explicar la versión en aritmética: mathoverflow.net/questions/30874/teorema-aritmético-del-punto-fijo/