停止性問題

よくわからないままアーカイブしてます...^^; Orz...

http://ja.wikipedia.org/wiki/停止性問題　より
「停止性問題（ていしせいもんだい）は、チューリング機械（≒プログラム、アルゴリズム）Aに入力xを入れたら有限時間で停止するか、という問題。アラン・チューリングは1936年、停止性問題を解くチューリング機械が存在しない事を対角線論法で示した。すなわちそのようなチューリング機械の存在を仮定すると、自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止するような別のチューリング機械が構成できるという矛盾が導かれる。

プログラムAにデータxを入力して実行する事をA(x)と書き、A(x)がyを出力するときy=A(x)と書く。コンピュータではいかなるデータも0と1の数字で表し、したがってプログラム自身も0と1の数字で表せる。 コンピュータ用語ではこの数値化を「エンコード」と呼び、理論計算機科学では「ゲーデル数化」という。以下記号を簡単にする為、プログラムAを数字で表したものも、Aと書く。 よって例えばプログラムA、Bに対し、「A(B)」は、「プログラムBを表す数字をbとし、Aにbを入力して実行する」の意である。停止性問題とは、「プログラムAとデータxが与えられたとき、A(x)が有限時間で停止するかどうかを決定せよ」という問題である。
また「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。 すなわち以下の性質を満たすプログラムHは存在しない、という定理である。

全てのプログラムAと全てのデータxに対し、
A(x)が有限時間で停止する ⇒ H(A,x)は有限時間でYESを出力して停止する。
A(x)は有限時間では停止しない ⇒ H(A,x)は有限時間でNOを出力して停止する。
Hの定義より、Hは入力(A,x)によらず必ず停止する事に注意されたい。A(x)が停止するかどうかを、必ず停止するHを使って決定する事はできない、というのが定理の趣旨である。

証明
背理法で示す。証明は、嘘つきのパラドックスに類似した論法を使う。

停止性問題を常に正しく解くプログラムHが存在したとする。
M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとする。(H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。)
M(M)は停止するだろうか？
M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
M(M)が停止しないとすると、Mの定義よりH(M,M)=YES。Hの定義より、H(M,M)=YESとなるのはM(M)が停止するときのみなので、矛盾。
よって停止性問題を常に正しく解くプログラムHは存在しない。」

画像：アラン・チューリング
www.tamabi.ac.jp　より Orz〜
「（Alan Mathison Turing, 1912年6月23日 - 1954年6月7日）はイギリスの数学者。
・・・幼年期のアランは天才の片鱗を見せ始めた。文字を読むことは三週間で覚え、数字に強く、パズルが非常に得意だったという。6歳のとき両親は彼をセント・マイケルズ学校に入学させた。校長は、その後の彼の教師がそうだったように、すぐに彼の才能に気づいた。1926年、14歳のとき、彼はシャーボーン学校にも入学した。登校初日がゼネスト予定日と重なったため、彼は前日から100kmの距離を一人で自転車で行くことにして、途中で宿をとって登校した。このできごとは地元紙に掲載された。
・・・校長は両親に次のような手紙を書いている。「彼がふたつの学校の間で落ちこぼれないことを望みます。彼がパブリックスクールに留まるなら、彼は教養を身に付けねばなりません。彼が単に科学者になるのなら、パブリックスクールに通うのは時間の無駄です。」 (Hodges, 2000, p26)
このようなことがあっても、チューリングは学問に対する驚くべき能力を示し、初等微分積分学も習っていない1927年にもっと難しい問題を解いていた。1928年、アインシュタインの書いた文章に触れた16歳のチューリングは、その内容を理解しただけでなく、明記されていなかったニュートン力学についてのアインシュタインの疑問を外挿したという。・・・

