機械の番号

自然数 $e$ に対し、機械 $M_e$ を次で定める。各 $q\in\mathbb{N}$, $a\in\{0,1,2\}$ について $v=(e+1)_{3q+a}$（$e+1$ の素因数分解における $p_{3q+a}$ の指数）とおく。$v=0$ なら $(q,a)$ に対する規則はない。$v\ge1$ なら $w=v-1$ とおき、規則

を $M_e$ に入れる。$e+1$ の素因数は有限個なので、$M_e$ の規則は有限個である。$\varphi^{(n)}_e=\varphi^{(n)}_{M_e}$ と書く。