日本語 - 北海道大学

チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
計算理論
Thomas Zeugmann
北海道大学 大学院情報科学研究科
アルゴ リズ ム研究室
http://www-alg.ist.hokudai.ac.jp/∼thomas/ToC/
第 12 回： チ ュー リング 機械
(日本語訳： 湊 真一， 大久保 好章)
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 機械 I
部分帰納的関数 (partial recursive function) を扱っ た 後は，アラ
ン-チューリングに より提案された チューリング機械 (Turing
machine) に 注目するこ とに し よう ．
彼の アイデアは，第 11 回の 講義で述べた ，アルゴリズムの 4 つの
性質を用いて「直感的な計算可能」 な関数という 概念を形式的に
表すこ とで ある．まず 始めに 彼が行っ た の は，機械の 基本的な演
算を，すべての アルゴリズムを実行可能な最小限の レベルに 絞り
込むこ とで あっ た ．話を単純に するた め，こ こ で は 1 テープ
チューリング機械 (one-tape Turing machine) を考え る．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
万能 TM
チャーチの 提唱
おわり
チ ュー リング 機械 II
1 テープ チューリング機械は，多数の セルに 分割された 無限長の
テープを持つ．個々の セルは，た だ 1 つの テープ記号
(tape-symbol) を記入で き る．入力値が実際に 書き 込まれている
セル以外に は，初期値とし て記号 ∗ が入っ ていると仮定する．
我々は，テープの セルを図 1 の よう に 数え るもの とする．
5
4
*
3
*
2
*
1
*
0
*
1
b1
2
b2
3
b3
4
*
5
*
図 1: 入力 b1 b2 b3 を持つチューリング機械の テープ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 機械 III
さらに ，チューリング機械は読み書き ヘッドを持つ．こ の ヘッド
は 1 度に 1 つの セルを見るこ とがで き る．そ し てこ の 機械は，有
限個の 状態を持ち，実行する命令の 集合を持っ ている．こ の 機械
は，最初は必ず 開始状態 zs に あり，ヘッドは入力の 最も左の セル
0 を見ている．我々はヘッドの 位置を矢印で 表すこ ととする．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 機械 III
さらに ，チューリング機械は読み書き ヘッドを持つ．こ の ヘッド
は 1 度に 1 つの セルを見るこ とがで き る．そ し てこ の 機械は，有
限個の 状態を持ち，実行する命令の 集合を持っ ている．こ の 機械
は，最初は必ず 開始状態 zs に あり，ヘッドは入力の 最も左の セル
0 を見ている．我々はヘッドの 位置を矢印で 表すこ ととする．
さて，こ の 機械は以下の よう に 動作する．ある状態 z に おいて，
テープ記号 b を読んだとき ，そ の セルに 記号 b 0 を書き 込み，状
態を z 0 に 遷移し ，ヘッドを左 (L と書く ) また は右 (R と書く ) に 移
動するか，ヘッドを動かさない (N と書く )，という 動作を，
(z, b, b 0 , H, z 0 ) の 組 (た だし H ∈ {L, N, R}) で 与え られるチューリ
ング機械の 命令に し た がっ て実行する．1 つの 命令の 実行をス
テッ プ (step) と呼ぶ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 機械 IV
こ の 機械は，特別 (distinguished) な状態 zf (終了状態) に 到達し た
とき ，停止するもの とする．以上より，チューリング機械を以下
の よう に 定義するこ とがで き る．
定義 1
M = [B, Z, A] は，以下を満た すとき 決定性 1 テー プ チ ュー リン
グ 機械 (deterministic one-tape Turing machine) と呼ばれる．す
なわち， B, Z, A が空で ない有限集合で あっ て， B ∩ Z = ∅ かつ
(1) card(B) > 2
( B = {∗, |, . . .} )
(2) card(Z) > 2
( Z = {zs , zf , . . .})
(テープ記号),
(状態集合 ),
(3) A ⊆ Z \ {zf } × B × B × {L, N, R} × Z (命令集合), た だし そ
れぞれの z ∈ Z \ {zf } と，そ れぞれの b ∈ B に 対し て，た だ 1
つの 5 個組 (z, b, ·, ·, ·) が決まっ ているこ と．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 機械 V
命令集合 A は，し ばし ば表形式で 書かれる．例え ば，
∗
zs
z1
·
·
·
zn
b 0 Nz
|
b2
...
bn
3
·
·
·
·
·
チューリング表
もし も命令集合が小さけ れば， (z, b, b 0 , H, z 0 ) と書く 代わりに ，
zb → b 0 Hz 0 (た だし H ∈ {L, N, R}) と書く 方が便利なこ とが多い．
また ，チューリング機械 M の 命令集合の こ とを，通常， M の プ
ロ グ ラ ム (program) と言う ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 計算 I
次に ，チューリング機械がど の よう に し て関数を計算するかを説
明し なけ ればならない．我々がまず 興味を持つ対象は， Nn から
N への 関数，すなわち，f : Nn → N である．し た がっ て入力は，
(x1 , . . . , xn ) ∈ Nn なる組で ある．
こ こ で は， xi と xi+1 を分け るた め，特殊なテープ記号 # を予約
するこ とに する．さらに ，以下で は話を簡単に するた め，数値は
1 進数 (unary) で 符号化されているもの とする．例え ば 0 は ∗ と
表現され， 1 は | と表し ， 2 は ||，3 は ||| とし ，以下同様とする．
なお，チューリング計算の 計算量 (complexity) を気に し ない限り
は，こ の 記法は何ら制約に はならない．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 計算 II
さらに ，次の 記法を導入すると便利で ある．任意の 関数
f : Nn → N に おいて，ある入力 (x1 , . . . , xn ) ∈ Nn の 組に 対する
f(x1 , . . . , xn ) の 値が未定義で あるとき ， f(x1 , . . . , xn ) ↑ と書く こ
とに する．一方， f(x1 , . . . , xn ) が定義されている場合は，
f(x1 , . . . , xn ) ↓ と書く こ ととする．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 計算 III
定義 2
任意の チューリング機械 M と，任意の n ∈ N+ と，任意の 関数
f : Nn → N を考え る．もし もすべての (x1 , . . . , xn ) ∈ Nn に 対し
て，以下の 条件を満た すならば， M は関数 f を計算する
(compute) と言う ．
(1) もし も f(x1 , . . . , xn ) ↓ で あっ て， x1 # . . . #xn が M の 空の
テープに 書かれていて， M の 初期ヘッド位置が x1 # . . . #xn
の 最も左に あり，初期状態が zs で あるならば， M は有限ス
テップ実行後に 状態 Zf で 停止する．さらに ，もし も
f(x1 , . . . , xn ) = 0 で あれば， M が状態 zf に おいて読める記
号は ∗ である．もし も f(x1 , . . . , xn ) , 0 であれば，M が状態
zf に おいて読めるセルから始まる連続し た | の 列（左から右
へ向かっ て読むとする）が計算結果を表す (図 2 を参照)．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
5
4
*
定理の 証明
3
*
2
*
1
*
0
*
万能 TM
チャーチの 提唱
1
|
2
|
3
|
4
*
おわり
5
*
zf
図 2: 計算結果 3 ( ||| ) を示すチューリング機械の テープ．
定義 3 (続き )
(2) もし も f(x1 , . . . , xn ) ↑ で あっ て， x1 # . . . #xn が M の 空の
テープに (セル 0 から) 書かれていて， M の 初期ヘッド位置
が x1 # . . . #xn の 最も左に あり，初期状態が zs で あるならば，
M は停止し ない．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 計算 IV
fn
M という 記法に より，チューリング機械 M に より計算される
Nn から N への 関数を表すこ とに する．
定義 4
任意の n ∈ N+ と任意の 関数 f : Nn → N に おいて， fn
M =fと
なるよう なチューリング機械 M が存在するならば，関数 f
はチ ュー リング 計算可能 (Turing computable) で あると言う ．さ
らに ，以下の よう に 定義する．
T n = すべての n 入力の チューリング計算可能な関数の 集合.
[
T =
T n = すべての チューリング計算可能な関数の 集合.
n>1
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ュー リング 計算 V
こ こ で ，ど の よう な関数がチューリング計算可能で あるかという
自然な疑問が生ず る．そ の 答え は次の 定理に より与え られる．
定理 1
チューリング計算可能な関数の クラスは，部分帰納的関数の クラ
スと等し い．すなわち， T = P で ある．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 I
P ⊆ T を示すに は，以下を証明すれば十分で ある．
(1) 関数 Z, S, V がチューリング計算可能で ある．
(2) チューリング計算可能な関数の クラスが，第 11 回の 講義で
定義された 演算 (2.1) から (2.6) に 関し て閉じている．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 II
定数 0 関数を計算するチューリング機械は，次の よう に し て容易
に 定義でき る．M = [{∗, |}, {zs , zf }, A] とする．た だし A は以下の
よう な命令集合で ある．
zs |
→
| Lzf
zs ∗
→
∗ Nzf .
つまり，もし も入力がゼロでなけ れば，M はヘッドを 1 つ左へ動
かし て停止する．我々の チューリング機械の 定義では，M は -1 番
地の セルの ∗ を見るこ とに なり, そ の 出力は 0 となる．もし も入
力がゼロで あっ た 場合は， M は 0 番地の セルの ∗ を見ているの
で ，そ の まま書き 換え ず ，ヘッドを動かさず に 停止する．明らか
に すべての n ∈ N に 対し て f1M (x) = 0 で ある．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 III
後者関数 (successor function) S は次の よう なチューリング機械
M = {∗, |}, {zs , zf }, A] に より計算で き る．た だし A は以下の よう
な命令集合で ある．
zs |
→
| Lzs
zs ∗
→
| Nzf .
つまり，こ の 機械は入力に 1 個の | を書き 足すだけ で 停止する．
し た がっ て，すべての n ∈ N に 対し て f1M (x) = S(x) となる．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 IV
さらに ，前者関数 (predecessor function) M = {∗, |}, {zs , zf }, A]
に より計算で き る．た だし A は以下の よう な命令集合で ある．
zs |
→
∗ Rzf
zs ∗
→
∗ Nzf .
こ の チューリング機械は，0 番地の セルの | を読んで，こ れを消去
し てヘッドを 1 つ右へ動かす，あるいは ∗ を読んで ヘッドを動か
さず に 停止するか，いず れかとなる．し た がっ て，すべての
n ∈ N に 対し て f1M (x) = V(x) となる．以上で (1) の 部分に つい
ては証明で き た ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 V
次に (2) の 部分の 証明の 概略を示す．こ れは一連の 主張に より示
される．
主張 1. (架空変数の 導入)
n ∈ N+ とする．もし も τ ∈ T n かつ
ψ(x1 , . . . , xn , xn+1 ) = τ(x1 , . . . , xn ) ならば，ψ ∈ T n+1 で ある．
主張 1 が成り立つこ とは直感的に 明らかで ある．ψ を計算するた
めに 必要なの は，xn+1 を入力テープから消去し ，そ の 後，ヘッド
を初期位置に 戻し ， τ の た めの チューリングプログラムを開始す
るこ とで ある．し た がっ て， ψ ∈ T n+1 となる．詳細は省略する．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 VI
主張 2. (変数の 同一視)
n ∈ N+ とする．もし も τ ∈ T n+1 かつ
ψ(x1 , . . . , xn ) = τ(x1 , . . . , xn , xn ) ならば，ψ ∈ T n で ある．
主張 2 を証明するた めに は，最後の 変数（すなわち Xn ）をコ
ピーするチューリングプログラムがあれば良い．よっ て，最初の
テープの 内容
∗ ∗ x1 # . . . #xn ∗ ∗
を
∗ ∗ x1 # . . . #xn #xn ∗ ∗
に 書き 換え ，そ の 後，ヘッドを初期位置に 戻し ， M を， τ を計算
するた めの プログラムの 初期状態に セットする．そ し て τ の プロ
グラムを開始すればよい．し た がっ て ψ ∈ T n で ある．こ こ で も
詳細は省略する．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 VII
主張 3. (変数の 置換)
n ∈ N+ , n > 2 とし ，i ∈ {1, . . . , n} とする．
もし も τ ∈ T n かつ
ψ(x1 , . . . , xi , xi+1 , . . . , xn ) = τ(x1 , . . . , xi+1 , xi , . . . , xn ) ならば，
ψ ∈ T n で ある．
主張 3 は，主張 2 と同様に (mutatis mutandis; 必要な変更を加え
て) 示すこ とがで き る．し た がっ て，こ こ で は証明は省略する．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 VIII
主張 4. (合成)
n ∈ N および m ∈ N+ とする．さらに τ ∈ T n+1 , ψ ∈ T m とし ，
φ(x1 , . . . , xn , y1 , . . . , ym ) = τ(x1 , . . . , xn , ψ(y1 , . . . , ym )) とする．
こ の とき φ ∈ T n+m で ある．
主張 4 の 証明は少し ややこ し い．明らかなアイデアとし ては， y1
の 最初の 記号まで ヘッドを右に 移動し ， ψ を計算するチューリン
グプログラムを開始すれば良さそ う で ある．もし も
ψ(y1 , . . . , ym ) ↑ ならば，φ を計算する機械もまた ，入力
x1 , . . . , xn , y1 , . . . , ym に 対し て発散する．し かし ，もし も
ψ(y1 , . . . , ym ) ↓ ならば，我々の ゴールは，新し いテープ内容
∗ ∗ x1 # . . . #xn #ψ(y1 , . . . , ym ) ∗ ∗
を作っ て，x1 の 最初の 記号を指すよう に ヘッドを左に 戻すこ とで
ある．こ れで ， τ の チューリングプログラムを開始すれば良い．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 IX
そ こ で 我々が克服すべき 問題は， ψ(y1 , . . . , ym ) の 計算に よっ て，
xi が上書き されないこ とを保証する，という こ とで ある．
よっ て，以下の 補題が必要で ある．
補題 2 ( M+ )
すべての チューリング機械 M に 対し て，以下の よう なチューリ
ング機械 M+ が存在する．
n
(1) すべての n に 対し て fn
M = fM+ で ある．
(2) M+ は計算開始時の 初期セルの 位置よりも左に は移動し ない．
(3) すべての x1 , . . . , xn に 対し て，もし も fn
M+ (x1 , . . . , xn ) ↓ なら
ば，初期ヘッド位置と同じ場所で 計算が停止し ，計算結果よ
りも右側の テープに は ∗ し か書かれていない．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
補題 M+ の証明
補題 M+ を示すた めの アイデアは以下の 通りである．M+ は以下
の よう に 動作する．
すべての 入力を 1 セルず つ右へ移動させ る．
初期セルに 特別な記号をマークする．こ れを L と呼ぶこ とに
し よう ．
移動し た 入力の 右側に ある最初の セルに 特別な記号をマーク
する．こ れを E と呼ぶこ とに し よう ．
次に 示す 3 つの 例外を除き ， M と同様の 動作をする．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
補題 M+ の証明
もし も M+ が E とマークされた セルに 到達し た とき に は（こ
の とき の 状態を z と呼ぶこ とに する），マーク E を 1 セルだ
け 右に 移動し ，そ の 後ヘッドを 1 セル左に 戻し ，そ の セル
（元は E だっ た セル）に ∗ を書き 込む．そ し てそ の 位置（元
は E だっ た が今は ∗ に なっ た セル）から M の 状態 z で の シ
ミュレーションを続行する．
もし も M が状態 z に おいて，L と書かれた セルに 来てし まっ
た とき に は， L と E の 間に あるすべての テープの 内容（ E を
含むが L は除く ）を， 1 つず つ右へ移動させ る．L の 右隣の
セルに ∗ を書き 込み， M+ は，こ の セルで の M の シミュ
レーションを続行する．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
補題 M+ の証明
もし も M が停止し た とき に は， M+ は，すべての 計算結果
を，そ の 最初の 記号が L の セルの 位置に 来るまで ，左に 移動
させ る．さらに ，移動し た 計算結果の すぐ右側から E まで の
すべての セルに ∗ を書き 込み，そ の 後，計算結果の 最も左側
の セルに ヘッドを戻す．そ し て M+ もまた 停止する．
以上で 補題 M+ が証明された ．
補題 M+ を持っ て，主張 4 が上記の 通り示された ．
残りの 原始再帰および µ-再帰に 関する主張は，演習問題とする．
以上で P ⊆ T が示された ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 X
最後に T ⊆ P を示す必要がある．n ∈ N+ および f ∈ T n とし ， f
を計算する任意の チューリング機械を M とする．関数 t (time; 時
間) と r (result; 結果) を以下の よう に 定義する．

 1 , M が x1 , . . . , xn , に 対し て
