FANDOM


入力を読み取るコンピュータそのものの仕組み、コンピュータに与えられる特定のプログラム、この両方からチューリング完全を解釈する。

ハードからの解釈

厳密で形式的に定義すると・・・

計算可能とは、定義域内の0と1の有限の数列で表現可能な任意の入力に対して、1ステップずつ、あらかじめ定めた、字母集合となる有限の集合から選ばれる文字によって、有限の文字数で記述可能な規則=プログラムに則りながら、入力と同じく0と1の有限の数列で表現可能な部分的な結果を導き出し、最終的に有限時間内に全体の結果を導き出す(そして終了状態に入る)ことをいう。定義域が有限であれば、あらかじめすべての入力とそれに対応する出力を用意しておけばいいだけなのでただそれだけで計算可能である。

反対に計算不可能とは、プログラムの長さ、または計算時間のいづれかがどうしても無限に長くなってしまうことをいう。

計算機のモデル

メモリの座標、値、状態、遷移関数

メタな視点からみて、関数を計算するためには、定義域と値域の要素すべてをそのプログラムを記述する言語で、それぞれ区別がつくように表さなければならない。

例 自然数をあらわす原始的な方法

まず、どんなプログラムにどんなコードでもかまいませんが、0にあたるコードを入力します。それで出力されたコードが1になります。0と同じコードになってしまったり計算が終了しなかったりする場合は、別のコードを0として入力しなおすなりプログラムを書きなおすなりします。
1のコードを入力して出力されたコードが2のコードとなります。0または1とかぶってしまう場合や計算が終了しない場合は0のときと同じように対応します。
2のコードを入力して出力されたコードが3となります。以下同様。

例の例 チャーチ数

プログラム λx.(λg.(λy.g(xgy)))
λ計算やコンビネータの適用は特に指示されてなければ左結合
0:=λf.(λx.x) とする。すると 1:=λf.(λx.fx), 2:=λf.(λx.f(fx)), 3:=λf.(λx.f(f(f(x)))) ...


任意の関数 f と g がともに計算可能ならば、そして g の値域が f の定義域の部分集合となっているならば、f(g(x)) (以下、関数の入れ子は特に指示がない限り右結合)も計算可能である;任意の値 x を関数 g を計算するプログラムに入力すると有限時間内に値 y が返ってくる、y を、手動でもいいので、関数 f を計算するプログラムに入力すると有限時間内に値 z が返ってくる、この z が求める値であり、かかった時間、およびプログラムの長さも有限+有限=有限である。

定義域を無限集合とし、同様の条件で、fx が計算可能ならば ffx,fffx,ffffx,... も計算可能であるが、関数の合成だけでは f^x(x) が計算可能であると証明することができない。単純に、fx を計算するプログラムと値を次の関数に渡すプログラムを重ねていくだけで、fx,ffx,fffx,... を計算する有限の長さのプログラムがそれぞれにできるが、その長さの列は無限大に発散するため、関数の合成しかできない言語では f^x(x) を計算する有限の長さのプログラムをつくることができない。(ただし定義域と値域が有限集合であり、都合がよければ可能)。

無限の定義域の中から値を受け取り、それぞれの値に固有の関数を計算するプログラムを返す関数を計算するプログラムによって、f^x(x) 以降を計算するプログラムを得ることができる。

任意の長さの文字列を変換するのにすべていっぺんに済ませてしまうのは、有限のプログラムでは無理があるため、実際には有限部分の変換を有限回くりかえして済ませる。有限部分を座標で決めるか、文字列のパターンで決めるか、それともあれするかでいくつかの計算機のモデルが考えられる。

チューリングマシン

2-記号チューリングマシンについて、有限の長さのテープから任意の値を受け取って任意の値を返す有限の関数を計算する有限のプログラムが、それぞれの返す値に存在することについて考える。ヘッドの位置はあとから有限のプログラムを追加してどこへでも動かすことができるので問題としない。

テープの長さが 1 のとき、考えうる関数は 0 を受け取って 0 を返す、0 を受け取って 1 を返す、1 を受け取って 0 を返す、1 を受け取って 1 を返すのいづれかであり、これらはそれぞれ一つだけの状態でプログラミングできる。

