2 ms·
tl;dr A fixed point p for a function f, is a value so that f(p)=p. A semi-recursive function f is a like a recursive function, except that instead of invoking
by im3w1l 12y ago
tl;dr
A fixed point p for a function f, is a value so that f(p)=p.
A semi-recursive function f is a like a recursive function, except that instead of invoking itself, it invokes some other function provided as an argument to f.
The y-combinator (aka fixed-point-combinator) is a function, that for a function f, finds a fixed point for f.
We can turn a semi-recursive function f into the corresponding recursive function g, by finding a fix point for f, which we can do using the y-combinator.
- tel 12y agoAlso, and a big also, the Y-combinator exists in (untyped) lambda calculus---e.g. all you need is abstraction and application. This came as a shock to Church when he invented it as he wanted to use LC as a language for mathematical logic and fixed point combinators spell out doom for logical purposes. He thus invented the simply typed lambda calculus to banish such constructions.
- deleted 12y ago[deleted]