4 ms·

I have no background in combinatory logic, and so I've predictably never understood fixed-point combinators: 1. Every function has a fixed point. 2. A fixed-p

I have no background in combinatory logic, and so I've predictably never understood fixed-point combinators: 1. Every function has a fixed point. 2. A fixed-point combinator will compute it. So what is the fixed point of f(x) = x + 1? Also why doesn't this give us mathematical superpowers? Define f(x) = x iff x is a non-trivial zero of the Riemann zeta function...

LudwigNagasena 3y ago
Every function in untyped lambda calculus has a fixed point. The fixed point of f(x) = x + 1 is garbage that cannot be decoded back into a number.
- ridiculous_fish 3y ago
  We often extend arithmetic with new sorts of numbers to solve previously unsolvable equations like sqrt(-1) - is finding a fixed point of f(x) = x + 1 in this tradition? Does it point to an extension of arithmetic? Also I find this confusing: "Applied to a function with one variable, the Y combinator usually does not terminate" What does it mean for a function to terminate? Is it like the limit of a series?
  - LudwigNagasena 3y ago
    > Does it point to an extension of arithmetic? Well, the fixed point of f(x)=x+1 can be interpreted as infinity. So kind of yes? > What does it mean for a function to terminate? Lambda calculus is a formal system that describes computation. So it literally means termination like when a computer program finishes running / halts. You have text which describes your program and you apply a few rewriting rules until you can’t. If at some point you can’t apply any more rewriting rules, you’ve reached a final state, your program has terminated. I suppose, when you apply Y combinator eg to f(x)=x+1 then you are just going to get x+1+1+… and so on as you keep applying rewriting rules.
defrost 3y ago
1. No. - https://en.wikipedia.org/wiki/Fixed-point_combinator https://en.wikipedia.org/wiki/Fixed-point_combinator In a generic context a fixed point combinator will only return a fixed point of a function if one exists. 2. No. (see: 1. above) Your confusion stems from the usual domain of application to function spaces where every function has a fixed point (ie. not all function spaces, just those that are made up of functions with at least one fixed point). From the link above: In the classical untyped lambda calculus, every function has a fixed point.
- ridiculous_fish 3y ago
  What would be the fixed point of f(x) = x + 1 in the classical untyped lambda calculus? Sorry if this question is really basic, but it's honest and I find it fascinating.
  - bmacho 3y ago
    I think in untyped lambda calculus you work with expressions, so you take your f function (somehow represented as an expression in untyped lambda calculus), you put that in a fixed point combinator, and the resulting expression is a fixed point of your f function. It most certainly won't be a representation of a number->number function, but a general element of untyped lambda calculus nevertheless. It is somehow similar how you take square root of a negative number on the Complex plane. You represent your negative number as a complex number (r \mapsto r + 0i), then you can take a square root of it, but that won't correspond to a representation of a real number.
  - nightlyherb 3y ago
    Using church numerals[1], right_incr(n) = g => y => n(g)(g(y)) and using the following shorter fixed-point combinator[2], X(f) = ( a => a(a) )( x => f(x(x)) ) I get this junk: X(right_incr) = ( a => a(a) )( x => g => y => x(x)(g)(g(y)) ) = ( x => g => y => x(x)(g)(g(y)) ) ( x => g => y => x(x)(g)(g(y)) ) X(right_incr)(g)(y) = let f = ( x => g => y => x(x)(g)(g(y)) ) in f(f)(g)(y) = let .. in f(f)(g)(g(y)) = let .. in f(f)(g)(g(g(y))) = ... Which, as you can see, only gets more complex when I try to transform it. [1] https://en.m.wikipedia.org/wiki/Church_encoding https://en.m.wikipedia.org/wiki/Church_encoding [2] https://en.m.wikipedia.org/wiki/Fixed-point_combinator#Other_fixed-point_combinators https://en.m.wikipedia.org/wiki/Fixed-point_combinator#Other...
