debugModerate
What is a fixpoint?
Viewed 0 times
fixpointwhatstackoverflow
Problem
Could someone please explain me, what is a fix point?
I caught the minimum explanation about fix point from the website:
After infinitely many iterations we should get to a fix point where
further iterations make no difference. It means that applying one more
ExprF would't change anything -- a fix point doesn't move under ExprF.
It's like adding one to infinity: you get back infinity.
But could not configure it out, what does it mean.
Can please someone explain me in a very easy for a dummy like me.
I caught the minimum explanation about fix point from the website:
After infinitely many iterations we should get to a fix point where
further iterations make no difference. It means that applying one more
ExprF would't change anything -- a fix point doesn't move under ExprF.
It's like adding one to infinity: you get back infinity.
But could not configure it out, what does it mean.
Can please someone explain me in a very easy for a dummy like me.
Solution
Putting it very simply, a fixed point is a point that, when provided to a function, yields as a result that same point. The term comes from mathematics, where a fixed point (or fixpoint, or "invariant point") of a function is a point that won't change under repeated application of the function.
Say that we have function $f(x) = 1/x$. For $x = 2$ we get result $\tfrac12$. If we applied the function again, we find $f(f(2))=2$. It's back to where we started, but we're alternating between these values. However, for $x = 1$ a single application of the function yields $1$ again. This means that $f(1) = f(f(1)) = f(... f(f(1))... )$. The value $1$ is a fixed point for function $f(x) = 1/x$.
A fixed point $x$ for a function $f(x)$ is some point that satisfies the equation $x = f(x)$. There might be no fixed points for a function, one, or multiple. For example, every $x$ is a fixed point for function $f(x) = x$ (which is actually the definition itself).
In computer science, more specifically combinatory logic, a fixed point for a function $f$ is some value that won't change under application of $f$ (or more precisely, that returns an identical value for $f$). For recursion, for example, it would be useless to apply a further recursive call to the function because the returned value would be identical to the argument. Another example of where it might hold meaning is in the gradient descent algorithm, where a fixed point would be the local minimum sought through the descent. Repeated applications of the algorithm would yield the same result every time, at which point we can stop because there will be no further refinement of the result.
Say that we have function $f(x) = 1/x$. For $x = 2$ we get result $\tfrac12$. If we applied the function again, we find $f(f(2))=2$. It's back to where we started, but we're alternating between these values. However, for $x = 1$ a single application of the function yields $1$ again. This means that $f(1) = f(f(1)) = f(... f(f(1))... )$. The value $1$ is a fixed point for function $f(x) = 1/x$.
A fixed point $x$ for a function $f(x)$ is some point that satisfies the equation $x = f(x)$. There might be no fixed points for a function, one, or multiple. For example, every $x$ is a fixed point for function $f(x) = x$ (which is actually the definition itself).
In computer science, more specifically combinatory logic, a fixed point for a function $f$ is some value that won't change under application of $f$ (or more precisely, that returns an identical value for $f$). For recursion, for example, it would be useless to apply a further recursive call to the function because the returned value would be identical to the argument. Another example of where it might hold meaning is in the gradient descent algorithm, where a fixed point would be the local minimum sought through the descent. Repeated applications of the algorithm would yield the same result every time, at which point we can stop because there will be no further refinement of the result.
Context
StackExchange Computer Science Q#76763, answer score: 11
Revisions (0)
No revisions yet.