Grigorchuk group

Description

Let $\set{0, 1}^*$ be the set of finite words in the letters $0$ and $1$, the vertices of the infinite rooted binary tree. Define four maps $a, b, c, d$ of $\set{0, 1}^*$ to itself by recursion on the length of a word $w$. Each map sends the empty word to the empty word, and: $$a(0w) = 1w, \quad a(1w) = 0w,$$ $$b(0w) = 0\,a(w), \quad b(1w) = 1\,c(w),$$ $$c(0w) = 0\,a(w), \quad c(1w) = 1\,d(w),$$ $$d(0w) = 0w, \quad d(1w) = 1\,b(w).$$ Each map is a bijection that preserves the length of words and the tree structure. The Grigorchuk group $\Gamma$ is the group generated by $a, b, c, d$ under composition.