36 votos

¿Puede alguien explicar el Y Combinator?

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:xx2f:xx2 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 xx2 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/

24voto

Pandian Puntos 1

El Y es una función que toma una función f y devuelve algo aplicado a sí mismo (concretamente λx.f(xx) ). Así que si queremos hacer Y(f) un punto fijo de f , Y(f) tiene que ser igual a f(Y(f)) . Por lo tanto, queremos que algunos a tal que aa=f(aa) . Ahora, a tiene acceso a sí mismo (se aplica a sí mismo). Por ello, podemos crear directamente un a . aa=f(aa) a=λa.f(aa) a=λx.f(xx) Y=λf.aa=λf.(λx.f(xx))(λx.f(xx)) Esencialmente, al aplicar a a sí mismo, está dando a una referencia a sí mismo, lo que le permite utilizarlo de forma recursiva. Sin embargo, a es sólo un valor intermedio - no es la función recursiva en sí misma, ya que todavía necesita una referencia a sí misma para hacer la recursión. La página web Y elimina completamente esta necesidad al encontrar el punto fijo, dando a una función su forma final y recursiva.

0 votos

¿Cómo se pasa del primer paso al segundo?

0 votos

Ohh ok lo entiendo.

5 votos

¿Por qué queremos específicamente un a tal que aa=f(aa) ¿Por qué no? a=f(a) o aaa=f(aaa) ?

13voto

ciberandy Puntos 104

Si conoces el argumento diagonal de Cantor, puedes descubrir el combinador Y.

Teorema de Cantor Dejemos que A,B sean conjuntos y supongamos que existe una función sin punto fijo f:BB . Entonces, no hay suryección A(AB) .

Observación. Normalmente, B es un 2 -de elementos, de modo que AB=P(A) y f es la función que invierte los dos valores.

Prueba. Dejemos que g:A(AB) sea una función. Encontraremos alguna función h:AB tal que h no es a imagen y semejanza de g .

Utilizamos el argumento diagonal : definir h que será dada por h(a)=f(g(a)(a)). Entonces, si a es cualquier elemento de A tenemos que h(a)=f(g(a)(a))g(a)(a), (ya que f es libre de puntos fijos), y por lo tanto que hg(a) . Por lo tanto, ya que a era arbitraria, h debe estar fuera de la imagen de g .

Ahora bien, no se dice así a menudo, pero el argumento diagonal de Cantor se aplica en realidad a toda clase de teorías de tipos distintas de la de conjuntos y funciones, incluso a la no tipificada λ -Cálculo. Sin embargo, las consecuencias son muy diferentes.

Escribe Λ para la recopilación de todos los λ -términos. (Técnicamente, estamos empleando el truco de pensar en los λ -cálculo como un tipo λ -cálculo con un solo tipo Λ satisfaciendo ΛΛ=Λ .)

Queremos tomar A=B=Λ en nuestro argumento anterior. Pero, ¿qué debería hacer una función de λ -términos a λ -términos ser? Pues no es más que un λ -¡Término mismo! Por lo tanto, hay absolutamente es una sobreproyección Λ(ΛΛ). Es la función de identidad.

¿No contradice esto el argumento de Cantor? La respuesta es no - ya que la conclusión del argumento es falsa, entonces una de las hipótesis debe ser falsa. Y en este caso, la única hipótesis que puede fallar es la existencia de una función sin punto fijo ΛΛ .

Así es - no hay ningún punto fijo libre λ -Término. Pero como el argumento anterior es completamente constructivo, podemos hacerlo aún mejor: podemos construir ese punto fijo nosotros mismos llevando a cabo el argumento a la inversa.

Primero hagamos esto en general, y luego veremos cómo funcionan las cosas en el modo no tipado λ -Cálculo. Todo en el siguiente argumento surge como resultado directo de escribir los pasos de la prueba anterior a la inversa.

Contrapositivo al teorema de Cantor Dejemos que g:A(AB) sea una suryección. Entonces no hay ninguna función libre de puntos fijos f:BB .

Prueba. Considere la función h:AB dado por h(a)=f(g(a)(a)). Desde g es suryente, hay algún a tal que g(a)=h . Entonces tenemos g(a)(a)=h(a)=f(g(a)(a)), y por lo tanto g(a)(a) es un punto fijo de la función f .

¿Cómo funciona esto en el caso de la versión no tipificada de λ -¿Cálculo? Pues bien, esta vez nuestra proyección g es la función de identidad, por lo que h se convierte en h=λx.f(xx). Desde g es la función de identidad, podemos elegir a=h . Entonces nuestra expresión final para el punto fijo es hh=(λx.f(xx))(λx.f(xx)). Y, en efecto, tenemos (λx.f(xx))(λx.f(xx))=f((λx.f(xx))(λx.f(xx))). ¡Hay más! Podemos λ -abstraer el f para darnos un propósito general combinador de puntos fijos . λf.(λx.f(xx))(λx.f(xx)) Hola, viejo amigo.

1 votos

2 votos

Esto es raro y la mejor respuesta IMO. Mientras que la mayoría de los tutoriales enseñan por qué Y envía una función a punto fijo, esto en realidad te enseña a reinventar Y ¡!

6voto

El Y combinador puede definirse también de forma Turing. Utilicemos nombres de variables menos formales pero más descriptivos para definir el combinador: A=λself.λf.f (self self f);Y=A A.

El A se puede considerar como una función que se toma a sí misma como primer argumento y la función objetivo, cuyo punto fijo se quiere encontrar, como segundo. Devuelve la función aplicada a A A f tal y como queríamos.

Entonces, un combinador arbitrario F que se define en términos de sí mismo como F x y=F y x F puede definirse en términos de Y y algún otro combinador Fr . Específicamente, F x y=F y x F equivale a F=λx.λy.F y x F, que a su vez se deduce de F=(λself.λx.λy.self y x self)F. Por último, llamemos a la subexpresión resultante Fr=λself.λx.λy.self y x self. Entonces F=Y Fr .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X