gregfjohnson 3y ago
Here is a way to look at this in concrete terms, using python. An important class of lambda terms are those for which there is no normal form. In computational terms, these are terms that would cause you to go into an infinite loop if you tried to apply the conversion rules of lambda calculus "until" you reached a normal form (i.e., a lambda term for which there are no beta redexes). Canonical example: >>> (lambda fn: fn(fn)) (lambda fn: fn(fn)) Traceback (most recent call last): ... RecursionError: maximum recursion depth exceeded For many functions, the fixed point turns out to be a variant of this divergent ("infinite loop") expression. Assuming a definition of "+" that preserves divergence, then "infinite_loop" is a fixed point of f(n) = n + 1. An encoding of the fixed point operator in python is: y = lambda Input_Fn:((lambda f: lambda n: Input_Fn(f(f))(n)) \ (lambda f: lambda n: Input_Fn(f(f))(n))) For fun, we will play a little bit fast and loose, and combine standard integer arithmetic with lambda calculus. Here is a functional whose fixed point is the factorial function: >>> fac1 = lambda f: lambda n: ((n > 1) and n * f(n-1) or 1) Example evaluation: >>> y(fac1)(4) 24 If we use the standard encoding of the integers as Church numerals, two would be represented as: two = lambda successor: lambda zero: successor(successor(zero)) The "add_one" function becomes: add_one = lambda n: lambda successor: lambda zero: successor(n(successor)(zero)) For concreteness (and human intuition), we can define int_zero, int_successor = 0, (lambda n: n+1) >>> add_one(two)(int_successor)(int_zero) 3 What is a fixed point of the add_one function? >>> y(add_one)(two)(int_successor)(int_zero) Traceback (most recent call last): ... RecursionError: maximum recursion depth exceeded
- gregfjohnson 3y ago
  One additional comment, regarding the "fac1" functional above: >>> fac1 = lambda f: lambda n: ((n > 1) and n * f(n-1) or 1) If you happened to have a function "my_fac" that calculates the factorial function, and you applied "fac1" above to that function, you would get a new implementation of the factorial function, that calls your my_fac function internally. In other words, "my_fac" is a fixed point of fac1: >>> fac1(my_fac) is the same function as my_fac.