テープの長さが n のとき、考えうる任意の関数がプログラミング可能とし、n+1 の長さのときについて。長さが n のときの関数を計算するそれぞれのプログラムに、最後 n+1 マス目までヘッダを移動させるプログラムと、長さが 1 のときのプログラムを追加する。

以上より、任意の有限の関数を計算する過程を再現する有限のプログラムが任意に存在する(計算過程の再現や記述も計算のうちに入ると言えば入る)。

任意の計算過程は有限のプログラムで再現可能であり、再現するプログラムは実際に計算するプログラムより長くならずに済む。無限の定義域を持つ関数について、定義域を有限の範囲に制限し、それから元の定義域に向けて無限に広げていく過程で、それらの計算を再現するチューリングマシンの状態がどうしても無限に多くなっていくとき、その関数は計算不可能である。そうでなければ、つまり有限個の状態に収まるのであれば、その関数は計算可能である。

マルコフアルゴリズム

ソフトからの解釈

あるプログラムが読み取る言語がチューリング完全であるためには、(制限のない)再帰をそれぞれの表現で持つ必要があり、任意の再帰的表現を受け取ることができるプログラムはチューリング完全である。

再帰的表現の例

λ計算

Y コンビネータ

Y=(λx.λf.(x(ffx)))(λx.λf.(x(ffx)))

数列

pair=λx.λy.λf.(fxy)

pair a b で数列 (a,b) を表す。

3列以上の数列は2分木で表す。

pair x pair y z

無限数列にはYコンビネータを使う。

例 aが無限に続く数列

Yλx.(pair a x)

μ再帰関数

Δ_1関数

計算可能性と再帰が等価であることの証明

記述可能な証明を得るために、計算という概念を形式的な表現で記述する。チューリングマシンなどをそのまま採用してもいいが、集合論の表現でなんとかやってみる。

T //メモリ
Q //状態
 q_0 //初期状態
 h //停止状態 
δ:PAIR(T,Q)→PAIR(T,Q) //遷移関数
Count //ステップ数

遷移関数は何でもいいというものではなく、チューリング完全な計算機モデルであればほかのチューリング完全なモデルを再現できるものでなければならない。

計算可能であることは次のように定義される

Count=0→pair=<t_0,q_0>
∧∀n[(Count=n→pair=<t,q>)→(Count=n+1→pair=δ(<t,q>))]
∧∃n<ω[Count=n→pair=<t,h>]

遷移関数の定義は無数に考えられるが、

計算可能性⇒再帰の証明

時点

\((\lceil q\rceil;状態,\lceil σ\rceil;ヘッダの位置の情報,t_l;ヘッダから左側の情報,t_r;ヘッダから右側の情報)\)

遷移関数

\begin{eqnarray} δ(q,σ)=\left\{ \begin{array}{ll} λt_l.λt_r.f(\lceil q'\rceil,fst\ t_l,snd\ t_l,(\lceilσ'\rceil,t_r))\quad左へ移動する場合 \\ λt_l.λt_r.f(\lceil q'\rceil,fst\ t_r,(\lceilσ'\rceil,snd\ t_r)),\quad右へ移動する場合\\ λt_l.λt_r.(\lceil h\rceil,\lceilσ\rceil,t_l,t_r)\quad停止する場合\\ \end{array} \right. \end{eqnarray}

独自研究

この記事の最初に書かれた計算の定義を、単なる比喩や安易な思い込みを含む普遍的な世界観による定義ではなく、厳密に定義すると、「観測者がそれぞれの観測者による解釈=意味世界により『計算』とされる現象を観測した」と捉えられる。しかしこの解釈は計算機が属する宇宙を形式言語(有限の存在がが実際に扱えないものでもよい)に置き換えて説明するときに、チャーチ=チューリングのテーゼに反する場合も考えられる。しかし実在する計算機はその開発者によるプログラムのほかに、ニュートン力学や量子力学というこの宇宙のプログラムとされるものに則って動く、というよりは人間が作ったプログラム自体この宇宙のプログラムとされるものを前提として成り立っているため、有限の存在にとってもろもろの物理学の法則が絶対普遍の真理であると確かめようがない以上、より実際的で厳密な定義としてチャーチ=チューリングのテーゼを採用することはできないのではないか。ただこれはあくまでより実際的で厳密な定義の話で、恐れ多くもチャーチ=チューリングに反対するわけではない。

形式的な定義

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。