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 EITC/IS/CCTF Computational Complexity Theory Fundamentals:
- Are regular languages equivalent with Finite State Machines?
- Is PSPACE class not equal to the EXPSPACE class?
- Is algorithmically computable problem a problem computable by a Turing Machine accordingly to the Church-Turing Thesis?
- What is the closure property of regular languages under concatenation? How are finite state machines combined to represent the union of languages recognized by two machines?
- Can every arbitrary problem be expressed as a language?
- Is P complexity class a subset of PSPACE class?
- Does every multi-tape Turing machine has an equivalent single-tape Turing machine?
- What are the outputs of predicates?
- Are lambda calculus and turing machines computable models that answers the question on what does computable mean?
- Can we can prove that Np and P class are the same by finding an efficient polynomial solution for any NP complete problem on a deterministic TM?
View more questions and answers in EITC/IS/CCTF Computational Complexity Theory Fundamentals