QuesnayJr 3y ago
If it doesn't really have a fixed point you get a function that never terminates. In denotational semantics you define a special value, "bottom" that means "undefined", and the fixed point is bottom. And it's not all functions, just computable ones. But if there's algorithm to compute non-trivial zeroes of the zeta function, it would just never terminate if there aren't any.
cryptonector 3y ago
It's a tool for constructing recursive functions when the language does not support a function calling itself by name. That happens if, for example, the language won't finish compiling the function and making a symbol with its name available for binding/linking until it's done compiling it, so.. in such a case you can't recurse by name. So what to do? Well, you make your recursive function take an extra parameter that is also a function value, and then you'll define a function that calls your wannabe-recursive function with.. itself as the argument function so that it can then call itself as intended. It's quite simple when thought of that way. "Fixed point" can seem like a high falutin' term of art, and that's because it is -- we love our terms of art, but we also need to be able to explain them. `fix` then is a function which takes a function value as an argument and which returns a new function value which is a function that calls the argument to `fix` with that same argument as its first argument. Reading that I realize it's hard to express this in pure natural language -- one has to introduce symbols for naming the various functions.
deleted 3y ago
[deleted]
mrkeen 3y ago
I don't understand the formal side of things, but I've used Y before, so here goes: In the lambda calculus, functions are nameless. Recursion is when an expression refers to itself by name. The Y combinator gives you recursion despite the contradiction in my last two sentences. > So what is the fixed point of f(x) = x + 1? We don't have names, so what is the fixed point of (λx. x + 1)? Introduce a new variable into the expression's body to act as the expression's name, and also include it as the first parameter: (λf x. x + 1) (Your function did not refer to itself which is why there's no f in the body of the above expression). Now let's take the ingredients and put them together. I'm including an 'input' so that we can converge on an output: Y = (λg. (λh. g (h h)) (λh. g (h h))) fixf = (λf x. x + 1) input = 3 Y fixf input = (λg. (λh. g (h h)) (λh. g (h h))) (λf x. x + 1) 3 Now we just apply those lambdas to their terms and see what we end up with: (λg. (λh. g (h h)) (λh. g (h h))) (λf x. x + 1) 3 ^ | g | (λh. (λf x. x + 1) (h h)) (λh. (λf x. x + 1) (h h)) 3 ^ | h | (λf x. x + 1) ((λh. (λf x. x + 1) (h h)) (λh. (λf x. x + 1) (h h))) 3 ^ | f | (λx. x + 1) 3 ^ |x| 4
tromp 3y ago
The fixed point of any function f = f (f (f (f .... so for f(x)=1+x it is 1+ (1+ (1+ (1+ ... , an infinite sum. This is correct in the sense that 1 + infinity = infinity, but in practice this could result in an infinite loop or stack overflow. For f(x)=x+1 it's the reverse ...) +1) +1) +1 which behaves similarly.

LudwigNagasena 3y ago

Every function in untyped lambda calculus has a fixed point. The fixed point of f(x) = x + 1 is garbage that cannot be decoded back into a number.

ridiculous_fish 3y ago
We often extend arithmetic with new sorts of numbers to solve previously unsolvable equations like sqrt(-1) - is finding a fixed point of f(x) = x + 1 in this tradition? Does it point to an extension of arithmetic? Also I find this confusing: "Applied to a function with one variable, the Y combinator usually does not terminate" What does it mean for a function to terminate? Is it like the limit of a series?
- LudwigNagasena 3y ago
  > Does it point to an extension of arithmetic? Well, the fixed point of f(x)=x+1 can be interpreted as infinity. So kind of yes? > What does it mean for a function to terminate? Lambda calculus is a formal system that describes computation. So it literally means termination like when a computer program finishes running / halts. You have text which describes your program and you apply a few rewriting rules until you can’t. If at some point you can’t apply any more rewriting rules, you’ve reached a final state, your program has terminated. I suppose, when you apply Y combinator eg to f(x)=x+1 then you are just going to get x+1+1+… and so on as you keep applying rewriting rules.

defrost 3y ago

1. No. - https://en.wikipedia.org/wiki/Fixed-point_combinator https://en.wikipedia.org/wiki/Fixed-point_combinator In a generic context a fixed point combinator will only return a fixed point of a function if one exists. 2. No. (see: 1. above) Your confusion stems from the usual domain of application to function spaces where every function has a fixed point (ie. not all function spaces, just those that are made up of functions with at least one fixed point). From the link above: In the classical untyped lambda calculus, every function has a fixed point.

ridiculous_fish 3y ago
What would be the fixed point of f(x) = x + 1 in the classical untyped lambda calculus? Sorry if this question is really basic, but it's honest and I find it fascinating.
- bmacho 3y ago
  I think in untyped lambda calculus you work with expressions, so you take your f function (somehow represented as an expression in untyped lambda calculus), you put that in a fixed point combinator, and the resulting expression is a fixed point of your f function. It most certainly won't be a representation of a number->number function, but a general element of untyped lambda calculus nevertheless. It is somehow similar how you take square root of a negative number on the Complex plane. You represent your negative number as a complex number (r \mapsto r + 0i), then you can take a square root of it, but that won't correspond to a representation of a real number.
- nightlyherb 3y ago
  Using church numerals[1], right_incr(n) = g => y => n(g)(g(y)) and using the following shorter fixed-point combinator[2], X(f) = ( a => a(a) )( x => f(x(x)) ) I get this junk: X(right_incr) = ( a => a(a) )( x => g => y => x(x)(g)(g(y)) ) = ( x => g => y => x(x)(g)(g(y)) ) ( x => g => y => x(x)(g)(g(y)) ) X(right_incr)(g)(y) = let f = ( x => g => y => x(x)(g)(g(y)) ) in f(f)(g)(y) = let .. in f(f)(g)(g(y)) = let .. in f(f)(g)(g(g(y))) = ... Which, as you can see, only gets more complex when I try to transform it. [1] https://en.m.wikipedia.org/wiki/Church_encoding https://en.m.wikipedia.org/wiki/Church_encoding [2] https://en.m.wikipedia.org/wiki/Fixed-point_combinator#Other_fixed-point_combinators https://en.m.wikipedia.org/wiki/Fixed-point_combinator#Other...

gregfjohnson 3y ago

Here is a way to look at this in concrete terms, using python. An important class of lambda terms are those for which there is no normal form. In computational terms, these are terms that would cause you to go into an infinite loop if you tried to apply the conversion rules of lambda calculus "until" you reached a normal form (i.e., a lambda term for which there are no beta redexes). Canonical example: >>> (lambda fn: fn(fn)) (lambda fn: fn(fn)) Traceback (most recent call last): ... RecursionError: maximum recursion depth exceeded For many functions, the fixed point turns out to be a variant of this divergent ("infinite loop") expression. Assuming a definition of "+" that preserves divergence, then "infinite_loop" is a fixed point of f(n) = n + 1. An encoding of the fixed point operator in python is: y = lambda Input_Fn:((lambda f: lambda n: Input_Fn(f(f))(n)) \ (lambda f: lambda n: Input_Fn(f(f))(n))) For fun, we will play a little bit fast and loose, and combine standard integer arithmetic with lambda calculus. Here is a functional whose fixed point is the factorial function: >>> fac1 = lambda f: lambda n: ((n > 1) and n * f(n-1) or 1) Example evaluation: >>> y(fac1)(4) 24 If we use the standard encoding of the integers as Church numerals, two would be represented as: two = lambda successor: lambda zero: successor(successor(zero)) The "add_one" function becomes: add_one = lambda n: lambda successor: lambda zero: successor(n(successor)(zero)) For concreteness (and human intuition), we can define int_zero, int_successor = 0, (lambda n: n+1) >>> add_one(two)(int_successor)(int_zero) 3 What is a fixed point of the add_one function? >>> y(add_one)(two)(int_successor)(int_zero) Traceback (most recent call last): ... RecursionError: maximum recursion depth exceeded

gregfjohnson 3y ago
One additional comment, regarding the "fac1" functional above: >>> fac1 = lambda f: lambda n: ((n > 1) and n * f(n-1) or 1) If you happened to have a function "my_fac" that calculates the factorial function, and you applied "fac1" above to that function, you would get a new implementation of the factorial function, that calls your my_fac function internally. In other words, "my_fac" is a fixed point of fac1: >>> fac1(my_fac) is the same function as my_fac.

QuesnayJr 3y ago

If it doesn't really have a fixed point you get a function that never terminates. In denotational semantics you define a special value, "bottom" that means "undefined", and the fixed point is bottom. And it's not all functions, just computable ones. But if there's algorithm to compute non-trivial zeroes of the zeta function, it would just never terminate if there aren't any.

cryptonector 3y ago

It's a tool for constructing recursive functions when the language does not support a function calling itself by name. That happens if, for example, the language won't finish compiling the function and making a symbol with its name available for binding/linking until it's done compiling it, so.. in such a case you can't recurse by name. So what to do? Well, you make your recursive function take an extra parameter that is also a function value, and then you'll define a function that calls your wannabe-recursive function with.. itself as the argument function so that it can then call itself as intended. It's quite simple when thought of that way. "Fixed point" can seem like a high falutin' term of art, and that's because it is -- we love our terms of art, but we also need to be able to explain them. `fix` then is a function which takes a function value as an argument and which returns a new function value which is a function that calls the argument to `fix` with that same argument as its first argument. Reading that I realize it's hard to express this in pure natural language -- one has to introduce symbols for naming the various functions.

deleted 3y ago

[deleted]

mrkeen 3y ago

I don't understand the formal side of things, but I've used Y before, so here goes: In the lambda calculus, functions are nameless. Recursion is when an expression refers to itself by name. The Y combinator gives you recursion despite the contradiction in my last two sentences. > So what is the fixed point of f(x) = x + 1? We don't have names, so what is the fixed point of (λx. x + 1)? Introduce a new variable into the expression's body to act as the expression's name, and also include it as the first parameter: (λf x. x + 1) (Your function did not refer to itself which is why there's no f in the body of the above expression). Now let's take the ingredients and put them together. I'm including an 'input' so that we can converge on an output: Y = (λg. (λh. g (h h)) (λh. g (h h))) fixf = (λf x. x + 1) input = 3 Y fixf input = (λg. (λh. g (h h)) (λh. g (h h))) (λf x. x + 1) 3 Now we just apply those lambdas to their terms and see what we end up with: (λg. (λh. g (h h)) (λh. g (h h))) (λf x. x + 1) 3 ^ | g | (λh. (λf x. x + 1) (h h)) (λh. (λf x. x + 1) (h h)) 3 ^ | h | (λf x. x + 1) ((λh. (λf x. x + 1) (h h)) (λh. (λf x. x + 1) (h h))) 3 ^ | f | (λx. x + 1) 3 ^ |x| 4

tromp 3y ago

The fixed point of any function f = f (f (f (f .... so for f(x)=1+x it is 1+ (1+ (1+ (1+ ... , an infinite sum. This is correct in the sense that 1 + infinity = infinity, but in practice this could result in an infinite loop or stack overflow. For f(x)=x+1 it's the reverse ...) +1) +1) +1 which behaves similarly.