数理論理学と計算可能性

前回の記事で，「計算が定義されることで数学の中で市民権を得る」と書きました．

うっすらとお気づきかもしれませんが最近の数記事は続き物になっておりますが（最後に伏線回収の回があります），それぞれ単体で読める記事ですのでご安心ください．

さて，計算を定義することで$${\infty}$$が数学の中で市民権を得ることは，まあ腑に落ちる話かもしれません．
今回はもうちょっと別の話，論理学の話です．「論理が数学の中で市民権を得ることができるか？（論理を数学的に扱うことができるか）」という話です．

数学って実は“言葉”にうるさいという記事で，「数学には厳密なルールがある」と書きました．
この“厳密なルール”というのが“論理”のことで，数学的に論理を扱いたいと考える数学者は昔からいます．数学的に論理を扱うことを研究する分野のことを“数理論理学”と言います．

さて，数学的に扱うためには計算を定義する必要があるんでした．
少し難しい話になりますが，ここで“計算”というものを考えてみましょう．

“計算”というのは，「いつだれがやっても同じ結果が出る規則」のことです．例えば足し算という計算は，いつだれがやっても同じ結果が出ますよね．（計算ミスは，規則に従えていないので）

で，論理の計算を定義するというのはどういうことかと言うと，「仮定が与えられたときに，いつだれがやっても同じ結論が出せる規則を決める」ということです．
と言うと，論理の計算を定義するというのが難しいことであることがなんとなくわかるんじゃないかと思います．

具体的にどのように計算するのかはこの記事では割愛しますが，このように「計算できるかどうか」，言い換えると「いつだれがやっても同じ結果が出る規則を決められるかどうか」は“計算可能性”と言います．
この計算可能性に興味があるのは，数学畑の人間だけではなくてコンピュータ畑の人間もだと思います．コンピュータというのは，計算（compute）する機械なので．