5 計算のモデル 5.1,5.2 コンピュータ・CPUの動作原理 5.3 計算の数学的

5.1,5.2 コンピュータ・CPU の動作原理
5 計算のモデル
• 機械語
5.1,5.2 コンピュータ・CPU の動作原理
• レジスタ
5.3 計算の数学的モデル
ストアードメモリ方式 : プログラムもデータとして格納
3
2
1
5.3.1 チューリング機械
5.3 計算の数学的モデル
チューリング機械 (TM) :
• 無限テープ
• テープの記号と状態から動作を (非決定的に) 決める
• チューリング機械
• 動作は、次の状態・テープに書き込む記号・ヘッドの移動
• レジスタ機械、
M = (Q, Σ, Γ, δ, q0)
• Q: 状態の有限集合
• Σ: 入出力記号の有限集合
• λ 計算、
• Γ: テープ記号の有限集合 (Γ ⊇ Σ ∪ {B})
• 項書換え系、
• δ: 遷移関数 (δ : Q × Γ → Q × (Γ ∪ {L, R}))
などなど
• q0: 初期状態 (q0 ∈ Q)
4
5
6
5.3.2 帰納的関数
時点表示 : 状態が q でヘッドの位置が以下のとき、
例 : f (x, y) = x + y を満たす f : N2 → N を計算する
チューリング機械
原始帰納的関数 : 自然数 N 上の関数のクラス
原始帰納的関数の定義
• 零関数、次者関数、射影関数
def
zero: N0 → N ただし、zero() = 0
a1qa2 · · · an
def
suc: N → N ただし、suc(x) = x + 1
と書く
def
n
n
pn
i : N → N ただし、pi (x1, . . . , xn) = xi
• 合成関数、すなわち、g : Nm → N と gj : Nn → N が原
• 入力 1011 に対する動作
q01011 ⊢ 1q0011 ⊢ 1q1111 ⊢ 11q111 ⊢
111q11 ⊢ 1111q1 ⊢ 111q21 ⊢ 111q2 ⊢
11q31 ⊢ 1q311 ⊢ q3111 ⊢ q3B111 ⊢
q4111
チューリング機械が定義する自然数上の計算 :
q01k1 01k2 0 · · · 01kn ⊢∗ q1m
は f (k1, . . . , kn) = m
始帰納的関数のとき、
f (~
x) = g(g1(~
x), . . . , gm(~
x))
で定義される関数 f : Nn → N は原始帰納的関数
7
原始帰納的関数の例 (続き)
(
· y = x − y if x >= y
• x−
0
otherwise
を計算する関数 sub(x, y) なぜなら
原始帰納的関数の例
def
• one() = 1 なぜなら 1 = suc(zero())
原始帰納的関数の定義 (続き)
def
• two() = 2 なぜなら 2 = suc(one())
• 原始帰納法で定義された関数、すなわち、
sub(x, 0) = x
sub(x, y + 1) = prod(sub(x, y))
def
g : Nn → N と h : nn+2 → N が原始帰納的関数のと
き、
f (~
x, 0) = g(~
x)
· 1 なぜなら
• pred(x) = x −
pred(0) = 0 (= zero())
pred(y + 1) = y (= p2
1(y, pred(y)))
• x × y を計算する関数 mult(x, y) なぜなら
mult(x, 0) = 0
mult(x, y + 1) = add(x, mult(x, y))
def
• add(x, y) = x + y なぜなら
f (~
x, y + 1) = h(~
x, y, f (~
x, y))
で定義される関数 f : Nn+1 → N は原始帰納的関数
add(x, 0) = x (= p1
1(x))
add(x, y + 1) = suc(add(x, y))
(= h(x, y, add(x, y)))
問 : 関数 exp(x, y) = xy 、fact(x) = x!、min(x, y)
が原始帰納的であることを示せ。(ここで 00 の値は問わ
ここで、h(x, y, z) = suc(p3
3(x, y, z)) は原始帰納的
10
9
8
11
ない)
12
補題 : 原始帰納的関数 f (~
x, y) を利用して次のように定義
される f ′(~
x, y) と f ′′(~
x, y) は原始帰納的関数である
f ′(~
x, y) =
f ′′(~
x, y) =
X
z<y
Y
f (~
x, z) = f (~
x, 0)+· · ·+f (~
x, y−1)
z<y
f (~
x, z) = f (~
x, 0)×· · ·×f (~
x, y−1)
証明 : f ′ のみ示し、f ′′ は省略
定理 原始帰納的関数はチューリング機械で計算できる
略証 (続き)
略証 : 原始帰納的関数の構成に関する帰納法
• zero(), suc(), pn
i (x1, . . . , xn) はチューリング機械
で計算できる
• 合成
g : Nm → N と gj : Nn → N を計算するチューリング
f ′(~
x, 0) = 0
f ′(~
x, y + 1) = f ′(~
x, y) + f (~
x, y)
機械があると仮定し、g(g1(~
x), . . . , gm(~
x)) はチューリ
ング機械で計算できることを示す
13
• 原始帰納法
g : Nn → N と h : Nn+2 → N を計算するチューリング
機械があると仮定し、以下で定義される f がチューリン
グ機械で計算できることを示す



f (~
x, 0) = g(~
x)
f (~
x, y + 1) = h(~
x, y, f (~
x, y))
15
14
補題 p(~
x), q(~
x), r(~
x, y) が原始帰納的述語なら、次の述
例 : 述語「=0」 (=0(x) を x = 0 と書くことにする)
原始帰納的述語
c=0(x) =  0 · · · x が 0 のとき
1 · · · x が 0 でないとき
·
· x) と書けるので、c
c=0(x) = 1 − (1 −
=0 は原始帰納


• (n 変数) 述語: p : Nn → { 真, 偽 }
• 述語 p の特徴関数 cp : Nn → N
的関数である。よって「=0」は原始帰納的述語
x) = 真のとき
cp(~
x) =  0 · · · p(~
1 · · · p(~
x) = 偽のとき


例 : 述語「x = y 」、「x ≤ y 」は原始帰納的。なぜなら、
· y) + (y −
· x))
c=(x, y) = c=0((x −
def
• 述語 p が原始帰納的 ⇐⇒ cp が原始帰納的
c≥(x, y) = c=0
語も原始帰納的
(1) ¬p(~
x)
(2) p(~
x) ∨ q(~
x)
(4) (∃z < y) r(~
x, z)
(3) p(~
x) ∧ q(~
x)
(5) (∀z < y) r(~
x, z)
(6) p(f1(~
x), . . . , fn(~
x)) (ここで fi は原始帰納的)
証明 : (3),(5) はそれぞれ (2),(4) で表せる
· c (~
(1) c¬p(~
x) = 1 −
p x)
(2) cp∨q (~
x) = cp(~
x) × cq (~
x)
(4) 述語を s(~
x, y) とかく。cs(~
x, y) =
· y)
(x −
(6) 述語を p′(~
x) とかく。
Y
z<y
cr (~
x, z)
cp′ (~
x) = cp(f1(~
x), . . . , fn(~
x))
16
17
18
p(~
x, y) の限定最小解関数 : y 未満で p(~
x, z) を満たす z ∈
N があればその最小の z を返し、そうでなければ y を返
例 : 次の述語は原始帰納的
す関数
µz<y p(~
x, z)
def
= min({z ∈ N | z < y, p(~
x, z)} ∪ {y})
•x<y
• x×y =z
(x > 1) ∧ (¬(∃u < x)(∃v < x) (u × v = x))
と書く。
Y
z≤v
cp(~
x, z) を g(~
x, v)
def
• pr(x) = x 番目の素数
• 合成関数 (帰納的関数の合成)
∵ (原始帰納的帰納関数は全域的だが、fM は一般には
• 原始帰納法 (帰納的関数を用いた原始帰納法)
部分関数)
• 原始帰納的述語の最小解関数
関数のクラスと一致する
は原始帰納的。なぜなら
pr(0) = 2
pr(x + 1) =
µz<pr(x)!+2((pr(x) < z) ∧ prime(z))
• 部分関数 f と g は以下を満たすとき等価である (f = g)
という
- 同一の引数を与えたとき、一方が未定義なら他方も未
定義であり、そうでなければ結果が一致する
22
• 原始帰納的関数
M が存在
• 帰納的関数のクラスは、チューリング機械で計算できる
(例：pr(0) = 2, pr(1) = 3)
21
帰納的関数の定義
• 原始帰納的でない関数 fM を計算するチューリング機械
x ÷ y = µz<x(x < (y × (z + 1)))
ii) y 未満では p(~
x, z) を満たす z がないとき
v
0 1 ··· y − 1
cp(~
x, v) 1 1 · · · 1
g(~
x, v) 1 1 · · · 1
X
よって、
g(~
x, v) = y
v<y
帰納的関数
• x ÷ y は原始帰納的。なぜなら
g(~
x, v) = m
20
19
例:
X
v<y
始帰納的関数
証明 : (∃z ≤ v) p(~
x, z) の特徴関数
v
0 1 ··· m − 1 m m + 1 ··· y − 1
cp(~
x, v) 1 1 · · ·
1
0
∗
··· ∗
1
0
0
··· 0
g(~
x, v) 1 1 · · ·
ここで ∗ は 0 または 1
よって、
補題 p(~
x, y) が原始帰納的述語ならば、µz<y p(~
x, z) は原
def
• prime(x) ⇐⇒
i) p(~
x, z) を満たす最小の z が m (< y) のとき
23
述語 p の最小解関数 :
µz p(~
 x, z)

· · · p(~
x, y) を満たす z ∈ N が存在するとき
=z
未定義 · · · それ以外のとき
帰納的関数の例 : f (x) = µz (z 2 = x)
x 0 1 2 3 4 5 ···
f (x) 0 1 未 未 2 未 · · ·
24
5.3.3 計算モデルの同等性
アッカーマン関数 : 帰納的だが原始帰納的でない関数
定理 帰納的関数はチューリング機械で計算できる
証明 : 帰納的関数の構成に関する帰納法
• 14 ページの定理 [原始帰納的関数は TM で計算できる]
• 原始的述語 p の最小解関数 µz p(~
x, z) がチューリング機
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
問 5.5 (text p.141) 急激に大きくなる関数で、限定最
小解関数では書けない
械で計算できることを示す
• 上の定理の逆も成立する
25
26