2002年12月 1日 作成 チューリング・マシーン >> 目次 (作成日順)
2008年 1月16日 補遺  


 
 今回は、「チューリング・マシーン」 について述べる。

 
 チューリング は、計算可能性を定式化するために、概念的な計算機械を考えた。
 計算機械は、以下の 3つの概念を使って記述される。

 (1) 機械の内的状態 [ 状態記号 ]
 (2) 機械の外に用意された テープ [ テープ 記号 ]
 (3) 写像 (状態記号と テープ 記号の関係)

 機械の内的状態(状態記号)は以下のように記述される。

  Q = {q0, q1,・・・, qn}.

 テープ 記号は以下のように記述される。

  M = {s0, s1,・・・, sn}.

 そして、以下の写像を考える。

  t : Q × M → Q × M × { R, L, O }.

 R は 「right (右に移動する)」、L は 「left (左に移動する)」、O は 「動かない」 という意味である。

 
 チューリング・マシーン は以下のように記述される。

  T = (Q, M, t, q0, F).

 q0 は 「初期状態 (initial state)」 である。
 F は 「最終状態 (final state)」 である。
 当然ながら、F は Q の サブセット である。

 また、或る内的状態の変化 [t(q, s)=(q’, s’, x) であるとき ]、(q, s, q’, s’, x) のことを 「instruction」 という。

 
 以下を前提にして、最終状態が 「停止」 となる例を扱ってみる。

 (1) テープ には区画が用意されている。
   それぞれの区画には、あらかじめ、「有限個の」 以下の記号のなかから、それぞれ、1つが プリント されている。
   {s0, s1,・・・, sn}.

 (2) テープ に対して操作をする装置を ヘッド という。
   ヘッド は、以下の状態のなかから 1つを取る。
   {q0, q1,・・・, qn}.

 (3) ヘッド は (テープ から) テープ 記号を読む。
   ヘッド は、状態記号と テープ 記号を判断して、以下の 3つの操作をする。
   - テープ 記号を置換する。
   - ヘッド の位置を移動する。 [ 右に移動するか、左に移動するか、または動かない。 { R, L, O } ]
   - ヘッド の状態記号を置換する。

 (4) なお、ヘッド の移動について、「instruction (q, s, q’, s’, x)」 が、あらかじめ、用意されている。
   この一覧表を δ (デルタ) と呼ぶ。

 
 さて、以下の例を考える。

 (1) ヘッド の状態  q0
 (2) テープ の記号  { s0, s1, s1, s1, s0, s0, s0,・・・ }.
 (3) δ (F = { Q2} ) は以下とする。

 

 q0q1q2
