計算不可について解らない事

以下、何となく書く事。

数学的に計算不可能な問題には以下の2パターンがあると考える?

①計算量が膨大
以下は、youtubeの動画『「フカシギの数え方」おねえさんといっしょ!みんなで数えてみよう!』へのリンク。



巡回経路問題の話?1秒間に2000億回の経路計算が可能なスーパーコンピューターを使用しても、宇宙創成137億年以上の計算時間が必要。あまりに長い時間が解答に必要とされるので、実質的に計算不可能。

②自己言及を含む問題?
チューリング・マシンの問題。この辺りが解らない。

提示された計算式に対して、計算可否を判定出来る計算機械は存在しない事を証明する。

<停止性判定>
計算式の計算可否を判定出来る計算機械とは、計算作業が永続するかどうかを判定出来る計算機械である。上記①のyoutubeの動画で計算されている問題は、長い時間をかければ計算可能な問題である。一方で、円周率の計算のように永久に終了しない計算もある。

<背理法>
(1)計算可否を判定出来るコンピュータープログラムHが
  存在すると仮定する。

Hは以下のように動作する。

・入力された計算式Mの計算が終了するのならYESを出力する。
・入力された計算式Mの計算が終了しないのならNOを出力する。

(2)上記のコンピュータープログラムHを改造した
  コンピュータープログラムH´の存在を仮定する。

H´は以下のように動作する。

・入力された計算式Mの計算が終了するのなら計算が終了しない。
・入力された計算式Mの計算が終了しないのならNOを出力する。

(3)この時、H´自体をH´への入力情報とする事が可能である。

あるコンピュータープログラムへの入力情報が、プログラムのソースコードであっても構わない事という事らしい。例えば、プログラムのソースコードの語数を数える「語数カウントプログラム」が存在する場合、「語数カウントプログラム」のソースコード自体を「語数カウントプログラム」への入力情報とする事も可能である。

⇒一つの情報をコンピュータープログラムとしても、入力情報としても扱えるという事が、問題を理解するポイントであるらしい。

(4)H´自体をH´の入力とする場合を考える。
以下のような問題が発生する。

・入力情報をH´とする計算が終わる場合
 ⇒H´の計算が終わらない。

・入力情報をH´とする計算が終わらない場合
 ⇒NOが出力され、H´の計算が終わる。

上記のように、H´への入力情報をH´とすると矛盾が生じる。従って、計算可否を判定出来るコンピュータープログラムHは存在不可能とする。

***********

僕が解らないのは、どうしてH´を仮定しなくてはならないのかだ。

以下は、オートマトンやらチューリングマシンやらについて書かれた「白と黒のとびら」。第13章以降が解らない。



人気ブログランキングへ
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

ABCDEFG

Author:ABCDEFG
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード