アドバンスドトピック 計算できるものと計算できないもの 2008年4月9日 神林　靖

コンピュータサイエンスの誕生 世界初のコンピュータが完成したのは1946年 コンピュータサイエンスが誕生したのは1936年

ENIAC (1)

ENIAC (2)

ENIAC (3)

John Atanasoff

Atanasoff-Berry-Computer

「コンピュータサイエンス」とは？ コンピュータに何ができて、何ができないか？ 計算とはなにか？ 計算できる関数とはなにか？ 計算できない関数とはなにか？ コンピュータに何ができて、何ができないか？

「計算する」とは何か？ 記号を処理すること（ホッブス） コンピュータが行えることすべて

「計算を定義するもの」 帰納的関数 ラムダ計算 チューリングマシン

二進法 (1) 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 1010

二進法 (2) 100 101 +) 1001

子ザル・モデル（１） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

子ザル・モデル（２） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

子ザル・モデル（３） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

子ザル・モデル（４） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

子ザルモデル（番外編）

子ザル・モデルが達成したこと 101 1011 N 2N+1

アラン・チューリング

チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態 チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態 チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態 チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態 チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

チューリングマシン Ｍ １ ０ １ １ B B T 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態 チューリングマシン 　Ｍ 無限長のテープ １ ０ １ １ B B ヘッド T 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

チューリングマシンの例 チューリングマシンで何ができるか、見てみよう 別のパワーポイントへ

チューリングマシンの符号化 チューリングマシンのテープと状態遷移関数を０と１の列で符号化する。 2019/4/14 チューリングマシンの符号化 チューリングマシンのテープと状態遷移関数を０と１の列で符号化する。 符号化したチューリングマシンをテープ上に書き込む。 そうしたテープを読み込んで、元のチューリングマシンの動作を模倣するチューリングマシンを作成できる。 それって、コンピュータのことですかい？

2019/4/14 万能チューリングマシン　Ｕ 元のチューリングマシンの符号 元のチューリングマシンへの入力 作業領域 S 有限制御部 A B C 無限長のテープ 万能チューリングマシンＵは、元のチューリングマシンＭへの入力（Ｂ）と、Ｍの状態遷移関数（Ａ）を見ながら、Ｍの動作を模倣する。

チューリングマシンの停止性判定問題 チューリングマシンＭとそれへの入力ｘが与えられたときに、Ｍがｘに対して停止するか否かを判定せよ。

計算不可能であることの証明（１） x1 x2 x3 … xj … M1 M2 M3 … Mi a11 a12 a13 … a1j … すべてのチューリングマシンを書き出してみる。 x1 x2 x3 … xj … M1 M2 M3 … Mi a11 a12 a13 … a1j … a21 a22 a23 … a2j … a31 a32 a33 … a3j … … … … ai1 ai2 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=[与えられた解答をｎｃの計算時間で確認できる判定問題の集合]

帰着可能性 (NP完全問題) 判定問題A 判定問題B Algorithm Y Algorithm X Yes/No Yes/No

NP完全問題 NPに属するすべての問題Aに対して、AはBに多項式時間で帰着可能である。 問題Bは、クラスNPに属する。 NP完全問題を解く多項式時間で解くアルゴリズムXが存在すれば、NP ⊆ Pとなる。

思い出話 １９８０年当時のコンピュータメーカー IBM Burroughs UNIVAC NCR CDC Honeywell 富士通+日立+NEC+東芝+三菱電機+沖電気

ソフトウェア会社の栄華盛衰 (1) 1984年 1 MicroPro $60,000 2 Microsoft $55,000 3 Lotus $53,000 4 Digital Research $45,000 5 VisiCorp $43,000 6 Ashton-Tate $35,000 7 Peachtree $21,700 8 MicroFocus $15,000 9 Software Publishing $14,000 10 Borderbund $13,000

ソフトウェア会社の栄華盛衰 (2) 2001年 1 Microsoft $23,845,000 2 Adobe $1,266,387 3 Novell $1,103,592 4 Intuit $1,076,000 5 Autodesk $926,324 6 Symantec $790,153 7 Network Associates $745,692 8 Citrix $479,446 9 Macromedia $295,997 10 Great Plains $250,231

第五世代コンピュータ (1) 並列論理型コンピュータ 人間はいつか死ぬ p→q 彼は仙人である r→s 仙人は死なない s→￢q 彼は人間ではない r→￢p

第五世代コンピュータ (2)

私の研究室でやっていること 移動エージェントを使ったロボットの制御

課題 感想文 注 意：用紙はＡ４版２枚。ワープロ打ち とする。 1枚目に概要、2枚目に感想。 提出期限：4月16日 午前13時まで（厳守） 注　　意：用紙はＡ４版２枚。ワープロ打ち 　　とする。 　　　　　1枚目に概要、2枚目に感想。 提出期限：4月16日　午前13時まで（厳守） 提出場所：情報工学科事務室前 　　　　　レポート提出用ポスト