Fandom

巨大数研究 Wiki

コメント0

計算可能性と再帰について

数学において「計算する」ということは、地形を変えて川の流れを変えたり、持ち上げたボールから手を離して「ボールが下に落ちた」という結果を観察したりすることと同じであり、「電卓に1+1を入力したら2という答えが返ってきた」というような具体的な現象のみを指すのではない。1+1=2や「ボールから手を離したら落ちた」というような簡単な計算であれば、計算機に頼らなくとも頭の中だけですぐに答えを導くことができるが、これらの完全に予測可能な自然現象をどんどん重ねることで、実質予測不可能なほどの計算をすることができるようになる(実際には完全に予測可能な自然現象は存在しないので、そういう意味では「完全に人工な」知能というものは存在しない。また、ここでいう予測不可能というのはカオスとは別の話なので注意)。

数学でいう「計算機」とは、電卓やパソコンのような実体ではなく、概念を意味する言葉であり、サイコロや障子や箪笥でも計算機となりうる。たとえばサイコロを振って出た目によってその日の運勢を占えば、その占いはサイコロによって計算可能ということになる。

計算可能性の定義には、以下に述べるように計算機の存在(具象)からの定義と、計算方法(抽象)からの定義が考えうる。

具象からの解釈

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

計算可能とは、定義域内の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関数

計算可能性と再帰の同値性

計算可能性⇒再帰の証明

時点

\((\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にアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWiki