アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

216

7

章 至るところにある万能性

ことで、チューリングマシンを完全にシミュレートすることができます。このシミュレーションは機械

が停止するまで続き、もし機械が停止しなければ、永久に動くことになります。

7.3

　

SKI

コンビネータ計算

SKIコンビネータ計算（SKI combinator calculus）とは、ラムダ計算と同じように、式の構文を操作

する規則のシステムです。ラムダ計算も非常に単純なのですが、それでも変数、関数、呼び出しとい

う3 種類の式があります。「6.2.2　意味論」では、変数によって簡約規則が少し複雑になることを見ま

した。SKI 計算はラムダ計算よりもさらに単純で、呼び出しとアルファベットのシンボルという2種類

の式しかなく、規則はずっと簡単になります。その能力はすべて、3種類の特別なシンボル、

S

、

K

、

I

によるものです。これらのシンボルはコンビネータ（combinator）と呼ばれ、それぞれ独自の簡約規則

を持っています。

●

S[

a

][

b

][

c

]

を

a

[

c

][

b

[

c

]]

に簡約する。ここで

a

、

b

、

c

は任意のSKI計算の式を示します。

●

K[

a

][

b

]

を

a

に簡約する。

●

I[

a

]

を

a

に簡約する。

たとえば、

I[S][K][S][I[K]]

という式を簡約していくと、以下のようになります。

I[S][K][S][I[K]]

→

S[K][S][I[K]]

（

I[S]

を

S

に簡約する）

→

S[K][S][K]

（

I[K]

を

K

に簡約する）

→

K[K][S[K]]

（

S[K][S][K] ...