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

Problem Detail: 

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.

Asked By : Guy Coder

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3466