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

208

7

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

7.1

　ラムダ計算

ラムダ計算が役に立つプログラミング言語であることを見てきましたが、チューリングマシンと同等

の能力があるのかについては、まだ調べていませんでした。実のところ、ラムダ計算には少なくとも

チューリングマシン相当の能力はあるはずです。なぜなら、万能チューリングマシンを含む任意の

チューリングマシンをシミュレートできることがわかっているためです。

それでは、チューリングマシンの一部であるテープをラムダ計算で簡単に実装し、それがどのように

動くのかを実際に体験してみましょう。

６章と同じように、ここでは近道をすることにします。

proc

の生成と呼び出しと、短縮とし

ての定数だけを使うという制約を課して、ラムダ計算の式を

Ruby

のコードとして表現します。

ここに調査対象ではない

Ruby

言語を持ち込むのは少し危険ですが、それと引き換えに、見慣

れた式の構文とそれを評価する簡単な方法が手に入ります。ここでの発

見は、課された制約

内にとどまる限り有効です。

チューリングマシンのテープには、テープの左側にある文字のリスト、テープの中央にある文字（読

み書きのためのヘッドの下にある文字）、テープの右側にある文字のリスト、空白として扱われるべき

文字、という4つの属性があります。これら4つの値は、ペアのペアとして表現できます。

TAPE = -> l { -> m { -> r { -> b { PAIR[PAIR[l][m]][PAIR[r][b]] } } } }

TAPE_LEFT ...