Fixed point, what does it mean in the world of computer science

Question

I keep coming across references to fixed point in questions and answers at stackexchange and I look up the meaning on the web obviously finding reference at sites such as Wikipedia. However none of the references really answer my question of what is a fixed point and what does it mean in the world of computer science.

---

EDIT

After 8 years this finally popped into my head.

How would you explain fixed point to a kindergartner?

A fix point is when you do the same thing again and again and nothing changes. So if your room is messy and you clean it, it is now at a fixed point because if you clean it again it is still clean.

I know there is a joke or comic in there somewhere but I don't have my comedian hat on today.

Answer 1

In computer science, the arguably most prominent use of fixed-points is in lattice theory¹. A lattice is a partially ordered set $(S, \leq)$ with the additional property that given any two elements $x,y \in S$, the set $\{x,y\}$ has both a supremum and infimum (in $S$).

Now you often consider monotone functions $f$ on this lattice which "converge", that is for some $x \in S$ you have $f(x)=x$. Important results in this area are Kleene's fixed-point theorem and the Knaster-Tarski theorem.

A prominent example is the lattice $(2^A,\subseteq)$ for $A$ some set, and $f$ induced by an inductive definition. For example, let $A = \{a,b\}^*$ and we define a language $L \in 2^{\{a,b\}^*}$ by

$\qquad \begin{align} \phantom{w \in L} &\phantom{\implies} \varepsilon, a \in L \\ aw \in L &\implies baw \in L \\ bw \in L &\implies abw, bbw \in L \end{align}$

This inductive definition corresponds to the monotone function

$\qquad \displaystyle f(A) = \{\varepsilon, a\} \cup A \cup \{baw \mid aw \in L\} \cup \{abw, bbw \mid bw \in L\}$

By Knaster-Tarski theorem, we know $f$ has a smallest fixpoint which is a supremum of all smaller "intermediate results" (which correspond to finitely often applying the constructors of the inductive definition), and that smallest fixpoint is indeed $L$.

By the way, the largest fixpoint also has uses; see here for an example.

---

In recursion theory, there is another fixed-point theorem, also due to Kleene. It says²,

Let $\varphi$ a Gödel numbering³ and $ r :\mathbb{N} \to \mathbb{N}$ a total, computable function (intuition: a compiler). Then there is $i \in \mathbb{N}$ such that $\varphi_{r(i)}=\varphi_i$.

In fact, there are even infinitely many such $i$; if there where only finitely many, we could patch $r$ (by table-lookup) to not have fixed-points, contradicting the theorem.

---

1. Everybody uses it every day, even if you don't realise it.
2. I don't like that Wikipedia article; you are probably better off checking a genre book.
3. A special kind of function numbering. For intuition, think of it as a (Turing-complete) programming language.

Answer 2

Let me elaborate a bit on meisterluk's answer: Imagine we are trying to define the factorial function: remember the definition of the factorial function:

fact 0     = 1
fact (n+1) = n*(fact n)

Now in some PL frameworks (namely the $\lambda$-calculus), it isn't immediately obvious how to define such a function. However, it may be easy to define the following higher-order function, so-called because it takes as input another function and a natural number

Fact f 0     = 1
Fact f (n+1) = n * (f n)

There is no use of recursion in this function definition. However, if there was some way of finding the fix-point of Fact, that is, a function $\phi$ such that $$\mbox{Fact}\ \phi\ n ~=~ \phi\ n$$ for every $n$, then it is easy to check that $\phi$ is indeed an implementation of the factorial function.

Now in frameworks like the $\lambda$-calculus, one can show that all fixed-points of this nature do, in fact, exist, which makes it clear that you can use it as a general programing language.

There are many other uses to the notion of fixed-points in computer science, but most boil down to the one I showed above, i.e. prove that certain fixed-points exist to be able to show that certain functions or constructs are well-defined in your framework (here we have shown that the factorial function exists).

Answer 3

A fixed point of a function $f: A \to A$ is an element $x$ for which $f(x)$ is equal to $x$. For example, the function $x^2$ has two fixed points, which are the values $0$ and $1$, and the function $x^3$ has three fixed points. Mathematically that is the definition.

Now, depending on the mathematical structure you are dealing with, there are very many different reasons to be interested in fixed points. For example, if you consider a dynamic system that looks at the state of the world and changes it (like a thermostat) then a fixed point corresponds to a stable configuration. If you think of games in the mathematical sense of game theory, fixed points correspond to equillibria, if you think of the the behaviour of an optimization routine that iteratively improves its solution, a fixed point corresponds to an optimal solution. So the mathematical notion of a fixed point has a lot of applications in a lot of different contexts.

A very common, and fundamental application of fixed points in computer science is to mathematically model loops and recursive programs. If we try to model a program as a mathematical function, both loops and recursion are not obvious to model. This is because the body of a loop is a program and can be represented as a mathematical function. How do we derive the function representing the loop's behaviour? It corresponds to applying the loop body repeatedly, in conjunction with the loop guard, until no further change is possible. Similarly, if we model recursive programs mathematically, we need a mathematical notion of what it means for a function to apply itself. This answer is provided by fixed points.

Answer 4

A function in mathematics is a map between input and output values. Fixed points are input values (for a function) which map to output values satisfying equality with the input.

For the equality function $f(x) = x$ the set of input value equals to the set of fixed points of the function. For a function $f(x) = x^2$ the set of fixed points is limited to $\{0, 1\}$.

As far as computer science is concerned, we are talking a lot about partial functions, but this does not change the definition of fixed points for us.

You might also be confused about a totally different topic: Fixed-point arithmetic is a concept how to represent real numbers in the memory. But the name "fixed points" does not reference to this topic in general (because there is only 1 point).

Answer 5

game theory is a major subarea of CS and an important concept there is the Nash equilibrium which is a fixed point theorem. it gives a means of identifying optimal game strategies given that other players are aware of each others strategies. it can be proven via Kakutani fixed point theorem or the Brower fixed point theorem. Nash won the Nobel Prize in Economics in part for developing this theory.