Re:Fixed-Point Combinator
by LudwigNagasena on Saturday February 24, 2024 @01:24AM
(#39489581)
> 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.
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.