はてぃーぽったーの備忘録

某授業まとめ+競プロの感想記事

情報数学の講義で学ぶことの概略

これは私個人の経験則なのですが、講義の内容が何に役立つのかが見えて来ず、それゆえ勉強に身が入らないということが少なからずあると思います。そこで今日はこの講義で学ぶ内容はそもそもどういった分野に属しているのか、特にチューリングマシンはどういった点で役に立つのかをまとめていきます。

本講義では前半と後半で扱う理論が以下のようにガラッと変わります。

  1. 計算可能性の理論
  2. 計算の複雑さの理論

競プロ等の文脈ではよく見かける計算量の概念ですが, あのあたりは複雑さの理論に入っています。

講義前半で行うチューリングマシンの導入から決定(判定ともいう)可能性等についてのお話は計算可能性の理論です。この理論は、ある問題が電子計算機で計算可能であるかどうかに興味があります。つまりはどれくらいの時間がかかるか、どれくらいのメモリを必要とするかといった実装上の問題ではなく、原理的に計算が可能かどうかといった問題に主眼を置くわけです。実は前期でもそれなりにこの計算可能性の理論のお話をしていまして、例えば文脈自由文法で生成される言語と同じ言語を認識するオートマトンとしてPDAを学習しましたが、あれは無限長(可変長)のメモリを持っています。空間計算量を全く気にしていないわけですね。

ここで計算機というものについて軽く触れておきます。

計算機(けいさんき)は、計算機械的に、さらには自動的に行う装置である。人間が行う計算を援助するのみのものや、手動操作で自動的ではないものなどは計算器という文字表現をすることがある。計算機 - Wikipedia

だそうです。私たちが普段触れてるコンピュータなども計算機と言うようですね。

このような理論を研究する分野を「計算科学」と言います。wikipediaさんが上述の二つの理論についてもう少し詳しく解説してくれてます。

計算可能性理論 - Wikipedia

計算複雑性理論 - Wikipedia

 では、チューリングマシンについて説明していきます。端的に表現すると、

計算機を数学的な議論のために単純化、理想化したモデル

のことを言います。実は、実際の計算機の基本動作はチューリングマシンの原理に従っていると言えます。このことから、「チューリングマシンで解ける問題」と「計算機で実際に解ける問題」が同一であると言われるわけです。数学的な議論ができるというのがミソで、実際に計算機の上でシミュレーションをすることなく様々な問題の計算可能性についての議論ができるわけです。私たちは今後計算機を大いに活用することになるでしょうから、計算機に非常に近いモデル化された機械を学ぶことは重要であると言えるでしょう。

 

次回はチューリングマシンの形式的な定義から計算状況まで書いていこうと思います。

浅学なもので、誤解を産む表現がいくらかあると思います。何か至らない点や聞きたいこと等ありましたら遠慮なくコメントお願いします。

 

編集履歴

文中の表現を修正しました (2020/10/06)