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

ここでは簡単にチューリングマシンの数学的な表現について述べます。ちなみに、チューリングマシンもいろいろ種類があるのですが、ここでは、もっとも基本的なチューリングマシンを説明します。

チューリングマシンは頭文字を取ってＴＭと略したりもします。

イメージとしてのチューリングマシンは、無限に長いテープとヘッド、そしてヘッドのコントロールによって構成されます。

テープには有限の文字列が書き込まれており、ヘッダはテープに書かれている制御データによってテープ上を移動します。ヘッダを動かすのがコントロールです。別にヘッダではなくてテープを動かしても良いのですが、とりあえずのわかりやすさを優先させました。だいたい、無限に長いテープが移動するってどういうことよ（笑い）。ま、無限に長いテープ上を移動するヘッダもヘッダですが、まぁ、それはデータは有限ですから。

さて、そろそろ本題です。ヘッドはテープ上の有限な長さの文字列を移動しますが、これがいつ止まるのか？それとも止まらないのか、というのが、チューリングマシンの決定問題といわれるものです。

正確に言うと止まるとしても、われわれが死んだあと、あるいは宇宙が終わったあと止まる、というのでは困ります。このモデルは理論的なものですけど、やっぱり、ある程度実用的なものでないといけない。従って、データの長さをnとしたときに、nの多項式で表わされる時間なら、まずまず実用的でしょう、ということを偉い人が決めたので、この手の文字列（データ：あるいはヘッドを制御するプログラム）の集合をクラスPと呼んでいます。もう少しかっこよく専門的にいうと、多項式時間（Polynomial time)で解決できるアルゴリズムの集合がクラスPといわれるものです。PはもちろんPolynomial timeのＰです。

一般に計算機科学では、この手の計算量をオーダー（Order）の頭文字を取ってO（）という関数で表わしたりもします。たとえば、ある文字列をチューリングマシンで処理すると3n^5＋5n＋3(^はべき乗を表わす）としたらこのオーダーはO（n^5）と表わします。一番効いてくるものだけで表わすのが特徴です。

たとえば、O（5^n）というような、nがべき乗数となるようなものは、あまりにも時間がかかりすぎてチューリングマシンでは扱えないような問題となっています。

このO（）が普通に使われますが、下限とか上限とかいろいろこれから難しい話も出てきます。その都度に多様な記号が使われたりしますが、それはその都度説明することにします。

あと、もう一つだけ。この場合、問題の計算量を時間を元に考えていましたが、処理する量を空間と考える評価方法もあったりします。しかし、とりあえずP=NP？問題ではとりあえず、時間が目安となります。

※2014/10/26　一部文言を修正。誤字脱字などもありましたので。ご迷惑をおかけいたしております。