高々y ステップ実行後に 停止するとき ;
t(x1 , . . . , xn , y) =

0 , そ れ以外の とき .
r(x1 , . . . , xn , y) =
f(x1 , . . . , xn ) ,
0,
t(x1 , . . . , xn , y) = 1 の とき ;
そ れ以外の とき .
こ れで ， t, r ∈ Prim を示すこ とがで き る．さらに ，クリーニは，
上で 定義し た t と r に 関する次の 標準形定理 (normal form
theorem) を示し た ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
証明 XI
定理 3 (Kleene)
すべての f ∈ T n , n ∈ N+ に 対し て，関数 t, r ∈ Prim が存在し ，
すべての x1 , . . . , xn ∈ Nn で 以下を満た す．
f(x1 , . . . , xn ) = r(x1 , . . . , xn , µy[t(x1 , . . . , xn , y) = 1])
(1)
こ の 定理の 証明は本講義の 範囲を越え るの で，こ こ では示さない．
t と r の 原始帰納性と，等式 (1) に よっ て，T ⊆ P が成り立つ．な
ぜならば，こ の 等式に よっ て， µ-演算を 1 回だけ 適用すれば (演
算 (2.6))，計算結果の 関数 r は演算 (2.4) に より求められるからで
ある．以上で f ∈ P が示された ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
チ ャー チ の提唱
上記の 定理は，基礎的な認識論に 関する重要性を持っ ている．
我々は全く 異なる方向から議論を始めた に も関わらず ，最終的に
同じ計算可能関数に た ど り着いた ．つまり，
「直感的に 計算可能」
な関数を形式的に 表すた めの ，異なるアプローチが提案された と
いう こ とで ある．こ れらの アプローチに は他に も，ポストの アル
ゴリズム，マルコフの アルゴリズム，ランダムアクセス機械
(Random Access machine; RAM)，チャーチの λ-計算がある．こ
れらの 形式化手法はすべて，同じ計算可能関数の 集合を定義し て
いるという こ とが，後に わかっ た ．つまり結果とし て得られる関
数の クラスは，チューリング計算可能な関数と等し い．こ の 事実
が，チャーチの 有名な提唱を導いた ．
チ ャー チ の提唱 (Church’s Thesis). 「直感的に 計算可能」 な関数
の クラスは，チューリング計算可能な関数の クラスと等し い．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 I
こ こ で 我々は，た だ 1 つの チューリング機械が存在し て，そ れに
よっ てすべての 部分帰納的関数が計算で き るこ とを示そ う ．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 I
こ こ で 我々は，た だ 1 つの チューリング機械が存在し て，そ れに
よっ てすべての 部分帰納的関数が計算で き るこ とを示そ う ．
まず ，対関数 (pairing function) を利用し た 我々の 結果を用いれ
ば，任意の n 個組の 自然数を 1 つの 自然数で 符号化で き るこ とが
容易に わかる．し かもこ の 符号化は，すで に 述べた よう に ，原始
帰納的で ある．そ こ で 以下で は， N から N への すべての 部分帰
納的関数の 集合を P と表記するこ ととする．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 I
こ こ で 我々は，た だ 1 つの チューリング機械が存在し て，そ れに
よっ てすべての 部分帰納的関数が計算で き るこ とを示そ う ．
まず ，対関数 (pairing function) を利用し た 我々の 結果を用いれ
ば，任意の n 個組の 自然数を 1 つの 自然数で 符号化で き るこ とが
容易に わかる．し かもこ の 符号化は，すで に 述べた よう に ，原始
帰納的で ある．そ こ で 以下で は， N から N への すべての 部分帰
納的関数の 集合を P と表記するこ ととする．
次に ，任意の 部分帰納的関数 ψ(i, x) を考え る．すなわち，
ψ : N2 → N で ある．こ こ で ，もし も第 1 引数 i を固定すれば，
1 変数の 部分帰納的関数 ψi が得られる．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 II
すると, ψ で 計算で き るすべての 1 変数関数は次の よう に 図示で
き る (図 3 参照)．
ψ0
ψ1
ψ2
ψ3
ψ4
ψ5
·
·
·
ψi
...
計算理論
ψ(0, 0)
ψ(1, 0)
ψ(2, 0)
ψ(3, 0)
ψ(4, 0)
ψ(5, 0)
ψ(0, 1)
ψ(1, 1)
ψ(2, 1)
ψ(3, 1)
ψ(4, 1)
...
...
...
ψ(0, 2)
ψ(1, 2)
ψ(2, 2)
ψ(3, 2)
ψ(4, 2)
ψ(0, 3)
ψ(1, 3)
ψ(2, 3)
ψ(3, 3)
ψ(4, 3)
ψ(0, 4)
ψ(1, 4)
ψ(2, 4)
ψ(3, 4)
ψ(4, 4)
...
...
...
...
...
図 3: すべての ψi を表す 2 次元配列表．
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 III
例をあげると， ψ(i, x) = ix を考え るならば，例え ば ψ7 (x) = 7x
となる．し た がっ て，すべての 関数 ψ ∈ P2 は，一種の 番号付け
(numbering) で あると言う こ とが正当化で き る．
定義 5
以下が成り立つとき ，関数 ψ ∈ P2 は， P に 対し て万能
(universal) で あると言う ．
{ψi | i ∈ N} = P .
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 III
例をあげると， ψ(i, x) = ix を考え るならば，例え ば ψ7 (x) = 7x
となる．し た がっ て，すべての 関数 ψ ∈ P2 は，一種の 番号付け
(numbering) で あると言う こ とが正当化で き る．
定義 5
以下が成り立つとき ，関数 ψ ∈ P2 は， P に 対し て万能
(universal) で あると言う ．
{ψi | i ∈ N} = P .
こ こ で 明らかに 興味深い疑問は P に 対し て万能な ψ ∈ P2 が存在
するかど う かである．もし も P に 対し て万能な ψ が存在するなら
ば， P = T で あるから， ψ もまた チューリング計算可能で ある．
し た がっ て， ψ を計算する任意の チューリング機械を万能チ ュー
リング 機械 (universal Turing machine) とし て解釈で き るこ とに
なる．次の 定理で ，万能な ψ が存在するこ とが確かとなる．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 IV
定理 4
P に 対し て万能な関数 ψ ∈ P2 が存在する．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 V
こ の アイデアは容易に 説明で き る．我々の 定理 P = T より，すべ
ての τ ∈ P に 対し て， f1M = τ となるよう なチューリング機械 M
が存在する．そ こ で ，すべての チューリング機械を自然数で 符号
化するこ とを目指そ う ．そ れに は， cod(M) ∈ N となるよう な単
射の 一般帰納的関数 cod が必要で ある．さらに ，こ の アイデアが
成立するた めに は，次の よう な一般帰納的関数 decod も必要で
ある．
decod(cod(M)) = (M の プログラム).
もし も decod への 入力 i が，チューリング機械の 正し い符号で な
い場合に は， decod(i) = 0 と定義する．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 VI
こ う し て，万能関数 ψ は， 2 つの 入力変数 i と x を持つチューリ
ング機械 U に より記述でき る．動作開始時に は，通常と同様，ま
ず decod(i) を計算する．もし も decod(i) = 0 ならば，関数 Z(定数
0) を計算する．そ う でなけ れば，decod(i) が返し た 機械 M の プロ
グラムをシミュレートする．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 VI
こ う し て，万能関数 ψ は， 2 つの 入力変数 i と x を持つチューリ
ング機械 U に より記述でき る．動作開始時に は，通常と同様，ま
ず decod(i) を計算する．もし も decod(i) = 0 ならば，関数 Z(定数
0) を計算する．そ う でなけ れば，decod(i) が返し た 機械 M の プロ
グラムをシミュレートする．
こ の 動作を実現するに は，以下の 追加条件を満た さなけ ればなら
ない．
(1) U は decod(i) に よっ て得られた プログラムを上書き し てはな
らない．
(2) U は，有限個の テープ記号と有限の 状態集合で 実現し なけ れ
ばならない．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 VII
次に ，ど の よう に し てすべての 条件が実現で き るかを手短に 述べ
る．読みやすく するた め，以下では，テープ記号を bi と書き ，状
態集合を zs , zf , . . . と始めるこ とに する．そ し て，
M = [{b1 , . . . , bm }, {zs , zf , z1 , . . . , zk }, A]
が与え られるとする．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 VIII
こ こ で 我々は，以下の よう な符号を用いる．
(0n は，ちょう ど n 個の ゼロからなる文字列を表す．)
cod(L) = 101
cod(R) = 1001
cod(N) = 10001
cod(zs ) = 104 1
cod(zf ) = 106 1
cod(z` ) = 102(`+3) 1
cod(b` ) = 10
計算理論
2(`+1)+1
for all ` ∈ {1, . . . , k} ,
1
for all ` ∈ {1, . . . , m} .
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 IX
そ し て命令集合の 符号化は，各部分の 符号を連結するこ とに よっ
て行われる．すなわち，
cod(zb → b 0 Hz 0 ) = cod(z)cod(b)cod(b 0 )cod(H)cod(z 0 ) .
例え ば， zs b1 → b2 Nz1 は次の よう に 符号化される．
104 1105 1107 110001108 1 .
こ こ で ， m 個の テープ記号と k + 2 の 状態があるの で ，全部で
m(k + 1) 種類の 命令が存在し ，ある特定の 順序づ け を仮定すると
I1 , . . . , Im(k+1) と書き 表すこ とがで き る．最終的に ， M の プログ
ラムは，そ の すべての 命令の 符号を連結するこ とに より，次の よ
う に 符号化で き る．
cod(M) = cod(I1 ) · · · cod(Im(k+1) ) .
こ の 文字列は自然数を 2 進数で 表し た もの と解釈で き る．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 X
cod が単射で あるこ とは容易に 分かる．すなわち，
もし M , M 0 ならば cod(M) , cod(M 0 ) で ある．
さらに ，もし 以上に 示し た よう な cod を使う ならば， decode が，
許容される文字列を与え られた かど う かを判定する手間が省け る．
つまり，文字列から M の プログラムを直接読み取るこ とがで
き る．
最後に ，シミュレーションがど の よう に 行われるかを述べなけ れ
ばならない．まず ，U が M の プログラムを破壊し ないこ とを保
証し なく てはならない．こ れは本質的に は，補題 M+ で述べた や
り方とほぼ同じで ある．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
万能チ ュー リング 機械 XI
後は，条件 (2) がど の よう に 実現されるかの 説明が残っ ている．
明らかに ， U はシミュレーションの 途中で ，自分自身の 状態集合
を使っ て M の 動作状態を記憶するこ とはで き ない．なぜならば，
無限個の 状態が必要に なる可能性があるからで ある，し かし ， U
は M の 動作状態を，テープに マークするこ とがで き る．
（例え ば
強調文字を使う など ）．
U が有限個の テープ記号し か使わないという こ とを保証するた め
に ，U は， M の テープアルファベットの 中の 記号 b` を直接使わ
ず に ， cod(b` ) = 102(`+1)+1 1 だけ を用いるこ とに する．こ れな
ら，シミュレーションを行う た めに ，た っ た 2 つの テープ記号し
か必要とし ない． 以下，詳細は省略する．
こ の よう に し て，チューリング機械 U は，定理 P = T を使え ば，
部分帰納的関数 ψ ∈ P2 に よっ て表現可能で ある．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
言語の受理 I
次に ，チューリング機械が言語 L を受理するという こ とが，何を
意味するかを定義する．
定義 6
もし すべての 文字列 w ∈ Σ∗ に 対し て次の 条件を満た すとき ，言
語 L ⊆ Σ∗ はチューリング機械 M で 受理され る (accepted) と言う ．
もし w が，M の 空テープに (0 番地の セルから) 書かれていて，
チューリング機械 M が w の 最も左の 記号から，状態 zs で実行開
始するとき ， M は有限ステップの 実行後に 状態 zf で 停止する．
さらに ，
(1) もし w ∈ L ならば， M が状態 zf で 見ているセルに は | が
入っ ている．こ の 場合を M(w) = | と書く こ ともある．
(2) もし w < L ならば，M が状態 zf で 見ているセルに は ∗ が
入っ ている．こ の 場合を M(w) = ∗ と書く こ ともある．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
言語の受理 II
もちろん，言語 L ⊆ Σ∗ がチューリング機械 M = [B, Z, A] に 受理
されるた めに は，常に Σ ⊆ B を仮定し なけ ればならない．
さらに ，すべての チューリング機械 M に 対し て
L(M) =df {w | w ∈ Σ∗ ∧ M(w) = |}
を定義し ， M に より受理される言語を L(M) と表す．
テキストに いく つか例があるの で 見ておく こ と．
計算理論
c
Thomas
Zeugmann
チューリング機械
チューリング計算
定理の 証明
チャーチの 提唱
万能 TM
おわり
Thank you!
計算理論
c
Thomas
Zeugmann