続 atsushifxの七転八倒

ウツ、発達障害の闘病記とIT関係のつれずれを書いていきます

「プログラマの数学 第8章 計算不可能な問題」まとめ

第8章はコンピュータ、もっと広げて数学を使って解けない問題があることを学びます。
これらのことを計算可能性と呼びます。

まずは、前提となるカウンタブルについてのまとめ


  • 計算可能性を証明するには、背理法を使うことが必要である。背理法とは、Aが成り立たないならばBが成り立つことがありえないことを証明することで"AならばB"を証明する方法である

  • 無限集合にカウンタブルな集合とカウンタブルでない集合の2種類があることを説明する。カウンタブルな集合とは、集合の要素を1,2で始まる自然数に対応付けられる集合である

  • 集合がカウンタブルでないことを証明してみる。証明には対角線論法を用いる

  • 対角線論法とは、簡単に言うと。整数列の集合を表として示し、その対角線上の要素を使って列をつくることでカウンタブルでないことを証明する方法である。背理法の応用といってよい

次に、計算可能性のまとめ


  • 計算不能問題というものが存在する。計算不能問題は、そもそもコンピューターで解けない問題である。もちろん、プログラムすることもできない

  • 計算不能問題が存在するのはカウンタブルに関係する。プログラムの集合を考えたとき、プログラム集合はカウンタブルである。そのため、カウンタブルでない集合にはプログラムできない要素が存在する

  • 計算不能問題の例として停止判定問題がある。停止判定問題とは、あるプログラムPが有限時間内に停止するか、無限に実行されるかを判定するプログラムはかけないという問題である

つまりプログラムを考えるには、その問題がプログラムできるかどうかを考える必要があるということです。