s0s0Rq1s02 
s1s1Lq1s0Rq2 

 
 この例では、以下のような操作となる。

 (1) 最初の動作は、(q0, s0) だから、状態記号と テープ 記号は以下のように置換され、ヘッド は右に移動する。
   - 状態記号 (q1
   - テープ 記号 (s0

 (2) 次に、(q1, s0) だから、状態記号と テープ 記号は以下のように置換され、ヘッド は動かない。
   - 状態記号 (q2
   - テープ 記号 (s0

 (3) F (最終状態記号) が q2だらか、ヘッド は停止する。

 
 ゲーデル は、「計算可能性」 に言及して、以下のように言った (プリンストン 高等研究所の講演)。
 「私の意見では、最も完成度の高い やりかた は、有限個の手続きの概念を有限個の部分から構成される機械の概念に還元する、というチューリング 氏が提示した やりかた です。」

 



[ 補遺 ] (2008年 1月16日)

 本 エッセー では、チューリング・マシーン の考えかたを 「簡単な」 例題で示しました。前回、「帰納的」 という概念と 「帰納的に可算」 という概念はちがうことを述べました。「帰納的」──S ⊆ N が空でないとして── を チューリング・マシーン M を使って言い換えれば、特徴関数 CSが計算可能なので、x ∈ S あるいは ¬ (x ∈ S) の いずれの場合でも、チューリング・マシーン は、CSを有限の時間内で判断できる、ということです。

 「instruction (q, s, q’, s’, x)」──あるいは、M による 「特徴関数の 『計算 (computation)』」──は、δ├ M の 2項関係として、「閉含 (closure)・外点 (exterior point)」 という概念を使って考えることもできます。├ M に対して、反射的・推移的閉含 ├ M* を考えます。「閉含」 とは、位相空間 S の部分集合 M に対して、M の 「外点」 の集合 Me = (Mc)i の補集合 (Me)c = ((Mc)i)c のことを云い、Mで表します。したがって、M⊃M が成り立ちます。簡単に云えば、「M は M をふくむ最小限の閉集合」 のことです。なお、S の点 p が M の 「外点」 であるとは、p が M の補集合 Mc の内点になっていることです。

 チューリング・マシーン で計算可能ということは、S ⊆ N のなかで、δ├ M の初期状態で始まり、├ M* の内点に終わる関数がある、ということです。すなわち、(x1,・・・, xn) q0B ├ M* f (x1,・・・, xn) qhB となる qh が存在する、ということです。逆の言いかたをすれば、上述した式を満たす チューリング・マシーン が存在するとき、関数 f は 「部分的に計算可能 (partially computable)」 であると云います。そして、関数 f が全域的かつ部分的に計算可能であるとき、チューリング・マシーン は f を計算する (compute) と云います [ 「全域的」 は、「ベーシックス」 144ページ を参照されたい。]

 チューリング・マシーン で数論的関数を計算するためには、対象を ゲーデル 数化すれば良いでしょう。
 以下の n + 2 変数述語を考えてみます。

    Tn (z, x1,・・・, xn, y).

 y は、ゲーデル 数 z である チューリング・マシーン M による初期状態 (x1,・・・, xn) q0B に始まり、wqhB に終わる ゲーデル 数です。そして、x が ゲーデル 数であるとき、その最後の関数値を取り出す原始帰納的関数 U を用意します。そして、f (x1,・・・, xn) を部分的に計算可能な関数として、それを部分的に計算する チューリング・マシーン を M として、M の ゲーデル 数を k とすれば、以下が成立します。つまり、f は、帰納的部分関数です。

   f (x1,・・・, xn) ←→ U (μyTn (k, x1,・・・, xn, y)).

 ちなみに、チューリング・マシーン は、「計算する」 configuration なので、プログラム のことであると言って良いでしょう。ただ、任意の チューリング・マシーン M と、その入力 データ を前提にして、M が データ に対する動作を 「解釈」 する チューリング・マシーン U を考えることができます──言い換えれば、U が存在します。その U のことを 「universal machine (万能機械)」 と云います。この U が、現代の コンピュータ です。

 さて、応用問題として、以下の事態が 「決定可能」 かどうか を考えてみましょう。

    任意に与えられた チューリング・マシーン (Q, M, t, q0, F) に対して、xq0B で始まり、wqhB に
    終わる M による計算が存在するかどうかを決定する アルゴリズム を作りなさい。

 この問題は、対象を ゲーデル 数化すれば、∃y T1(z, x, y) に関する 「決定問題」 となります。答えは、「決定不能」 です。この問題を、チューリング・マシーン の 「停止問題 (halting problem)」 と云います。「停止問題」 とは、単純に言い切ってしまえば、「プログラム が停止するか否かを決定する プログラム を作成できない」 ということです──「『決定可能 (決定のための アルゴリズム)』 を決定する」 プログラム を作ることができない、ということです。というのは、もし、∃y T1(z, x, y) が 「決定可能」 だとすれば、「帰納的」 であり、したがって、∃y T1(x, x, y) も 「帰納的」 になるはずですが、∃y T1(x, x, y) は、「帰納的に可算」 であって 「帰納的」 ではないからです。
 ∃y T1(x, x, y) の補集合を考えてみて下さい──ド・モルガン の法則を使って、¬ (∃y T1(z, x, y)) ≡ ∀y ¬ T1(x, x, y). すなわち、n + 1 変数述語で、すべての y が 「帰納的に可算ではない」 ということになるので、∃y T1(x, x, y) が 「帰納的に可算」 であっても、その補集合が 「帰納的に可算でない」 ので、「帰納的」 でない、ということ (もし、この意味がわからないなら、前回の 「計算可能関数」 補遺 168ページ を復習して下さい)。




  << もどる HOME すすむ >>
  ベーシックス