debugModerate
Fixed point, what does it mean in the world of computer science
Viewed 0 times
sciencethewhatpointmeanworldcomputerdoesfixed
Problem
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.
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.
Solution
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.
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.
- Everybody uses it every day, even if you don't realise it.
- I don't like that Wikipedia article; you are probably better off checking a genre book.
- A special kind of function numbering. For intuition, think of it as a (Turing-complete) programming language.
Context
StackExchange Computer Science Q#3466, answer score: 17
Revisions (0)
No revisions yet.