チューリングマシンの数理モデル

今回は、チューリングマシンを数学的に定義するという話です。

まず、記号の話からしますか。退屈でしょうが付き合ってください。 だって数学の話だしね(笑い）

　Σ：入力。専門的にいうと入力記号の有限集合 

　Γ：テープにあるデータ。Σに空白記号を加えたもの。有限 

　b：空白記号 

　Q：チューリングマシンの状態。有限集合。 

　　　状態q0を特に初期状態という。 

　　　数学的な書き方をすれば、 

　　　　　　q0∈Q（元q0は集合Qに属すると読む） 

　F：チューリングマシンの終了状態の集合

　　　　たとえば、結果が2値の場合は結果yesを表わすqyと、

　　　　結果noを表わすqnとしたときは

　 　　　　　F＝｛qy，qn｝

　　　　数学的に書くと、

　　　　　　F⊆Q

　　　（FはQの部分集合と読む。でもイメージ的には４≦５。

　　　　カントールの集合論を思い出してください）

　Δ：ヘッドを移動させる命令の集合。

　　　テープの入力データの中に付記されている 

　　　ここでは、 

　　　　　-1 ： ヘッドをテープの一つ左の入力へ移動

　　　　　+1 ： ヘッドをテープの一つ右

　　　　　  0 ： ヘッドはそのまま  

　　とする 

　δ：チューリングマシンの状態遷移関数。定義は次の通り

　　　　δ：（Q－F）×Γ　→　Q×Γ×Δ 

　　意味的には現在の状態は（Q－F）のある元で表わされ、入力はΓの元。 

　　これが関数δによって、

　　　次の状態の集合はQの元、

　　　次のテープの状態はΓの元、 

　　　これに加えて、ヘッドの移動の命令Δ、

　　によって表現されます、ということ 

　　例えば、 

　　　　δ(q0，ｓ）＝（q’，s’，+1） 

　　というのは、現在の状態がq0，

　　ヘッドの置かれているテープからの入力s（s∈Γ）のとき、 

　　チューリングマシンの状態はq0からq'へ変わり、 

　　現在ヘッドの置かれているテープの状態はsからs'へ変わり

　　そのあとヘッドはテープの一つ一つ右側の入力へ移る

　　ということ 

一応、チューリングマシンの数学的なモデルは上記のような記号（集合）であらわせるんです。

それじゃあ、問題が解けた、つまり決定問題がyesとなって受容されたということを、この世界の専門用語でどういうかというレッスンを次にしましょう。すでに、受容という言葉で出てるんですけどね。これは受理という書き方をする人もいます。まぁ、言葉はわりといい加減でも、数学的に厳密なら言い訳というのがこの世界。ここでは、竹内外史先生の「PとNP」に従い、p.3-p.4より引用します。本は絶版でも、竹内外史といえば、知る人ぞ知る超有名日本人ですしね。

「いまインプットx∈Σ*がマシンのプログラムMで受容されるということを、上のプログラムの進行がqyイエスで終結することとする。

このときにプログラムMで検証される言語LMを

　　LM＝｛x∈Σ*｜xはMで受容される｝

によって定義する。」

とあります。注意書きとしてプログラムMをマシンMといったりもする、とか、まぁ、いろいろ難しい事が書いてありますが、その都度、注釈を入れていきます。

あと「プログラムMで検証される言語LM」という言い方がこの世界の独特の言い方だったりします。ところで、この世界って？ずっと使ってましたが、これから先、この世界、といえば、数学の中でもわりと特殊な数理論理学という世界の事だと思ってください。さきの「プログラムMで検証される言語LM」でいう「言語LM」とはあれですよあれ。数理論理学で使うあれ。専門用語って奴ですね。竹内先生の説明では

「計算論では一般に記号の集合Πがあったときに、Π*の部分集合のことを言語というが、数理論理学のときは言語は一つの論理体系を定義するときの基本的な記号の集合のことをいう」

とあります。この辺は実にディープな世界。計算論というのは数学基礎論から発達した、計算機を扱う学問で計算機科学といったりもします。一方、数理論理学というのは記号論理学ともいいまして、∧（AND）、∨（OR）、￢（NOT）などなど、の記号を使った特殊な数学ですね。ま、これもある種の数学です、はい。この辺もその都度説明します。その他諸々の事も以下同文です。

おまけですが、数理論理学はもともとは哲学の一分野だったんですね。誰もが名前を聞いたことがあるような人を、下に挙げておきます。

• ラッセル（Wikipedia：http://ja.wikipedia.org/wiki/バートランド・ラッセル）
• ウィトゲンシュタイン（Wikipedia：http://ja.wikipedia.org/wiki/ルートヴィヒ・ウィトゲンシュタイン）
• ヒルベルト（Wikipedia：http://ja.wikipedia.org/wiki/ダフィット・ヒルベルト）

特に、ヒルベルトは知っておきましょう。数学の世界では、物理学のアインシュタインよりも有名と言っても良いぐらいです。

あと、ゲーデルの不完全性定理は知ってる方も多いでしょうけど、竹内外史先生はそのゲーデルのお友達だったとっても偉い先生です。覚えておくように（笑い）