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:
- Can PDA detect a language of palindrome strings?
- Is Chomsky’s grammar normal form always decidible?
- Can a regular expression be defined using recursion?
- How to represent OR as FSM?
- Is there a contradiction between the definition of NP as a class of decision problems with polynomial-time verifiers and the fact that problems in the class P also have polynomial-time verifiers?
- Is verifier for class P polynomial?
- Can a Nondeterministic Finite Automaton (NFA) be used to represent the state transitions and actions in a firewall configuration?
- Is using three tapes in a multitape TN equivalent to single tape time t2(square) or t3(cube)? In other words is the time complexity directly related to number of tapes?
- If we have two TMs that describe a decidable language is the equivalence question still undecidable?
- In the case of detecting the start of the tape, can we start by using a new tape T1=$T instead of shifting to the right?
View more questions and answers in EITC/IS/CCTF Computational Complexity Theory Fundamentals