クラスPとチューリングマシンその１

クラスPの問題がなにかということを理解するためには、そのまえにチューリングマシンについて理解する必要があります。普通の人はまずここが一つの関門でしょう。できるだけ分かりやすく、と心がけてはいますが、易しく説明するのが難しい事も多いのです。何が言いたいか、というと、こっから先、分からなかったらごめんね、ということです。

さて、チューリングマシンをまず説明しましょう。ここから先、Wikipedaも引用したりします。チューリングマシンの記事も引用すればいいじゃないかという話もありますね、そうですね。

そういうわけで、Wikipediaの記事チューリングマシン（http://ja.wikipedia.org/wiki/チューリングマシン）より一部、引用します。

歴史
1936年にイギリスの数学者アラン・チューリングの論文「計算可能数について──決定問題への応用」で発表された。同様の考え方は同年にエミール・ポスト (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。

（引用終わり）

Wikipediaの記事はかっこいいなぁ。それは置いといて、チューリングの論文のタイトルにあるように、チューリングマシンは決定問題を扱うモデルです。

決定問題、というのがまず、問題ですね。決定問題、というのは、なにか問題が与えられたとしましょう。皆さんは、現代のコンピュータが０と１で形成される２進数ですべてを処理しているというのはご存じですね。現代では常識です。ということは、情報というものは、すべて、０と１の羅列で表わされるわけでしょう？どれだけ長くなっても。コンピュータは疲れを知りませんからね。ということはさぁ、結局情報って数字なわけぇ（なぜかコギャル風）。どんな長い文章でも０と１であらわして、それをわれわれに分かるような１０進数に変更できます。どれだけ桁が大きくなるか分からないけど、数字に直せます。で、なんかのルールに従って、それが、その数字がルールにあってるかあってないか、ということを決定しましょう、というのが決定問題。Wikipediaのクールな記事を引用するとこうなります。（http://ja.wikipedia.org/wiki/決定問題）

決定問題

決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合{0,1} ^* から{0,1}への写像、あるいは{0,1} ^* の部分集合である。

たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。

決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。

（引用終わり）

{0,1} *というのは、０と１の有限な羅列の全体の集合という意味です。これをあるやり方で０か１の二つしか値のない集合へ写像する、言い方を変えれば真か偽かに決定するということが、この記事の{0,1}への写像という言い方です。数学では普通にこういう言い方をします。あるいは｛0,1｝*の部分集合というのは、２値への写像だけではなく、多値へ写像も扱うことがありますよ、という意味です。

さて、チューリングマシンに戻ると、この決定問題を扱う計算機モデルのことをチューリングマシンといっているわけです。