計算とは？

第2章 No.0 ／ 推論こそが計算である

コンピュータ (computer) とは「計算機」と訳すことができる。しかし、計算とは何だろう。例えば、

11 + 42 = 53

も計算であるし、

x² = 2 より、x = √2

を計算することも計算であった。しかし、さらに広義に計算を定めると以下のようになる。

「…」で囲まれた文を 命題 という。上のような 2 つの命題から「太郎は空を飛べない」と結論を得ることを 推論 という。

実は、このように 文 (日本語) により書くことができる表現を、より形式的に表して 推論 することを計算という。

さらにこのように計算を定義しても、計算することができない文を表現できることが 1930 年代に ゲーデル により証明された。このような文を パラドックス という。

以下に紹介する 命題論理 と、一階述語論理 には、パラドックスが生じないことが知られている。