大学時代と計算可能性についての研究
キングス・カレッジの計算機室はTuringと名づけられている
数学や科学ほど古典をまじめに学ばなかったため、チューリングはケンブリッジ大学トリニティ・カレッジの奨学金を受けられず、第二希望のケンブリッジ大学キングス・カレッジへ進学した。1931年から1934年まで学生として学び、優秀な成績を修めて卒業、1935年にガウス誤差関数に関する論文が認められてキングス・カレッジのフェロー（特別研究員）に選ばれた。
彼の重要な論文 "On Computable Numbers, with an Application to the Entscheidungsproblem"（「計算可能数、ならびにそのヒルベルトの決定問題への応用」、1936年5月28日）でチューリングは、チューリングマシンという概念を導入する事でアルゴリズムの概念を定式化し、1931年にゲーデルが発表した不完全性定理を別の形式で公式化した。
チューリングマシンは現在のコンピュータを先取りした概念で、今日から見ればコンピュータを抽象化したものであるともいえる。この論文でチューリングはまず、チューリングマシンを適切に設計すれば、いかなるアルゴリズムもチューリングマシンで実行可能である事を証明した。(万能チューリングマシン。今日でいうノイマン型コンピュータの理論的背景。)そしてこの事実を使い、「与えられたアルゴリズムが有限時間で停止するか？」という問題(停止性問題)を完全解決する事は不可能である事を示した。つまりチューリングは、コンピュータが実現されないうちに、コンピュータの理論的限界を示したのである。この証明はアロンゾ・チャーチのラムダ算法による同等の証明の直後に発表されたが、チューリングの論文のほうがずっとわかりやすく直感的であった。チューリングのこの論文ではまた決定可能数の記述法も導かれた。チューリングの成果と前後して「アルゴリズム」の概念が様々な方法で定式化されたが、それらは全て同値である事が後に示された(チャーチの提唱)。したがってチューリングは「アルゴリズム」の概念に最初に定式化を与えた人物の一人であるといえる。
チューリングマシンの停止判定不可能の証明は、コンピュータにはできないことがあることを示している。例えば、万能ウィルス発見プログラムは作れないし、プログラムが盗作かどうかを完璧に判定するプログラムも作れない。同様にプログラムにバグがあるかどうかを完璧に判定するプログラムも作れない。このことは、無駄なソフトウェア開発を防ぐという意味で有意義であった。
1937年から1938年にかけて彼はプリンストン大学においてアロンゾ・チャーチに師事し、1938年、プリンストンで博士号を得ている。博士論文では、数の広がり（正の整数→負数→無理数→虚数）とその公理体系の進化に関して、それらすべてを包含する「順序数」という概念の体系を整理しようとした。またこの時期、フォン・ノイマンも同じくプリンストンにおり、二人は親交があったと言われている。ノイマンはチューリングにアメリカに残ることを勧めたという。
1939年にケンブリッジに戻ると、彼はウィトゲンシュタインの数学基礎論という講義に出ている。ウィトゲンシュタインの数学批判に対して、チューリングは数学を擁護する立場を取った。・・・」

http://ja.wikipedia.org/wiki/チューリング機械　参照

画像：クルト・ゲーデル
optomo.biz　より Orz〜
「クルト・ゲーデル（1906年4月28日-1978年1月14日）は、現チェコ、ブルノ生まれの数学者・論理学者。完全性定理及び不完全性定理、連続体仮説の相対的無矛盾性などの業績が有名。その他、アインシュタインの一般相対性理論における「ゲーデル解」（1949年）（アインシュタインとは家族ぐるみで親密に交流）1970年台初頭には、ライプニッツによる「神の存在証明」を洗練し「ゲーデルの神の存在証明」などがある。1940年頃にはナチス・ドイツを逃れて妻アデルとアメリカ合衆国に移住したが、この時点ですでに人間不信に近い症状が出、晩年は精神にも失調をきたし、妻以外が作った食事は口にせず、妻の入院していた間に飢餓状態となり、プリンストン病院で死去。彼の絶筆はガベルスベルガーと呼ばれる古い速記法で書かれていたため、解読は出来なかったと言われる。」

天才達が集っていたプリンストン研究所でもノイマンは飛び抜けていたようですね・・・かのアインシュタインが自分よりノイマンの方頭が切れると言ってたそう・・・でもそのノイマンはおれよりゲーデルの方が優秀だと言ったとか・・・