Smn定理
以下のLISPのコードは、s11 を実装したものである。
例えば、(s11 '(lambda (x y) (+ x y)) 3) を評価すると (lambda (y) ((lambda (x y) (+ x y)) 3 y)) になる。
例えば、それらの数のビットをインターリーブするといった符号化が考えられる。すると任意の正の数 m と n について、m+1 個の引数をとる原始再帰関数 s n m {\displaystyle s_{n}^{m}} が存在し、次のように振舞う。すなわち、あらゆる m+n 引数の関数のゲーデル数 p について、
φ s n m ( p , x 1 , ... , x m ) = λ y 1 , ... , y n . φ p ( x 1 , ... , x m , y 1 , ... , y n ) {\displaystyle \varphi _{s_{n}^{m}(p,x_{1},\dots ,x_{m})}=\lambda y_{1},\dots ,y_{n}.\varphi _{p}(x_{1},\dots ,x_{m},y_{1},\dots ,y_{n})\,}
となる。 s 1 1 {\displaystyle s_{1}^{1}} は、関数 s そのものである。