English version
これまで SUCC1 や Pop1 という機械を見てきた.それぞれの機械はある手順を実行する.手順は入力に対してどんな操作をして出力を作るかという命令を順番に並べたものである.ここでは単純なモデルとして機械は一度に一つの命令しか実行できないものを考えた(つまりここでは並列計算は考えない).命令には,「入力があれば出力のテーブルにコピーする」や,「出力のテーブルの頭と尾の記号を削除する」というようなものがあった.
命令を並べた手順によって計算というものができることはこれまでにみてきた.その具体例は SUCC1 と Pop1 であった.こうやって任意の機能の機械を作っていくこともできる.しかし,毎回新しい問題ごとに設計しなくてはならないのだろうか.足し算のために足し算機械を,引き算のために引き算機械を作る必要があるのだろうか.それとも足し算も引き算もかけ算も割り算もできる,より一般的な計算機械を作ることはできるのだろうか.
こうなると数学者は考える.「いったいいくつの命令があれば全ての問題を解くことができるのだろうか.」「全ての問題とはいったいなんだろうか」「何が計算でき,何が計算できないものなのか」
以前,λ計算の動機という話をした.そこでは計算というものを形式的に考え直すという動機があった.これまでに計算はより単純な手順によって構成されることを見てきた.つまり,計算は形式的なものでも実行できる,それは可能だったのだ.可能性がわかったので,質問は次のレベルになる.多くの学問の発展と同じパターンがここには見られる.
λ計算について次のレベルに行く時が来たようだ.