アドバンスドトピック
計算できるものと
計算できないもの
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
子ザル・モデル(1)
西野哲郎著「中国人郵便配達問題=コンピュータサイエンス最大の難関」講談社選書メチエ より
子ザル・モデル(2)
西野哲郎著「中国人郵便配達問題=コンピュータサイエンス最大の難関」講談社選書メチエ より
子ザル・モデル(3)
西野哲郎著「中国人郵便配達問題=コンピュータサイエンス最大の難関」講談社選書メチエ より
子ザル・モデル(4)
西野哲郎著「中国人郵便配達問題=コンピュータサイエンス最大の難関」講談社選書メチエ より
子ザルモデル(番外編)
子ザル・モデルが達成したこと

101
1011

N
2N+1
アラン・チューリング
チューリングマシン M
無限長のテープ
1 0
1
B
B
B
ヘッド
S 有限制御部
状態遷移関数
現在状態
現在記号
次の状態
新記号
移動方向
S
0
S
0
R
S
S
1
B
S
T
1
1
R
N
チューリングマシン M
無限長のテープ
1 0
1
B
B
B
ヘッド
S 有限制御部
状態遷移関数
現在状態
現在記号
次の状態
新記号
移動方向
S
0
S
0
R
S
S
1
B
S
T
1
1
R
N
チューリングマシン M
無限長のテープ
1 0
1
B
B
B
ヘッド
S 有限制御部
状態遷移関数
現在状態
現在記号
次の状態
新記号
移動方向
S
0
S
0
R
S
S
1
B
S
T
1
1
R
N
チューリングマシン M
無限長のテープ
1 0
1
B
B
B
ヘッド
S 有限制御部
新記号
状態遷移関数
現在状態
現在記号
次の状態
移動方向
S
0
S
0
R
S
S
1
B
S
T
1
1
R
N
チューリングマシン M
無限長のテープ
1 0
1 1 B
B
ヘッド
T 有限制御部
新記号
状態遷移関数
現在状態
現在記号
次の状態
移動方向
S
0
S
0
R
S
S
1
B
S
T
1
1
R
N
チューリングマシンの例

チューリングマシンで何ができるか、
見てみよう
 別のパワーポイントへ
チューリングマシンの符号化



チューリングマシンのテープと状態遷移
関数を0と1の列で符号化する。
符号化したチューリングマシンをテープ
上に書き込む。
そうしたテープを読み込んで、元のチュー
リングマシンの動作を模倣するチューリ
ングマシンを作成できる。
それって、コンピュータのことですかい?
万能チューリングマシン U
A
元のチューリン
グマシンの符号
B
元のチューリング
マシンへの入力
C
作業領域
無限長のテープ
S 有限制御部

万能チューリングマシンUは、元の
チューリングマシンMへの入力(B)と、
Mの状態遷移関数(A)を見ながら、M
の動作を模倣する。
チューリングマシンの停止性
判定問題

チューリングマシンMとそれへの入力x
が与えられたときに、Mがxに対して停
止するか否かを判定せよ。
計算不可能であることの証明(1)
すべてのチューリングマシンを書き出してみる。
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。
計算不可能であることの証明(2)

Mが入力xiに対して停止するのは、表
中のチューリングマシンMiがxiに対し
て停止しないとき、かつその時に限る。
というチューリングマシンがどこかにあ
るはずだから、探しなさい。
計算不可能であることの証明(3)

MはMiではありえない。なぜなら、 Mi
がxi対して停止しないとき Mは停止し、
Miがxi対して停止するときにはMは停
止しないからである。
え~!矛盾じゃ~ん!
すべてのチューリングマシンを網羅する表は構成できない。
チューリングマシンの停止性判定問題は計算不可能である。
ENIGMA (1)
ENIGMA (2)
ENIGMA (3)
アラン・チューリングと仲間
理論的に可能でも、
現実には不可能な問題



P = NP?
アルゴリズムの例
クリーク問題
 グラフと3以上の整数kが与え
られたとき、k個の頂点からな
る完全グラフがあるか?
公開鍵暗号 (1)





2つの素数 (p, q) を求める
N = p×q
L = lcm(p-1, q-1)
gcd(E, L) = 1 となる E を求める
E×D mod L = 1となる D を求める
公開鍵暗号 (2)

暗号文 = 平文E mod N

平文 = 暗号文D mod N
暗号解読には、素因数分解が決め手
(でも、たいへん!)
P = NP?問題



P=[ncの計算時間で解ける判定
問題の集合]
NP=[与えられた解答をncの計算
時間で確認できる判定問題の集
合]
P ⊆ NP
帰着可能性
(NP完全問題)
判定問題A
Yes/No
Algorithm X
Algorithm Y
判定問題B
Yes/No
NP完全問題



NPに属するすべての問題Aに対し
て、AはBに多項式時間で帰着可
能である。
問題Bは、クラスNPに属する。
NP完全問題を解く多項式時間で
解くアルゴリズムXが存在すれば、
NP ⊆ Pとなる。
思い出話

1980年当時のコンピュータメーカー
 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)
私の研究室でやっていること

移動エージェントを使ったロボットの制御
課題

注
感想文
意:用紙はA4版2枚。ワープロ打ち
とする。
1枚目に概要、2枚目に感想。
提出期限:4月16日 午前13時まで(厳守)
提出場所:情報工学科事務室前
レポート提出用ポスト
ダウンロード

アドバンスドトピック(神林)