アドバンスドトピック計算できるものと計算できないもの 2008年4月9日神林靖コンピュータサイエンスの誕生  世界初のコンピュータが完成したのは1946年  コンピュータサイエンスが誕生したのは1936年 ENIAC (1) ENIAC (2) ENIAC (3) John Atanasoff Atanasoff-Berry-Computer 「コンピュータサイエンス」とは？    計算とはなにか？計算できる関数とはなにか？計算できない関数とはなにか？  コンピュータに何ができて、何ができないか？「計算する」とは何か？  記号を処理すること（ホッブス）  コンピュータが行えることすべて「計算を定義するもの」    帰納的関数ラムダ計算チューリングマシン二進法 (1) 1 2 3 4 5 6 7 8 9 10 1 10 11 100 101 110 111 1000 1001 1010 二進法 (2) +) 100 101 1001 子ザル・モデル（１）西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエより子ザル・モデル（２）西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエより子ザル・モデル（３）西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエより子ザル・モデル（４）西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエより子ザルモデル（番外編）子ザル・モデルが達成したこと  101 1011  N 2N+1 アラン・チューリングチューリングマシンＭ無限長のテープ１０１ B B B ヘッド S 有限制御部状態遷移関数現在状態現在記号次の状態新記号移動方向 S 0 S 0 R S S 1 B S T 1 1 R N チューリングマシンＭ無限長のテープ１０１ B B B ヘッド S 有限制御部状態遷移関数現在状態現在記号次の状態新記号移動方向 S 0 S 0 R S S 1 B S T 1 1 R N チューリングマシンＭ無限長のテープ１０１ B B B ヘッド S 有限制御部状態遷移関数現在状態現在記号次の状態新記号移動方向 S 0 S 0 R S S 1 B S T 1 1 R N チューリングマシンＭ無限長のテープ１０１ B B B ヘッド S 有限制御部新記号状態遷移関数現在状態現在記号次の状態移動方向 S 0 S 0 R S S 1 B S T 1 1 R N チューリングマシンＭ無限長のテープ１０１１ B B ヘッド T 有限制御部新記号状態遷移関数現在状態現在記号次の状態移動方向 S 0 S 0 R S S 1 B S T 1 1 R N チューリングマシンの例  チューリングマシンで何ができるか、見てみよう  別のパワーポイントへチューリングマシンの符号化    チューリングマシンのテープと状態遷移関数を０と１の列で符号化する。符号化したチューリングマシンをテープ上に書き込む。そうしたテープを読み込んで、元のチューリングマシンの動作を模倣するチューリングマシンを作成できる。それって、コンピュータのことですかい？万能チューリングマシンＵ A 元のチューリングマシンの符号 B 元のチューリングマシンへの入力 C 作業領域無限長のテープ S 有限制御部  万能チューリングマシンＵは、元のチューリングマシンＭへの入力（Ｂ）と、Ｍの状態遷移関数（Ａ）を見ながら、Ｍの動作を模倣する。チューリングマシンの停止性判定問題  チューリングマシンＭとそれへの入力ｘが与えられたときに、Ｍがｘに対して停止するか否かを判定せよ。計算不可能であることの証明（１）すべてのチューリングマシンを書き出してみる。 x2 x3 … xj … M1 a11 a12 a13 … a1j … M2 a21 a22 a23 … a2j … M3 a31 … a32 … ai2 a33 … … … a3j … … … x1 Mi ai1 ai3 aij チューリングマシンMiが入力xjに対して、停止するならば aij =1、さもなければ、 aij =0。計算不可能であることの証明（２）  Mが入力xiに対して停止するのは、表中のチューリングマシンMiがxiに対して停止しないとき、かつその時に限る。というチューリングマシンがどこかにあるはずだから、探しなさい。計算不可能であることの証明（３）  MはMiではありえない。なぜなら、 Mi がxi対して停止しないとき Mは停止し、 Miがxi対して停止するときにはMは停止しないからである。え～！矛盾じゃ～ん！すべてのチューリングマシンを網羅する表は構成できない。チューリングマシンの停止性判定問題は計算不可能である。 ENIGMA (1) ENIGMA (2) ENIGMA (3) アラン・チューリングと仲間理論的に可能でも、現実には不可能な問題    P = NP？アルゴリズムの例クリーク問題  グラフと3以上の整数ｋが与えられたとき、ｋ個の頂点からなる完全グラフがあるか？公開鍵暗号（１）      ２つの素数 (p, q) を求める N = p×q L = lcm(p-1, q-1) gcd(E, L) = 1 となる E を求める E×D mod L = 1となる D を求める公開鍵暗号（２）  暗号文 = 平文E mod N  平文 = 暗号文D mod N 暗号解読には、素因数分解が決め手（でも、たいへん！） P = NP？問題    P=[ｎｃの計算時間で解ける判定問題の集合] NP=[与えられた解答をｎｃの計算時間で確認できる判定問題の集合] P ⊆ NP 帰着可能性 (NP完全問題) 判定問題A Yes/No Algorithm X Algorithm Y 判定問題B Yes/No NP完全問題    NPに属するすべての問題Aに対して、AはBに多項式時間で帰着可能である。問題Bは、クラスNPに属する。 NP完全問題を解く多項式時間で解くアルゴリズムXが存在すれば、 NP ⊆ Pとなる。思い出話  １９８０年当時のコンピュータメーカー  IBM  Burroughs  UNIVAC  NCR  CDC  Honeywell  富士通+日立+NEC+東芝+三菱電機+沖電気ソフトウェア会社の栄華盛衰 (1) 1984年 1 2 3 4 MicroPro Microsoft Lotus Digital Research $60,000 $55,000 $53,000 $45,000 5 6 7 VisiCorp Ashton-Tate Peachtree $43,000 $35,000 $21,700 8 MicroFocus $15,000 9 Software Publishing 10 Borderbund $14,000 $13,000 ソフトウェア会社の栄華盛衰 (2) 2001年 1 2 3 4 Microsoft Adobe Novell Intuit 5 6 7 Autodesk Symantec Network Associates $926,324 $790,153 $745,692 8 Citrix $479,446 9 Macromedia 10 Great Plains $23,845,000 $1,266,387 $1,103,592 $1,076,000 $295,997 $250,231 第五世代コンピュータ (1)  並列論理型コンピュータ  人間はいつか死ぬ彼は仙人である仙人は死なない p→q r→s s→￢q  彼は人間ではない r→￢p   第五世代コンピュータ (2) 私の研究室でやっていること  移動エージェントを使ったロボットの制御課題  注感想文意：用紙はＡ４版２枚。ワープロ打ちとする。 1枚目に概要、2枚目に感想。提出期限：4月16日午前13時まで（厳守）提出場所：情報工学科事務室前レポート提出用ポスト