Recursión
Avanzado Lógica Computación
Falta llamativamente una cosa: los bucles. Las
funciones no tienen nombre, así que nada puede referirse a sí mismo
— no hay ningún f(...) donde f pueda llamar a f. Y sin
embargo todo algoritmo real necesita repetición. La solución es el
truco más famoso del campo.
El término divergente
Empieza con una paradoja. ¿Qué pasa si una función se come a sí misma?
Ω se β-reduce a sí mismo: un bucle infinito en una sola línea. (El paso a paso se rendirá en su límite de seguridad — nunca alcanza una forma normal porque no existe.)
Puntos fijos
Un punto fijo de una función g es un valor X con
g X = X. Ahora supón que existe un combinador mágico
Y con la propiedad:
Alimenta a Y con una función que diga «si n es cero, devuelve 1, si no multiplica n por yo misma de n−1» — y el argumento es la llamada recursiva. Autorreferencia, construida a partir de nada más que sustitución.
El combinador Y
Fíjate en el truco de Ω dentro: x x es otra vez
autoaplicación, pero esta vez envuelta en f (…) de modo
que cada «vuelta» hace un paso de trabajo real antes de recurrir. Ω
diverge; Y hace algo en cada ronda.
Factorial, en principio
Cada pieza de esa línea es algo que tú construiste: IF, ISZERO, MULT de las codificaciones de Church, PRED (la difícil — cabalga sobre los pares) e Y para el bucle. Sin incorporaciones. Sin nombres. Una regla.
A dónde seguir
- El cálculo lambda de la wiki — la lectura profunda completa: historia, equivalencias y las personas
- Alonzo Church — el hombre en la pizarra
- Lecturas adicionales e investigación — las fuentes primarias
(λx.x x) (λx.x x) — el término Ω — ¿qué hace?
Y g se despliega a ___ (lo que vale un paso β)
¿Por qué el cálculo λ necesita un combinador para la recursión?
Escribe el combinador Y: Y = ___
Siguiente: · Anterior: booleanos y pares