If the value in the fixed point definition is the lim of the repeated application of the function can we call it still a fixed point? In the example shown if instead of 4->4 we have 4->3.9, 3.9->3.99, 3.99->3.999, … is 4 still the fixed point?
The concept of a fixed point in the context of computational complexity theory and recursion is an important one. In order to answer your question, let us first define what a fixed point is.
In mathematics, a fixed point of a function is a point that is unchanged by the function. In other words, if we apply the function to the fixed point, the result will be the same point. More formally, for a function f and a point x, if f(x) = x, then x is a fixed point of f.
Now, let's consider the scenario you have presented. You have a sequence of values where each value is obtained by repeatedly applying a function. In the example given, the function is mapping 4 to 3.9, 3.9 to 3.99, 3.99 to 3.999, and so on. The question is whether 4 is still a fixed point in this case.
To determine this, we need to check if applying the function to 4 results in 4 itself. Let's do the calculation:
f(4) = 3.9
f(f(4)) = f(3.9) = 3.99
f(f(f(4))) = f(f(3.9)) = f(3.99) = 3.999
…
As we can see, the repeated application of the function does not converge to 4. Instead, it approaches a value very close to 4, but never actually reaches it. Therefore, in this particular case, 4 is not a fixed point of the function.
It is worth noting that the concept of a fixed point is closely related to the idea of convergence. In order for a fixed point to exist, the repeated application of the function must converge to a specific value. In this case, the sequence of values approaches 4, but it never reaches it. Therefore, we cannot consider 4 as a fixed point in this scenario.
If the value in the fixed point definition is the limit of the repeated application of the function, we can call it a fixed point only if the sequence of values converges to that value. In the example you provided, where the sequence approaches but never reaches 4, 4 is not a fixed point.
Other recent questions and answers regarding The Fixed Point Theorem:
- Provide an example of a computable function T and explain how the recursion theorem guarantees the existence of a fixed point for this function.
- Explain the recursion theorem and its relevance to fixed points in the context of transformations on Turing machines.
- What is the relationship between fixed points and computable functions in computational complexity theory?
- How can fixed points be understood in terms of attractors? Provide an example to illustrate your answer.
- Define a fixed point in the context of computational complexity theory and explain its significance.