本日は、数学基礎論、計算機科学について紹介していきたいと思います。
- 数学基礎論
数学基礎論はその名の通り、数学の基盤となる分野です。数学基礎論の一分野に数理論理学がありますが、ほとんど数学基礎論といえば数理論理学を指すことが多いです。
数理論理学はざっくりいうと数学の証明のお作法を学びます。数学の証明は、公理や定義から始まって論理的な推論をいくつも経て主張ないし定理を得る過程のことです。論理的推論の例として、アリストテレスの有名な例で「人はいつか死ぬ。ソクラテスは人である。ゆえにソクラテスは死ぬ。」というものがあります。これは集合論的にいうと、「AはBであり、a \(\in\) Aであるから、a is B」ということを意味しています。これは反証しようがない推論となっており、こうした推論の方法/テクニックを学びます。
数学基礎論ないし数理論理学は計算機科学と結びつきが強い分野(というか数理論理を使って定式化している)で、計算機科学の書籍には基本的な数理論理の話がだいたい載ってます。
この分野で有名なのがゲーデルの不完全性定理です。これは超ざっくりいうと「自然数論を含む論理体系は自己の無矛盾を証明することができない。」です。ある理論体系の中で、証明も反証もできない命題が存在するもので、ゲーデルがこの証明が世の中にでた際、かなり衝撃を与えたと言われています。
- 計算機科学
計算機科学はコンピュータ(計算機)を数学的にモデル化して、コンピュータの限界や新アルゴリズムの存在を模索する分野です。その際最初に必要となる概念がオートマトンです。数学的定義の詳細は割愛しますが、有限な状態の集合と、状態を遷移する写像から成り、これは状態をもつシステムを構築する際にとても有用な概念となります。オートマトンという言葉よりかは状態機械(もしくはステートマシン)で呼ばれることが多いです。オートマトンで処理可能な文字列を「文脈自由言語」と呼びますが、これはプログラミング言語のコンパイラーによく使われます。
オートマトンと無限に長いのテープを一緒にしたものがチューリングマシンです。チューリングマシンがコンピュータの数学的モデルであり、ある命題の計算可能性や計算時間や計算領域を調べる際に使われます。
さまざまな命題を分類するのに計算時間を用いられることが多いです。計算時間の分類として有名なのがクラスP、クラスNPです。入力の文字数をnとしたとき、クラスPに属する問題は決定性チューリングマシンを使ってnの多項式時間でとける命題で、クラスNPは非決定性チューリングマシンをつかってnの多項式時間でとける命題です。現在P\(\neq\)NPという予想はされていますが、証明はされてません。P\(\neq\)NP予想はミレニアム懸賞問題のひとつになるほど重要なステートメントになります。
最後まで読んでくださりありがとうございます。
質問等はコメント欄か問い合わせページにておねがいします。