計算論　講義ノート 夜久竹夫 原　　　　筆 ： 大塚秋枝 　　　　　 ワープロ入力 ： 今井一昭 　　　　　　　　　　　　　　　　　　 　 大久保雅司 　　　　　　　　大ﾐ寛子 　　　　　　　　　　　　　　　 　　　　奥山敏昭 　　　　　　　　　　　　　　　 　　　　野口竜一 　　　　　　　　　　　　　　　 　　　　南　和子 　　　　　　　　　　　　　　　 　　　　ﾆ田賢一 　　　 ワープロ編集 ： 倉谷遣一 １９８６.９.２４ 【目次】 《前期》 ０．計算論‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ (　１) １．準備と用語‥‥‥‥‥‥‥‥‥‥‥‥‥ (　４) ２．計算可能性序論‥‥‥‥‥‥‥‥‥‥‥ (　５) ３．計算可能関数‥‥‥‥‥‥‥‥‥‥‥‥ (１１) ４．手続きのコード化と万能手続き‥‥‥‥ (１７) ５．関数の分類と"停止問題"‥‥‥‥‥‥‥ (２３) 　　《後期》　 ６．帰納的関数族‥‥‥‥‥‥‥‥‥‥‥‥ (２９) ７．Ｔｕｒｉｎｇ ａｕｔｏｍａｔｏｎ‥‥ (４１) ８．帰納的集合族‥‥‥‥‥‥‥‥‥‥‥‥ (４８) 練習問題‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ (５２) ０．計算論 　−広い意味− 　　　　オートマトン理論 　　　　言語理論 　　　★計算可能性の理論 　　　★計算量の理論 　　　★計算モデルの理論 　　　　プログラムの理論　 　　　　アルゴリズム　←　計算機数学と同じ意味 　ｮ｢｢ｲｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　､目的､､計算機とプログラムの基礎理論､ ｶ｢｢ｺｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　　 ､　　　　　　　　計算機数学　　　　 ､ 　 ､　　　　　　　　　　　　　　　　　　　　､　　 ､ 　　　　　　　　　　　　 ､ 　 ｮ｢｢ﾞ｢｢｢ｲ　ｮ｢｢｢｢｢｢｢｢｢ｲｮ｢｢｢ﾞ｢｢ｲ　　 ､ ､　 ､ ､ ､､ ､ 　､　　 ､ ､ 計 ､　､　 プログラムの ､､ オ ､ 　､　　 ､ ､　算 ､　､　　 　 理論 ､､ ｜　､ 　､　　 ､ ､　可 ､　､　 　 計算量 ､､ ト ､ 代 ､　　 　 ､ 基 ､　能 ､　､　 アルゴリズム ､､ マ ､ 数 ､　　 ､ 礎 ､ 性　､　､ 　　　 ､､ ト ､ 学 ､　　 ､ 論 ､ 　､ ､ 　　 ､､ ン ､ 群 ､　　 ､ ､　　　､　､　　　　　　　　　､､ ､ 　､　　 ､ ｶ｢｢｢ﾞ｢ﾞ｢｢｢｢｢｢｢｢｢ﾞﾞ｢｢｢ｺ　　､　　 ､ 　､ ､ 　　 ､､ ､ ｶ｢｢｢｢｢｢ｺ ､　プログラム技術 ､ｶ｢｢｢｢｢｢ｺ 　　　､　　　　　　 ､ ｶ｢｢｢｢｢｢｢｢｢ｺ −狭い意味− 　　　　上の★印 【注】 　ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　 　､ ､ (関数) 　､　 計算不可能 ､ 問題の全体 　､　ｮ｢｢｢｢｢｢｢｢｢｢ｲ　　　 ､ 　 ､ 　､　､ ､ 　 ､←｢｢ｺ　 　､ ､ 計算可能 ､ 　 ､ 　 　 　､ ､ ､ 計算量∞ ､ 　 　 　､ ､ ､←｢｢｢｢→ ､ 　 　 　､ ､ 　計算量理論 ､ 　 ､ 　 　 　､ ､ ×←｢｢｢｢｢→､ 　 ､ 　 　 　､ ､ ､ ､ 　 ､ 　 　 　､ ､ ｶ｢｢｢｢｢｢←､→｢｢｢｢｢｢ﾆ　　 　 　､ ､　計算量ゼロ ､ 計算可能理論 ､ 　 　 　､ ｶ｢｢｢｢｢｢｢｢｢｢ｺ　　　 ､ 　 　 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ　　　　　　 ”計算量”は距離に当たる 測り方を決めたり比較するのが ｮ｢｢｢｢｢｢ｲ ､計算モデル論､ ｶ｢｢｢｢｢｢ｺ ☆ ２つのプログラムｐとｑが等しいか ／ ０　(ｐ＝ｑ) ｆ(ｐ､ｑ)＝､　 ＼１　(ｐ≠ｑ) 前期 計算可能性 @ ☆の計算不可能性の証明 ［計算論の基本定理］ （計算機数学） A 帰納関数 後期 プログラムの理論 計算量 計算モデル 参考書 細井　勉　　　計算の基礎理論 　　　エンゲラ−　　計算の理論入門、日本コンピュ−タ協会 §１．準備と用語 自然数　：０、１、２、‥‥‥ 　　　直積集合：　２つの集合Ａ，Ｂがあるとき、Ａ，Ｂから、それぞれ任意の 　　　　　　　　要素ａ，ｂをとって作った順序対(ａ，ｂ)のすべてを要素とす 　　　　　　　　る集合、即ち、（ａ1ｂ1),(ａ1ｂ2)……(ａ2ｂ1)……(ａnｂn) のすべてを要素とする集合をＡ，Ｂの直積といい Ａ×Ｂで表す つまり、Ａ×Ｂ＝｛(ａ，ｂ)｜ａ｢Ａ，ｂ｢Ｂ｝ 不確定写像：多価関数→値を２つ以上持っている 　　　アルファベット：記号の有限集合、例えば ｛ａ1，ａ2，ａ3，…，ａn｝＝Σ ｛Ａ，Ｂ，…，Ｚ，ａ，…｝ ｗｏｒｄ：Σの元の有限列 ｗ＝ｂ1ｂ2…ｂi 　　　ｗの長さ：｜ｗ｜＝ｉ(上) 　 ｗがｎｕｌｌ ｓｔｒｉｎｇ (ｅｍｐｔｙ ｗｏｒｄ) def εと書く ←−→｜ｗ｜＝０ ｮ｢｢｢ｲ ､ 記法 ､ ｶ｢｢｢ｺ def Σ0＝＝＝｛ε｝ 　長さをもっていない集合 def Σi＝＝＝｛ｂ1，ｂ2，…，ｂi；ｂk｢Σ，１≦ｋ≦ｉ｝(ｉ≧１) def Σ*＝＝＝　Ｕ Σi 　　　　　　 i=0 Σ*の部分集合を　ｌａｎｇｕａｇｅ という。 【例】Σ＝｛０，１｝とする Σ0＝｛ε｝ Σ1＝｛０，１｝ 　　　　　 Σ2＝｛００，０１，１０，１１｝ Σ*＝｛ε，０，１，００，０１，１０，１１，０００，……｝ 【例】Σ＝｛０，１，…，９，Ａ，…，Ｚ，＋，−，…｝としたとき ＦＯＲＴＲＡＮ語は、Σ*の部分集合 §２．計算可能性序論 　はじめに 　　数論的関数 　　　ｆ：Ｎk→Ｎ 　　の計算可能性 　 ｮ｢｢｢｢｢｢｢ｲ　 ､数論的関数全体､　 　､ ､　 ､ｮ｢｢｢｢ｲ ､　 ､､計算可能､ ､　 ､ｶ｢｢｢｢ｺ ､　 ｶ｢｢｢｢｢｢｢ｺ　 　ここでは操作列型プログラミング言語（アセンブラ語，ＦＯＲＴＲＡＮに 　即した仮想プログラミングシステムを考え、その上で、計算可能性を定める。 　　操作列型プログラミング言語は、 　 　・ 関数型プログラミング言語（ＬＩＳＰ） 　 　・ 述語論理型プログラミング言語（Ｐｒｏｒｏｇ） 　 　・ オートマトン 　 　・ 帰納関数 　　と一致する。 ｮ｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､手続きＰｒｏｃｅｄｕｒｅ､　　 ｶ｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　　概要 　つぎの様なシステムを考える。 　ｮ｢｢｢｢ｲプログラム ､手続き ､　 　､ファイル､　 ｶ｢｢｢｢ｺ　 ｮ｢｢｢｢ｲメモリー ､ データ ､　データファイルは分割されていて各場所０、１、２……にはＮ ､ファイル､の元が入る。 ｶ｢｢｢｢ｺ　データファイルの”様相”はＣ：Ｎ→Ｎ ”手続き” 　”様相の変化” 　これらを手がかりとして計算可能性をもとめる。 　つぎに手続きを定める。帰納的に以下で 　　ｉ｢Ｎ　（｛０、１、２、３、４、５、６、７、８、９｝*） ｮ｢｢｢｢｢ｲ ､定義２．１､ （手続きの形式） ｶ｢｢｢｢｢ｺ （T）ｂａｓｅ　次の基本操作（代入文）は手続き 　　　 ａ. ゼロクリアー 　　　　　　　形式　　Ｓｉ：＝０； 　　　　　　　意味　　Ｓｉの値を０ 　　　　　　　　　　　ｉ番地の内容を０ 　　　　　　　　　ｮ｢｢｢ｲ ｮ｢｢｢｢ｲ ｾ｢｢｢ﾆ　　　　ｾ｢｢｢｢ﾆ Ｓ５　､１０ ､ 　→　 ､ ０ ､ Ｓ５：＝０； ｾ｢｢｢ﾆ ｾ｢｢｢｢ﾆ ､ ､ ､ ､ ､　　　､ ､　　　　､ 　　 　ｂ. 代入 　　　 形式　　Ｓｉ：＝Ｓｊ； 　　　　　　　意味　　Ｓｉの内容をＳｊの内容 ｮ｢｢｢｢ｲ ｮ｢｢｢｢ｲ Ｓ０､ １００ ､ ､ ､ ｾ｢｢｢｢ﾆＳ５：＝Ｓ０；､ ､ ､ ､　　 ､ ､ ､ ､ → ､ ､ ｾ｢｢｢｢ﾆ　 ｾ｢｢｢｢ﾆ Ｓ５､ ０　､ ､ １００､ ｾ｢｢｢｢ﾆ　 ｾ｢｢｢｢ﾆ ､　　　　､ ､　　　　､ ｃ. 後者関数　　Ｓｕｃｃｅｓｓｏｒ 　 形式　　Ｓｉ：＝ｓｕｃ（ｓｊ）； 　　　　　　　意味　　Ｓｉ：＝Ｓｊ＋１； 　　　　　　　　　ｮ｢｢｢｢ｲ ｮ｢｢｢｢ｲ ､ １００ ､ 　　　　 ､ ､ ｾ｢｢｢｢ﾆ 　　　　　　 ｾ｢｢｢｢ﾆ ､ ､　　 ､ ､ ､ ､ → ､ ､ ､ ､ ､ ､ ｾ｢｢｢｢ﾆ ｾ｢｢｢｢ﾆ ､ ０ ､ ､ １０１､ ｾ｢｢｢｢ﾆ ｾ｢｢｢｢ﾆ ､ ､ ､ ､ Ｓ５：＝ｓｕｃ（Ｓ０）； 　　 　ｄ. 前者関数　　Ｐｒｅｄｃｅｓｓｅｒ 形式　　Ｓｉ：＝ｐｒｅｄ（Ｓｊ）； 　　　　　　　意味　　Ｓｉ：＝Ｓｊ−１； 　　　　　　　ただし　ｐｒｅｄ（０）＝０ 　　　　　　　　　　　　つまり　０−１＝０ 　　（U）　ｉｎｄｕｃｔｉｏｎ 　　　　　　　　ｐ，ｑが手続き→以下の形の文は手続き 　　 ｅ　分岐文 ｉｆ　ｓｉ＝０　ｔｈｅｎ　ｐ　ｅｌｓｅ　ｑ　ｅｎｄｉｆ； ｆ 変数回繰り返し文 　　　　　　 ｆｏｒ　ｉ　ｉｎ　１．．ｐｒｅｄ ｋ（Ｓｉ） 　　　　　　　　ｌｏｏｐ　ｐ　ｅｎｄ　ｌｏｏｐ； ｇ　有界でない繰り返し文 ｗｈｉｌｅ　Ｓｉ≠０　ｌｏｏｐ　ｐ　ｅｎｄ　ｌｏｏｐ； 　　　 ｈ　連接 ｐｑ また、ｋ個のｐの連接をｐkまたは 　　　　　ｆｏｒ　ｉ　ｉｎ　１ ．．ｋ　ｌｏｏｐ　ｐ　ｅｎｄ　ｌｏｏｐ； 　 と略記することもある。 　　　　手続き全体をＰと書く。 例２．１　手続きの例 Ｐ２．１ 　　　　Ｓ１：＝ｐｒｅｄ（Ｓ１）；＼ｈ 　　　　Ｓ１：＝ｐｒｅｄ（Ｓ１）；／　　＼ｈ 　　 Ｓ０：＝Ｓ１； ／　　 (注)Ｓ０←Ｓ１−２　informal 例２．２ 　　　Ｐ２．２ 　　　　Ｓ０：＝Ｓ２； ＼ｈ 　　　　ｆｏｒ　ｉ　ｉｎ　１　．．　ｐｒｅｄ０（Ｓ１）＼ 　／ 　　　　　　ｌｏｏｐ 　 ､ｆ 　　　　　　　　Ｓ０：＝ｓｕｃ（Ｓ０）； 　　　､ 　　 ｅｎｄ　ｌｏｏｐ； 　 ／ (注)Ｓ０←Ｓ１＋Ｓ２　informal ｮ｢｢｢｢｢｢｢｢ｲ　 ､手続きによる計算､　 ｶ｢｢｢｢｢｢｢｢ｺ　 Ｐｒｏｃｅｄｕｒｅ　Ｓｅｍａｎｔｉｃｓの定義 　　計算演算子　ａｐｐｌｙ：ｃ×ｐ→ｃを導入 　　　　　　　　ａｐｐｌｙ（ｃ，ｐ）をｃ・ｐ 　　　　　　　　（ｃ・ｐ）・ｑをｃ・ｐ・ｑとかく。 　　（定義２．２） 　　　　　以下で定められる演算子ａｐｐｌｙを計算演算子という。 　　１．　基本演算子の適用　ｃ｢Ｃ　　ｉ，ｊ｢Ｎ 　　　　ａ　ｃ・（Ｓｉ：＝０；）（Ｓ） 　　　 　 ／０　　　　（Ｓ＝Ｓｉ） ＝､ 　 ＼ｃ（Ｓ）　（Ｓ≠Ｓｉ） ｂ　ｃ・（Ｓｉ：＝Ｓｊ；）（Ｓ） 　　 　　 ／ｃ（Ｓｊ）　（Ｓ＝Ｓｉ） 　＝､ 　　　 　 　　 ＼ｃ（Ｓ）　　（Ｓ≠Ｓｉ） 　　　　ｃ　ｃ・（Ｓｉ：＝ｓｕｃ（Ｓｊ） 　 　 ／ｃ（Ｓｊ）＋１　（Ｓ＝Ｓｉ） ＝､ 　　　　　　　　　 ＼ｃ（Ｓ）　　　　（Ｓ≠Ｓｉ） ｄ　ｃ・（Ｓｉ：＝ｐｒｅｄ（Ｓｊ） 　　　　　　　　　 ／ｃ（Ｓｊ）−１　（Ｓ＝Ｓｉ） ＝､ 　　　 ＼ｃ（Ｓ） 　 （Ｓ≠Ｓｉ） また、ｃ・ε＝ｃとさだめる。 　　　２．　制御文の適用 　　　　ｅ　分岐文 def ／ｃ・ｐ （ｃ（Ｓｉ）＝０） 　　　　　　ｃ・（Ｓｉ＝０）（ｐ怩早j＝＝､ 　　　　　　　　　　　　　　　　　　　　　 ＼ｃ・ｑ （ｃ（Ｓｉ）≠０） 　　 ｆ　整数回繰り返し文 def ／（ｃ・ｐ）・ｐSi-k-1　（ｃ（Ｓｉ）−ｋ≧１） 　　　　　　ｃ・ｐSiｰk　＝＝､ 　 　＼ ｃ・ε; （ｃ（Ｓｉ）−ｋ＝０） 　　　　ｇ　有回でないくり返し文 def ／ｃ・ｐ・ｐ*(Si≠0) （ｃ（Ｓｉ）≠０） 　　　　　　ｃ・ｐ*(Si≠0)＝＝､ 　　　　　　　　　　　　　　　 ＼ｃ・ε; （ｃ（Ｓｉ）＝０） 　　　　ｈ　連接 def 　　　　　　　ｃ・ｐｑ＝（ｃ・ｐ）・ｑ ↑　　　　 ↑ 連接　　　連接の消去 §３．計算可能関数　 　 　　　計算可能性を定義する。 ｮ｢｢｢｢｢ｲ 　､定義３.１ ､ ｶ｢｢｢｢｢ｺ 　　　 　　　関数ｆ（ｘ1，ｘ2，………，ｘn）＝ｙが手続きＰにより計算される。 ↑ ｜ｄｅｆ 　　　 ↓ 様相Ｃ＝　　　　 ､　　　　 　｢｢｢｢ﾞ｢｢｢｢ Ｓ０ ､　０　　 　　　　　　　　　Ｓ１　､　ｘ1 　 　　　　　　　　　：　　､　：　　 　　　　　　　　　Ｓｎ　､　ｘn　　 　　　　　　　　Ｓｎ＋１､　０　　 　　　　　　　　　：　　､　：　　 　　　　　　　　　　　　､　　　　 　 　　に対して 　 Ｃ o Ｐ＝ 　　 ､　　　　　 ｢｢｢｢ﾞ｢｢｢｢｢ Ｓ０ ､　ｙ　　　 Ｓ１　､何でもよい ：　　､ 　　　　 　､　　　　　 　 （準備） 　@　Ｐ（ｘ1，……，ｘn）＝ｙ ↑　　　　　　　 ｜　記法　　　　 ↓　　　　　　　 Ｃ o Ｐ（Ｓ０）＝ｙ ただし ､ Ｃ o Ｐ ､ Ｃ＝ ｢｢｢｢ﾞ｢｢｢｢　 ｢｢｢｢ﾞ｢｢｢｢　 Ｓ０ ､ ０ Ｓ０ ､ ｙ Ｓ１ ､ ｘ1 −→……−→ ： ､ ： Ｓ２ ､ ｘ2 Ｐ ､ ： ､ ： ､ Ｓｎ ､ ｘn ： ､ ： ､ def 　A　Ｐ（ｃ）＝＝＝ Ｃ o Ｐ ｮ｢｢｢｢｢ｲ 　､定義３.２ ､ ｶ｢｢｢｢｢ｺ 　　　関数ｆが全域計算可能　　totally computable def ←−→　　１.　ｆが全域的 ２. ｆを計算する手続きＰが存在 ｮ｢｢｢｢｢ｲ 　､定義３.３ ､ ｶ｢｢｢｢｢ｺ 　　　関数ｆが部分計算可能　　（準計算可能） 　　　　def 　 　←−→　次のような手続きＰが存在 　　　　　　　ｆ（ｘ1，……，ｘn）＝ｙ　←→Ｐ（ｘ1，……，ｘn）＝ｙ ｆ（ｘ1，……，ｘn）が定義されない 　　　　　　　　　　　　　 ←→　Ｐ（ｘ1，……，ｘn）が定義されない （停止しない） 　【例３.１】 　　問　Ｃ＝　　　　､　　　　 ｢｢｢｢ﾞ｢｢｢｢ Ｓ０　､　０　　 　　　　　　　Ｓ１　､　５　　 　　　　　　　Ｓ２　､　０　　 　　　　　　　：　　､　：　　 　　　　　　　　　　､ 　　　とする。　このとき　　Ｃ o Ｐ２.１を求めよ。 　　　　ただし、Ｐ２.１は、例２.１の手続き。　　 　　解　T.制御文（連接）を消去 〔・連接〕 　　　　＜注＞　ｃo(S1:=pred(S1);・S1:=pred(S1);・S0:=S1;) 　　　　　　　=(ｃo S1:=pred(S1))o(S1:=pred(S1);・S0:=S1;)　Def2.2h 　　　　　　　　　ｶ｢｢｢｢｢｢｢ｺ 　　　　 　 Ｃ1 　　　　　　　=((ｃo S1:=pred(S1))o(S1:=pred(S1))o S0:=S1;　…(2) 　　　　　　　　　 ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ､ Def2.2h 　　　 Ｃ2　　　　　　　　　　 ､ 　　　　　　 　ｶ｢｢｢｢｢｢｢｢｢｢｢ｺ 　 　　 Ｃ3 　　　 　　　　　　　　　　　　（３行目は連接になっていない） 　　　U.計算 　　　　　　Ｃ　　､　　　　　　　　　　　　　Ｃ1　 ､　　　　 ｢｢｢｢ﾞ｢｢｢｢ S1:=pred(S1)　｢｢｢｢ﾞ｢｢｢｢ 　　　　　　Ｓ０　､　０ ｢｢｢｢｢→ Ｓ０　､ ０　　 Ｓ１　､　５　　　Def2.2d 　　　　Ｓ１　､ ４　　 ､ ､　　　　 　　　　　　　　　　　　　　　　　　　　　　　Ｃ2 　､　　　　 S1:=pred(S1) ｢｢｢｢ﾞ｢｢｢｢ ｢｢｢｢｢→ Ｓ０　､　０　　 Def2.2d Ｓ１　､　３　　 　　　､　　　　 ､　　　　 　　　　　　　　　　　　S0:=S1　　　　｢｢｢｢ﾞ｢｢｢｢ 　 ｢｢｢｢｢→ Ｓ０　､　３　　 　　　　　　　　　　　　　　　Def2.2b　　　 Ｓ１ ､　３　　 　　　V (2)=ｃ2 o S0:=S1; Ｃ3＝　　　　 　､ 　　　　 Def2.2b 　 　｢｢｢｢ﾞ｢｢｢｢ 　　　 （＝Ｃ3とおく） Ｓ０ ､　３ 　 Ｓ１ ､　３ 　 　　　　　　　　　　　 Ｓ２ ､　０ 　 　 ：　 ､ ： 　 　､ 　　　 ∴　上のＣ3が解。 　例３.２ 　　問　Ｃ＝　　　　､　　　　 ｢｢｢｢ﾞ｢｢｢｢ 　　　　　　　Ｓ０　､　０　　 　　　　　　　Ｓ１　､　５　　 　　　　　　　Ｓ２　､　３　　 　　　　　　　　　　､ とする。このとき　Ｃ o Ｐ２.２を求めよ。 　　　　ただし、Ｐ２.２は、例２.２の手続き 　解　T. 　　　　 　 ｃo(S0:=S2;･for i in 1..pred0(S1) loop S0 := suc(S0) end loop;) 　=(ｃo S0:=S2;)o for i in 1..pred0(S1) loop S0 := suc(S0) end loop;　…(1) ここで 　､ 　　　 ｃo S0:=S2; ＝ 　｢｢｢｢ﾞ｢｢｢｢ 　＝　Ｃ1とおく 　 Ｓ０　､ ３　　 　　　　 Ｓ１　､ ５　　 Ｓ２　､ ３　　 　､ 　　　 　　　U　(1)=ｃ1o for i in 1..pred0(S1) 　　　　 loop S0:=suc(S0) end loop; =(ｃ1o S0:=suc(S0);)o for i in 1..pred1(S1) 　　　 　　 loop S0:=suc(S0) end loop; …(2) Def2.2fより 　　　　　　　 ここで ､　　　　 　　　　　　 ｃ1o S0:=suc(S0);　＝ ｢｢｢｢ﾞ｢｢｢｢　＝　Ｃ2 　　　　　　　　　　　　　 　 Ｓ０ ､ ４　　 　　　　　　　　　　　　　　　　　　　　Ｓ１　､　５　　 　　　　　　　　　　　　　　　　　　　　Ｓ２　､ ３　　 　　　　　　　　　　　　　　　　　　　　　　　､　　　　 　　　V　(2)=ｃ2o for i in 1..pred1(S1) 　　　 　loop S0:=suc(S0) end loop; 　 =(ｃ2o S0:=suc(S0);)o for i in 1..pred2(S1) 　　　loop S0:=suc(S0) end loop; …(3) 　 　　　　　Def2.2fより 　　 ここで ､ 　　　　　　 ｃ2o S0:=suc(S0);　＝　｢｢｢｢ﾞ｢｢｢｢ ＝ Ｃ3 Ｓ０ ､ ５ Ｓ１ ､ ５ Ｓ２ ､ ３ ､ 　　　W (3)=ｃ3o for i in 1..pred2(S1) 　 　　　loop S0:=suc(S0) end loop; 　　　　　　 =(ｃ3o S0:=suc(S0);)o for i in 1..pred3(S1) 　　　 loop S0:=suc(S0) end loop; …(4) 　　　　　　Def2.2fより 　　　　　 　　ここで　 ､ 　　　 　　　ｃ3o S0:=suc(S0); ＝ ｢｢｢｢ﾞ｢｢｢｢ ＝　Ｃ4 Ｓ０ ､ ６ Ｓ１ ､ ５ Ｓ２ ､ ３ ､ 　 X　(4)=ｃ4o for i in 1..pred3(S1) 　　　　loop S0:=suc(S0) end loop; =(ｃ4o S0:=suc(S0);)o for i in 1..pred4(S1) loop S0:=suc(S0) end loop; …(5) Def2.2fより 　　 ここで ､ 　　　　　　 ｃ4o S0:=suc(S0); ＝　｢｢｢｢ﾞ｢｢｢｢ ＝　Ｃ5 Ｓ０ ､ ７ Ｓ１ ､ ５ Ｓ２ ､ ３ ､ 　　　Y　(5)=ｃ5o for i in 1..pred4(S1) 　　　　loop S0:=suc(S0) end loop; =(ｃ5o S0:=suc(S0);)o for i in 1..pred5(S1) loop S0:=suc(S0) end loop; …(6) Def2.2fより 　　 ここで ､ 　　　　　　 ｃ5o S0:=suc(S0);　｢｢｢｢ﾞ｢｢｢｢ ＝　Ｃ6 Ｓ０ ､ ８ Ｓ１ ､ ５ Ｓ２ ､ ３ ､ 　　Z　(6)=ｃ6o for i in 1..pred5(S1) 　　　　 loop S0:=suc(S0) end loop; 　　　　　　=ｃ6o ε =ｃ6　 　ｮ｢定理３.１ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　　　 　､ ､ 　､ 関数ｆ：Ｎ → Ｎ と ｇ：Ｎ → Ｎ が計算可能 ､ 　､ ､ 　､　　　　−→ ｈ＝ｆ o ｇ　は計算可能 ､ 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　　【証明】 　　　ｆ，ｇを計算する手続きを、ｐ，ｑとする。 　　　ｒとして、ｐのあとで、Ｓ０の値を″入力″してｑを行う手続きを考える。 　 このとき、ｒはｈを計算する。 §４．手続きのコード化と万能手続き 　　　コード化：　｛手続き｝←→　Ｎ　　（１対１の対応がある。） 　　　万能手続き：　コンパイラ 　 汎用コンピュータ ｮ｢｢｢｢｢｢｢｢ｲ 　､手続きのコード化､ ｶ｢｢｢｢｢｢｢｢ｺ 　″Ｇodel numbering ″ Ｎ ←｢｢｢｢｢｢｢｢｢｢｢ 手続き 　　　　　写像　prime :　Ｎ｢→Ｎ を次のように定める。 def 　　　　　　　　prime(n)= m ←｢→ m は n 番目の素数 　　　　　　　　　　　　　　　　　　　ただし、prime(0)=1 prime(1)=2 　ｮ｢｢ｲ 　､定義､ 　ｶ｢｢ｺ 　　 　　ゲーデル数　Ｇodel number は、以下で定められる写像 　　　　　　ｇn : 手続き全体 −→ Ｎ 　　　　　である。ｇn(p)=n のとき、ｎはｐのゲーデル数であるという。 　　　T．ｐが基本手続きの場合 　　　　　ａ. ｐ＝ "Ｓi := ０ ;"→ ｇn（ｐ）＝ ２prime(i) 　　　　　ｂ. ｐ＝ "Ｓi := Ｓj ;"→ ｇn（ｐ）＝ ３2^prime(i)*3^prime(j) 　　　 ｃ. ｐ＝ "Ｓi := Ｓuc（Ｓj）;" 　　　　　　　　　　　　→ｇn（ｐ）＝ ５2^prime(i)*3^prime(j) 　　　　　ｄ. ｐ＝ "Ｓi := ｐred（Ｓj）;" 　　　　　　　　　　　　→ｇn（ｐ）＝ ７2^prime(i)*3^prime(j) 　　　U．ｐが制御文の場合 　　　　　ｅ. ｐ＝ "if Ｓi＝０ then ｒ else ｓ end if ;" 　　　　　　　　　　　　→ｇn（ｐ）＝ １１2^prime(i)*3^gn(r)*5^gn(s) 　　　　　ｆ. ｐ＝ "for ｉ in １..pred ｋ （Ｓi）loop ｑ end loop ;" 　　　　　　　　　　　　→ｇn（ｐ）＝ １３2^prime(i)*3^prime(k)*5^gn(q) 　　　　　ｇ. ｐ＝ "while Ｓi≠０ loop ｑ end loop ;" 　　　　　　　　　　　　→ｇn（ｐ）＝１７2^prime(i)*3^gn(q) 　　　　　ｈ. ｐ＝Ｐ1 Ｐ2 ｫ Ｐn 　（ｎ≧２） 　　　　　　　　→ｇn（ｐ）＝２gn(p1)×３gn(p2)×ｫ×ｐrime（ｎ）gn(pn) 　　　　　ここで、各ｐiは基本手続き、分岐、変数回繰り返し、有界でない 　　　　繰り返しのいずれかとする。 ｮ｢｢｢｢｢｢｢ｲ ､ ｇn の求め方 ､ ｶ｢｢｢｢｢｢｢ｺ 　 　　　（例）　ｐ＝　Ｓ0 :=０； 　　 for ｉ in １..Ｓ1 loop 　　 Ｓ0 := Ｓuc（Ｓo） end loop ； 　　　　　　　とする。このとき、ｇn（ｐ）を求めよ。 　　　（解）ｇn（ｐ）＝２gn(S0:=0 ;) 　 　×３gn(for i in 1..pred 0 (S1) loop S0:=Suc(S0) 　　　　　　 end loop ;) ＝２2^1×３13^(2^2･3^1･5^(5^(2^1･3^1))) 　　　　　　　注　for i in 1..S1 は、for i in 1..pred0(S1) を表す。 　　　（T）ｐ2.1のゲーデル数は？ 　　　　 ｇn（ｐ）＝２gn(S1:=pred(S1);)×３gn(S1:=pred(S1);) 　　　　　　　　　　　　　　　　　　　　　　　　　　 ×５gn(S0:=S1;) 　　＝２7^(2^2*3^2)×３7^(2^2*3^2)×５3^(2^1*3^2) （U）ｐ2.2のゲーデル数は？ 　　　　　　ｇn（ｐ）＝２gn(S0:=S2;)×３gn(for i in 1..pred 0 (S1) 　　 loop S0:=Suc(S0) end loop ;) 　　　　　　　　　 　＝２3^(2^1*3^3)×３13^(2^2*3^2*5^gn(S0:=suc(S0);)) 　 ＝２3^(2^1*3^3)×３13^(2^2*3^1*5^(2^1*3^1) 　ｮ｢定理４.１ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　　　 　､ ､ 　 　､ 手続きの全体ＰからＮの中への１対１写像が存在する。 ､ 　 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ　　　 【証明】 　　　　 上のｇnを考えればよい。 　ｮ｢定理４.２ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　　　　 　､ 　　　　　　　　　　　　　　　　　　､　　　　 　､　　次の手続きＰが存在する。 ､ 　　 　､　　ｎ｢Ｎに対して、 ､ 　　 　､ 　　　　　０(ｎをゲーデル数として持つ手続きが存在しな､ 　　 　､　　　Ｐ(ｎ)＝ 　 い)､ 　　 　､ １（その他） ､ 　　 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ　　　　 ｮ｢｢ｲ 　､定義､ ｶ｢｢ｺ 　　　様相のゲーデル数 　　　　　様相Ｃ： ､ ｢｢｢｢｢｢ﾞ｢｢｢｢｢｢ Ｓ0 ､ Ｙ0 Ｓ1 ､ Ｙ1 ． ､ ． ． ､ ． ､ Ｓn ､ Ｙn Ｓn+1 ､ ０ ． ､ ． ． ､ ． ､ を考える。このとき 　　　　　ｇn（Ｃ）＝ ２prime(y0)×３prime(y1)× 　　　　　　　　　　　　　　　　　　ｫ×prime（ｎ＋１）prime(yn) 　　　　　　ただし　Ｃ（Ｓx）＝０　（　ｘ＞ｎ）とする。　 　ｮ｢定理４．３｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　　　　 　､ ､ 　 　､ 様相の全体ＣからＮの中への１対１対応が存在する。 ､ 　 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ　　　　 ｮ｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　､手続きの枚挙と万能手続き､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢ｺ 次の写像を考える 　　　　ｇninv：Ｎ−−→手続きの全体 　　　　ただし ／Ｐ （ｇn（ｐ）＝ｎのとき） 　　　　ｇninv（ｎ）＝｜ ＼ε （ｇn（ｐ）＝ｎとなるｐが存在しない。） 　　　ｇninv　を逆ゲーデルコードという。 　　　ゲーデル数の小さい順に手続きを並べたものを 　　　　　　　（Ｐ1，Ｐ2，Ｐ3，‥‥） 　　　　とすると、 　　　 ｛Ｐ1，Ｐ2，‥‥‥‥｝＝手続き全体 　　　である。 　　　Ｐ1，Ｐ2，‥‥を手続きの枚挙という。（enumration 数え上げ） ｮ｢｢ｲ ､定義､ ｶ｢｢ｺ 　　　次の手続きＵを "１変数の万能手続き(universal procedure)" という： def 　　　　　　Ｕ（ｎ,ｘ）＝Ｙ　←｢→　Ｐn（ｘ）＝Ｙ　 　ｮ｢定理４.４ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　　　 　､ ､ 　 　､　　１変数の万能手続きは存在する。 ､ 　 　､ ｍ変数万能手続きについても同様。 ､ 　 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ　　　 【証明】 　　　　Ｕ（ｎ，ｘ）はつぎの形 　　　　　 Ｐn（ｘ）をシミュレートすればよい。即ち、 　　　　　　　Ｃ0　　　 ､ 　　　　　　　Ｃ　　　 ､　 　　　　　　　 ｢｢｢｢ﾞ｢｢｢｢　 ｢｢｢｢ﾞ｢｢｢｢｢｢　 Ｓ0 ､ Ｓ0 ､ Ｐn（ｘ） Ｓ１ ､ ｘ −−→ Ｓ1 ､　 ． ､ ． ､　 ． ､ ． ､　 ． ､ ､　 をシミュレートする。 　　　　Ｕは全体として以下のように動けば良い。 ､ ､ 　　　　　　 ｢｢｢｢ﾞ｢｢｢｢ ｢｢｢｢ﾞ｢｢｢｢｢｢ Ｓ0 ､ Ｓ0 ､ Ｓ1 ､ ｎ Ｓ1 ､ ｎ Ｓ2 ､ ｘ 　−−→ Ｓ2 ､ ､ Ｓ3　､ ｇn（ｐn） ､　 Ｓ4 ､ ｇn（Ｃ0） ､ ､ ､ ｢｢｢｢ﾞ｢｢｢｢｢｢ Ｓ0 ､ Ｓ1 ､ ｎ −−→ Ｓ2 ､ Ｓ3 ､ ｇn（ｐn） Ｓ4 ､ ｇn（Ｃ） ､ ､ ､ ､ ｢｢｢｢ﾞ｢｢｢｢｢｢ Ｓ0 ､ ｐn（ｘ） −−→ ､ ､ ､ ､ §６．関数の分類と“停止問題” ｮ｢｢｢｢｢｢｢ｲ 　　　停止問題：､計算可能でない､関数の例 ｶ｢｢｢｢｢｢｢ｺ 　【準備】 ｮ｢｢｢｢｢｢｢ｲ ､停止性識別写像､ｈ：｛手続きコード｝×｛データ｝→｛０，１｝ ｶ｢｢｢｢｢｢｢ｺ ↑ ↑ ゲーデル数 Ｎ（数値） 　　　　　　　　　　　　　　　　　　　／０（ｇn（ｐ）＝ｎがｄの上で 　　　　　defined　by　ｈ（ｎ，ｄ）＝｜ 　　 停止しない） 　　　　　　　　　　　　　　　　　　　＼１（その他） ｮ｢ｲ ､ｐ､ ｶ｢ｺ→ｮ｢ｲ ､ｈ､→０，１ ｎ →ｶ｢ｺ 　ｮ｢定理６.１ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ ､ 　　　　　　　　　　　　　　 ､ 　､　　上のｈは計算可能でない。ｈは部分計算可能である。 ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ↑ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　､手続きの停止問題の非可解性定理､　 ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ‖ 同値 ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　､Ｔｕｒｉｎｇ　Ｍａｃｈｉｎｅの停止問題の非可解性定理､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ‖ 同値 ｮ｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　､ゲーデルの不完全性定理 ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　 ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ※ ､計算機数学と（理論）計算機数学の基本定理､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　 【証明】 　　　　（対角線論法による） 　　　　ｈを計算する手続きＨが存在すると仮定、ｐを任意の手続きとする。 　　　　仮定より、 　　　 　Ｈ*：Ｎ→｛０，１｝が存在： 　　　　　　　 　　　　　　Ｈ*（ｇn（ｐ））＝Ｈ（ｇn（ｐ），ｇn（ｐ）） 　　　　即ち、 　　　　　　　　　　　　　　　　 ／０：ｐ（ｇn（ｐ））が停止しない。 　　　　　　　Ｈ*（ｇn（ｐ））＝｜ 　　　　　　　　　　　　　　　　 ＼１：ｐ（ｇn（ｐ））が停止する。 　　　　更に、次の 　　　　　　Ｈ**：Ｎ→｛０｝がＨ*から構成できる： 　　　　　　　　　　　　　　　 ／０2'：ｐ（ｇn（ｐ））が停止しない1'　 　　　　　　Ｈ**（ｇn（ｐ））＝｜ 　　　 　　 ＼undefined（停止しない）2： 　　　　　　　　　　　　　　　　　　　ｐ（ｇn（ｐ））が停止する1 　　　　　　Ｈ**：　Ｈ*を１行づつ真似しながら、但し、Ｈ*が１を出力して 　　　　　　　　　停止するところではＨ**は止まらない。→∞ループ 　　　　ｐとしてＨ**を考えると： 　　　　　Ｈ**（ｇn（Ｈ**））が停止1←→Ｈ**（ｇnＨ**）が停止しない2 　　　　　Ｈ**（ｇn（Ｈ**））が停止しない1'←→Ｈ**（ｇnＨ**）が停止1' 　　　　∴矛盾 　　補足） 　　　　　　ｎ，ｄ　　　　　ｎ　　　　　　　ｎ 　　　　　　　｜ ｜ ｜ 　　　　　　　｜ ｜ ｜ 　　　ｈ――→｜Ｈ――――→｜Ｈ*――――→ ｜Ｈ** 　　　　　　 ｜ ｜ ｜ 　　　　　　　↓ ↓ ↓ 　　　　　Ｈ（ｎ，ｄ）　Ｈ（ｎ，ｎ）　　／０：ｐ（ｇn（ｐ））が 　　　　　　　　　　　　　　　　　　　 ｜　　　　　　ｈａｌｔしない 　　　　　　　　　　　　　　　　　　　　＼undefined：その他 　【系】 　　　　ｐを任意の手続きとする。このとき、次の計算可能な手続きＥは存在 　　　しない。 　　　　　　　　　　 　／ｐのゲーデル数 　　　　　　　　 ／入力､ 　　　　　　　　､ ＼ｘ 　　　　　　　Ｅ､ 　　　　　　　　､　　 ／０：（ｐ（ｘ）≠ｘ＋１） 　　　　　　　　 ＼出力､ 　　　　　　　　　　　 ＼１：（ｐ（ｘ）＝ｘ＋１） 　　　　※手続きｐが関数ｆを計算するか。 　　　　※プログラムの正当性判定、検証、ｖｅｒｉｆｉｃａｔｉｏｎ 〔証明〕 　　　　ｐとして次の手続きを考える。 　　　　 　／Ｑ　　　　　　　　　　　　　　Ｑ：任意の手続き 　　　　　､　ｘ０←０　　　　　　　　　　ｘ１，…，ｘｎ：Ｑにあらわ 　　　　　､　ｘ１←０　　　　　　　　　　　　　　　　　　れる全ての 　　　　　､　　　：　　　　　　　　　　　　　　　　　　　変数 　　　 ､　ｘｎ←０ 　　　　　､ 　　　　　､　ｘ１←ｘ 　　　　　 ＼ ｘ２←ｓｕｃ（ｘ１） 　　 このとき、次が成り立つ。　ｘ１＋１＝ｘ＋１ 　　　 ｐが停止 ←→ ｐ（ｘ）＝ｘ＋１ 　　　　　 ↑ 　　　　 　↓ 　　　　Ｑ（ｘ）が停止 　　　Ｑは任意なので、停止問題の非可解性よりＥは存在しない。 　【問】ｆを計算可能な関数とし、ｐを任意の手続きとする。 　　　　次の計算可能な手続きＥ1は存在するか。 　　　　　　　　　　　　 　／ｐのゲーデル数 　　　　　　　 　　／入力 ､ 　　　　　　　 　 ､ 　　 ＼ｘ Ｅ1､ 　　　　　　　 　 ､　　　 ／０：ｐ（ｘ）≠ｆ（ｘ） 　　　　　　　 　 ＼出力 ､ 　　　　　　　 　　　　　 ＼１：ｐ（ｘ）＝ｆ（ｘ） 　　　解）ｆ（ｘ）＝ｘ＋１を考えれば良い。 　　　　　“系”よりＥ1は存在しない。 　ｮ｢定理６.２ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ 　､　　ＰとＱを任意の手続きとする。次の、Ｅ2は存在しない。 ､ ､ ､ 　､　　　　　　　　　　　／Ｐ，Ｑのゲーデル数 ､ 　､　　　　　　　／入力 ､ ､ 　､　　　　　　 ､ 　 　 ＼ｘ ､ ､ Ｅ2 ､ ､ 　､　　　　　　 ､ 　　　／０：Ｐ（ｘ）≠Ｑ（ｘ） ､ 　､　　　　　　 ＼出力 ､ ､ 　､　　　　　　　　　 　＼１：Ｐ（ｘ）＝Ｑ（ｘ） ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　【証明】 　　　Ｐ（ｘ）＝ｘ＋１となる手続きＰを考える。 　　　　　Ｅ2：存在 → Ｅ：存在 　　　∴矛盾 ｮ｢定理６.３ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ 　､　　ｆ：計算可能　ｐ：任意の手続き ､ 　､　　次のＥ3は存在しない。 ､ ､ ､ 　､　　　　　　／入力　ｐのゲーデル数 ､ 　､　　　 　　､ ､ ､ Ｅ3 ､ 　 ／０（ｐ≠ｆ）： ｘ；ｐ（ｘ）≠ｆ（ｘ）､ 　､　　　　　 ＼出力､ ､ 　､　　　　　　　　　 ＼１（ｐ＝ｆ）： ｘ；ｐ（ｘ）＝ｆ（ｘ）､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　【証明】 　　　Ｅ3：存在 → Ｅ1：存在　　　∴矛盾 ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　､関数ｆ、手続きｐ　　ｐ＝ｆかどうかは“決定不能”､　　　　　 　　　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ｮ｢定理６.４ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ 　､　　Ｐ，Ｑ：任意の手続き ､ 　､　　次のＥ4は存在しない。 ､ ､ ､ 　､　　　　　　／入力　Ｐ，Ｑのゲーデル数 ､ 　､　　　 　　､ ､ ､ Ｅ4 ､ ／０（Ｐ≠Ｑ）： ｘ；Ｐ（ｘ）≠Ｑ（ｘ）､ 　､　　　　　 ＼出力､ ､ 　､　　　　　　　　　 ＼１（Ｐ＝Ｑ）： ｘ；Ｐ（ｘ）＝Ｑ（ｘ）､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　【証明】 　　　Ｅ4：存在 → Ｅ2：存在　　　∴矛盾 ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　､Ｐ，Ｑ：手続き　　Ｐ＝Ｑかどうかは“決定不能”､　 ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 【前期】 《数値関数全体》 ｮ｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　　 　　　　　　　　　　 ､ｮ｢｢｢｢｢｢｢｢｢｢ｲ､ 　ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､､ (プログラムで) ､､ｮ｢ﾞﾎ｢ｎR〜SORTING D時間､ ､､　計算可能関数全体 ､､､　､ｶ｢２n〜ﾊﾐﾙﾄ=ｱﾝﾊﾟｽ ､ 計､､ ､､､ ､ ､ 算､､ｮ｢｢｢｢｢｢｢｢ｲ､､､ｮﾞ｢２2･･･2n ,２2･･･2 ｝ｎ ､ 可､､､"実際に"計算可能､､､､､､　､　 ､　 ｎ:データ数､ 能､､､ ×｢ﾞﾞﾞｺ､ｶ｢ﾞ｢｢ﾞ｢｢｢｢｢｢｢｢｢｢ｺ 性､､ｶ｢｢｢｢｢｢｢｢ｺ､､ ､　　ｶ｢｢ﾖ｢｢二人ゲーム　　　　 ､､　　　　　　　×｢｢ﾞﾞ｢ｺｮ｢｢プログラムの停止問題 ､ｾ｢｢｢｢｢｢｢｢｢｢ﾆ､　 ､ 　 ､､　　　　　　　　　　､､ ､ｮ｢プログラムの等価性判定問題 ｮ｢ﾞﾆ ×｢｢ﾞﾞ｢｢ｺ､　その他 "多数" ↓　､､ ×｢｢ﾞﾞ｢｢｢ｺ 一致ｶﾞ｢｢｢｢｢｢｢｢｢｢ﾞｺ 　　　 　　　､プログラムによる定義､ ｮ｢自然数の上の四則演算を基礎とする ､ ､ ､ 　 ｮﾞ｢｢｢｢｢｢｢｢｢｢ﾞｲ@､ ､ｾ｢｢｢｢｢｢｢｢｢｢ﾆ､　､ ｮ｢一筆書き可能なグラフ全体 ､､　　帰納関数全体　　ｾﾞ｢ｺ* ､ ､ｾ｢｢｢｢｢｢｢｢｢｢ﾆ､ ､ｮ｢｢ﾞ｢｢｢｢｢｢｢｢｢ｲB　 ｶﾞ｢｢｢｢｢｢｢｢｢｢ﾞｺ ､､ｮ｢ﾞ｢｢｢｢｢｢｢｢ｲ､ ､ 算術演算による定義 ､ ､､､　､　　　 ／時間 ､､ ､ ､ ､､､ ､ ｮ､ ､､ ､ ､ ､､､ ､ ､ ＼メモリ ､､ ､ ､ ､､､　× ､　　(空間)､､ 　ｮﾞ｢｢｢｢｢｢｢｢｢｢ﾞｲA､､､ ､ 　　 ､､ ､､ ､､ ､､､ C計算量理論､､ 　､ｾ｢｢｢｢｢｢｢｢｢｢ﾆ､ ､､､ ×←｢｢｢→､､ ､､ ､､ ､､ ､､ 　､､ Ｔｕｒｉｎｇ ､､ →､､ 　　　　 ､､ 　､､ オートマトンによる､､ ､､､ 識別可能(計算可能)､､ 　､､　計算可能関数全体 ､､　､､､な集合全体 　　　　 ､､ ､､ ×←｢｢｢→､､ ､､ｶ｢｢｢｢｢｢｢｢｢｢ｺ､ ､､ C計算量理論､､ ､､ ､ ､､ ､､ ､ｶ｢｢｢｢｢｢｢｢｢｢｢｢ｺ ､､ ､､ ､　 　､､　　　　　　　　　　､､ ､　　　　　　　　　　 　､ｶ｢｢｢｢｢｢｢｢｢｢ｺ､　､　　　　　　　　／プログラム 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢ｺ　､　　　　 ､ 　　 オートマトンによる定義 　､　 　　 ､ 帰納関数 　 ､ ､ 　　　　 ､ ＼オートマトン ７．帰納的関数族 　７．１　原始帰納的関数　（primitive vecursive functions） ｮ｢｢ｲ 　､定義､ ｶ｢｢ｺ 　　　次の形の関数を基本関数（basic functions）という 　　　　（１）ｓｕｃ（ｘ）＝ｘ＋１ 　　　　（２）ｎｉｌ（ｘ）＝０ 　　　　（３）從i（ｘ1,ｘ2,･･･,ｘn）＝ｘi ｘ，ｎ，ｉ，ｘ1，･･･，ｘn ｢Ν 　　　以下の演算子ＣＯＭＰを合成演算子という 　　　　　　／ｈ1,･･･,ｈr ：ｎ変数関数 　　 ､ 　　　　　〉原始帰納的関数 　　　　　　＼ｇ　　　　　：ｒ変数関数 　　　　ＣＯＭＰ（ｇ,ｈ1,･･･,ｈr）＝ｆ 　　 　　　　def 　　　　＜＝＝＞ｆ（ｘ1,･･･,ｘn） 　　　　　　　　　　　　　　　　　　 ｒ変数 　 　　　　　 ｮ｢｢｢｢｢｢｢｢｢ﾖ｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　　　 　　　＝ｇ（ｈ1（ｘ1,･･･,ｘn），・・・，ｈr（ｘ1,･･･,ｘn）） 　　　　　ｶ｢ﾎ｢ｺ 　 ｶ｢ﾎ｢ｺ 　　　　 ｎ変数 ｎ変数 　　［例］ＣＯＭＰ（ｇ,ｈ）＝ｇ o ｈ ｆ ｮ｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ｮ｢｢ｲ　 ､ ､ ､ｈ1 ､　 ､ ､ ｮ｢ｲ ← ｶ｢｢ｺ←｢ﾞ｢ｮ｢｢｢｢｢｢ｲ　　 ←｢ﾞ｢､ｇ､ ： ､ ､ｘ1，…，ｘn､ 　 ､ ｶ｢ｺ ← ｮ｢｢ｲ←｢ﾞ｢ｶ｢｢｢｢｢｢ｺ　　 ､ ､ｈr ､　 ､ ､　　　　　　ｶ｢｢ｺ　　､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　　原始帰納法演算子 　　　　ＰＲＥＣ（ｇ，ｈ）→ｆ 　　　　　　／ｇ：ｎ　　変数関数 　　　　　 ､ ｈ：ｎ＋２ 〃 　　　　　基底（basis induction） 　　　　　　＼ｆ：ｎ＋１　〃　　　　　　　　 　　　　ＰＲＥＣ（ｇ，ｈ）＝ｆ 　　　def 　　　　　　＜＝＝＞　ｆ（０,ｘ1,･･･,ｘn）＝ｇ（ｘ1,･･･,ｘn） 　　　　　　　　　　　ｆ（ｎ+１,ｘ1,･･･,ｘn） 　　　↑　 ＝ｈ（ｘ,ｆ（ｘ,ｘ1,･･･,ｘn）,ｘ1,･･･,ｘn） 　　　　　　　 suc(x)｢｢ｺ 　７．２　帰納的関数族（recursive function） ｮ｢｢ｲ 　､定義､ ｶ｢｢ｺ 　　　ｈ：Ｎn+1→Ｎに対して、 　　　　次の関数 　　　　　ｆ：Ｎ　→Ｎ 　　　　を対応させる演算子 （ＭＩＮＳと書く）を 　　　　　最小解 又は最小解演算子、μ作用素 という。 　　　ここで 　　　　　ｆ（ｘ1,ｘ2,･･･,ｘn）＝ｚ 　　　　　　　　　　　　　（ｈ（ｘ1,ｘ2,･･･,ｘn,ｘ）＝０　となるような 　　　　　　　　　　　　　　ｘが存在するとき、ｚはそのようなｘの最小値） ↑ 　　　　　　　　　　　　　　　 　　　　　　　　　　　　自然数 　　　なお、 　　　　　ｮ｢｢｢｢｢｢｢｢｢ｲ 　　　　　､ＭＩＮＳ：　ｈ→ｆ､ 　　　　　ｶ｢｢｢｢｢｢｢｢｢ｺ 　【例】 def 　　　　ｈ（ａ,ｂ,ｃ,ｘ）＝ａｘ^2＋ｂｘ＋ｃのとき、 　　　　　　ＭＩＮＳ（ｈ）＝ｆ 　　　　　　ｆ（ａ,ｂ,ｃ）＝−ｂ±普iｂ^2＋４ａｃ）／２ａ 　　　　のうち、自然数で小さい方の値　 ｮ｢｢ｲ 　､定義､ ｶ｢｢ｺ 　 def 　　ｆ：帰納的（部分）関数　＜＝＝＞ ｆが基本関数に合成、原始帰納法、 　　　　　　　　　　　　　　　　　 最小解演算子を有限解適用して得られる。 　　　　　帰納的関数は全て 帰納的部分関数である ｮ｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ｮ｢｢｢｢ﾞ｢帰納的部分関数 ､ｮ｢｢｢｢｢｢ﾖ｢ｲ ､ 　　　　､､ｮ｢｢｢｢ｲ　　､　　ｾ｢原始帰納的部分関数 　　　　､､､　　　　､　　､　　､　 　　　　､､ｶ｢｢｢｢ｺ×｢ﾞ｢｢ﾞ｢→上の例 ､ｶ｢｢｢｢｢｢｢｢ｺ ､ 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢ｺ ｮ｢｢｢｢｢｢｢ｲ　 　､帰納的全域関数､ ★帰納的関数は全て全域関数 ｶ｢｢｢｢｢｢｢ｺ 　　　　ｈ（ｘ1,ｘ2,･･･,ｘn,ｘ）は正則 　　　　　 def 　　　　　　　＜＝＝＞ ｘ1,ｘ2,･･･,ｘn｢Ｎ，･ｘ｢Ｎ 　　　　　　　　　　　　ｈ（ｘ1,･･･,ｘn,ｘ）＝０ 　　　　注）正則関数ｈの最小化 　　　　　　　　ＭＩＮＳ（ｈ）＝ｆ ↑ 　　　　　　　　　　　　　正則 　ｮ｢定理７.２ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ 　､　　ｆが帰納的全域関数　 ､ 　､　　　　＜＝＞ ｆは基本関数に合成、原始帰納法、正則関数の､ 　､　　　　　　　最小化を有限回適用して得られる。 ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　ｮ｢定理７.３ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ 　､　　帰納的全域関数族　　原始帰納的関数族 ､ 　､　　　　TREC　　　　　　　↑ PREC ､ 　､　　　　　　　　　　　　原始帰納的関数は帰納的関数である ､ 　､　　　　　　　　　　　　　　　　　　　　　　‖ ､ 　､　　　　　　　　　　　　　　　　　　　　全域関数 ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　【証明】 　　　次の関数　ａｃｋ： 　　　　　　ａｃｋ　ＴＲＥＣ−ＰＲＥＣ 　　　　ここで 　　　　　　／ａｃｋ（０,ｙ）＝ｙ＋１ 　　　　　 ､ ａｃｋ（ｘ+１,０）＝ｆ（ｘ,１） 　　　　　　＼ａｃｋ（ｘ+１,ｙ+１）＝ａｃｋ（ｘ,ａｃｋ（ｘ+１,ｙ）） 　注）　ａｃｋを　Ａｃｋｅｒｍａｎ関数　という 　 ↑ 　　　　　　　　　　　　原始帰納的関数でない 　　　　　　　／ＭＩＮＳ ←→　WHILE DO ･･･ 　　　　　　 ､ ＰＲＥＣ　←→　DO I=1 TO N ･･･ 　＼ＣＯＭＰ　←→　Ｐ1,Ｐ2 　　　　ここで０変数関数は定数関数とする 　　　　即ち、ｎ＝０のとき 　　　　　　　／ｆ（０）＝ｇ（）＝ｋ ､ 　　　　　　　＼ｆ（ｓｕｃ（ｘ））＝ｈ（ｘ,ｆ（ｘ）） 　《例》 　　　　ｇ（）＝１，ｈ（ｘ,ｆ（ｘ））＝（ｘ+１）*ｆ（ｘ） 　　　とすると、 　　　　［ｈ（ｘ,ｙ）＝（ｘ+１）ｙ］ 　　　　ＰＲＥＣ（ｇ,ｈ）＝ｘ！ ｮ｢｢ｲ 　､定義､ ｶ｢｢ｺ 　　　ｆが原始帰納的（primitie recursie） 　　 　　　　def 　　　　　　＜＝＝＞ ｆは基本関数から合成演算子と原始帰納法演算子を 　　　　　　　　　　用いて“構成できる“。 　原始帰納的関数の例 　　【例３．１】 （加算） 　　　　次の関数ａｄｄは原始帰納的。 　　　　ここで 　　　　　 ／ａｄｄ（０,ｙ）＝ｙ ､ 　　　　　 ＼ａｄｄ（ｘ+１,ｙ）＝ａｄｄ（ｘ,ｙ）+１‥‥‥‥（１） 　　　　即ち、 　　　　　　ａｄｄ（ｘ,ｙ）＝ｘ+ｙ 　　〔解〕 　　　　　ｎｉｌ，ｓｕｃ，(ｕi)↑ｎ，ＣＯＭＰ，ＰＲＥＣを適当に組み合わせ 　　　　て、（１）が記述出来ればよい 　　　　　ａｄｄ＝ＰＲＥＣ（ｕi,ＣＯＭＰ（ｓｕｃ,(ｕ23））‥‥（２） 　　↑ ↑ ↑ 即ちａｄｄはｆ ｇ ｈ ｕi ／ 　　　　　　　←ＰＲＥＣ　 ｓｕｃ（ｘ,ｙ） 　　　　　　　　　　　　　＼　　　　 ／ ＣＯＭＰ ＼ ｕ23 　　　　（噤jＰＲＥＣの定義より、 　 ／ａｄｄ（０,ｙ）＝ｕi（ｙ）＝ｙ 　　　　　 （２）＜＝＞ ､ ↑ ＼ａｄｄ（ｓｕｃ（ｘ）,ｙ） 　　　ＰＲＥＣの定義　 ＝ＣＯＭＰ（ｓｕｃ,ｕ23） 　　　　　　　　　　　　　　　　　　　　　　　　（ｘ,ａｄｄ（ｘ,ｙ）,ｙ） 　　 　 ＣＯＭＰの定義 → ＝ｓｕｃ（ｕ23（ｘ,ａｄｄ（ｘ,ｙ）,ｙ） 　ｮ｢｢｢｢｢｢｢｢｢ｲ 　　　　　　　　　　　　　　　 ＝ ､ａｄｄ（ｘ,ｙ）+１､　　 　ｶ｢｢｢｢｢｢｢｢｢ｺ ↑ 　　　　　　　　　　　　　　　　　　ｓｕｃとｕ23の定義 　　【例３．２】 　　　　次の関数 ｍｕｌｔ は原始帰納的 　　　　　ここで 　　　　　　 ／ｍｕｌｔ（０,ｙ）＝０ 　 ､ 　　　　　　 ＼ｍｕｌｔ（ｘ+１,ｙ）＝ｍｕｌｔ（ｘ,ｙ）+ｙ 　　即ち、 　　　　　　ｍｕｌｔ（ｘ,ｙ）＝ｘ・ｙ 　　〔解〕 　　　　ｍｕｌｔ（ｘ,ｙ） 　　　　　　　＝ＰＲＥＣ（ｍｉｌ,ＣＯＭＰ（ａｄｄ,ｕ23,ｕ23））（ｘ,ｙ） 　　　　ただし、ａｄｄは、例3.1(2) 　【問】 　　　（１）ｘ！ 　　　　　　 　／ｆａｃｔ（０）＝１ 　　､ 　　　　　　 　＼ｆａｃｔ（ｘ+１）＝ｆａｃｔ（ｘ）*（ｘ+１） 　　　（２）ｘ↑2 　 ／ｅｘｐ（０,ｘ）＝１ 　 ､ 　　　　　　　 ＼ｅｘｐ（ｎ+１,ｘ）＝ｅｘｐ（ｎ,ｘ）*ｘ 　　　（３）ｄｉｖ（ｘ,ｙ）　（＝ｘ／ｙ　切り捨て） 　　以上の関数が原始帰納的であることを示せ。 　　　 　　　／ 細井　勉 　　　 　　　＼ 広瀬　　、帰納法、サイエンス社 　　 　　注）　ａｃｋ（０,ｙ）＝ｙ+１ 　　　　　ａｃｋ（１,ｙ）＝ｙ+２ 　　　　　ａｃｋ（２,ｙ）＝２ｙ+３ ↑ 　　　　　ａｃｋ（３,ｙ）＝２↑（ｙ+３）−３ （？） 　　　　　ａｃｋ（４,ｙ）＝２↑２↑･･･↑２−３ ↓ ｶ｢｢ﾎ｢｢｢｢ｺ 　 ｙ+３ 　　　　　ａｃｋ（５,ｙ）＝２↑２↑･･･↑２−３ 　　　　　　　　　　　　　ｶ｢｢ﾎ｢｢｢｢ｺ　　 ／ ２↑２↑･･･↑２ ＼ 　　　　　　　　　　　〔　ｶ｢｢ﾎ｢｢｢｢ｺ 〕 ＼ ｙ+３ ／ 　　　（例）　ａｃｋ（５,１） 　　　　　　＝２↑２↑･･･↑２−３＝２↑２↑･･･↑２−３ 　　　　　　 ｶ｢｢ﾎ｢｢｢ｺ ｶ｢｢ﾎ｢｢｢ｺ 　　　　　　　 2↑2↑2↑2 65536 ”基礎論的数” 　《問の解答》 　　　　（１）ＰＲＥＣのとき、０変数関数は定数関数であるので 　　　　　　　　　ｆａｃｔ（０）＝１ 　　　　　　　とする。 　　　　　　　fact(suc(x))=COMP(mult,COMP(suc,U12),U22)(x,fact(x)) =mult(COMP(suc,U12)(x,fact(x)),U22(x,fact(x)) =mult(suc(U12 (x,fact(x))),fact(x)) =mult(suc(x),fact(x)) =mult(x+1,fact(x)) =(x+1)*fact(x) よって 　　　　　　　fact=PREC(COMP(suc,nil)COMP(mult,COMP(suc,U12),U22)) ただし、 　　　　　　　　 ／mult=PREC(nil,COMP(add,U12,U22)) ､ ＼add=PREC(U11,COMP(suc,U23)) 　　　　　　　　fact(0)=1 　　　　 def 　　 補注） nil( ) = 0 （２） exp(0,x)=COMP(suc,nil)(x) =suc(nil(x)) =suc(0) =0+1 =1 exp(n+1,x)=COMP(mult,U23,U33)(n,exp(n,x),x) =mult(U23(n,exp(n,x),x),U33(n,exp(n,x),x)) =mult(exp(n,x),x) =exp(n,x)*x ∴ exp=PREC(COMP(suc,nil),COMP(mult,U23,U33)) ただし 　　　　　　　 ／mult=PREC(nil,COMP(add,U23,U33)) 　　､ 　　 ＼add=PREC(U11,COMP(suc,U23)) （３）　関数div(x,y)が原始帰納的であることを示す前に、いくつかの 　　　　　　　他の関数が原始帰納的であることを導入する。 　　　　　　@前者関数pred(x)は原始帰納的である。 ／x-1 (x>0) 　　　　　　　　　　pred(x)=､ ＼ 0 (x=0) ／pred(0)=0 ､ 　　　　　　　　 ＼pred(suc(x))=x と定義すると、 　 pred=PREC(U12) (pred(0)=0) 噤jpred(0)=0 とする 　　　　　　　　　　pred(suc(x))=U12(x,pred(x)) =x A 差関数 　 ／x-y (x>y) 　　　　　 sub(x,y)､　 　　　　　　　　　 ＼ 0 (x<=y) は原始帰納的である。 　　　　　　　　 ／sub(x,0)= x ､ 　 ＼sub(x,y+1)=pred(sub(x,y)) と定義すると、 　　　　　　　　　　sub=COMP(PREC(U11,COMP(pred,U23)),U22,U12) 噤j subi(y,x)=sub(x,y) と定義する。 　　　　　　　　　　　　　 　　　　　　　　　　　 ／subi(0,x)= x= (x) ､ ＼subi(y+1,x)=PRED(subi(y,x)) =(PRED,U23(y,subi(y,x),x)) =COMP(PRED,U23) sub(x,y)=(subi,U22,U12)(x,y) =COMP(subi,U22,U12)(x,y) =COMP(PREC(U11,COMP(PRED,U23)),U22,U12) 　　　 B関数｜x-y｜= (｜sub｜(x,y)) は原始帰納的である。 　　　　　　 ｜x-y｜= (x-y)+(y-x)と定義すると、 　　　　　　 ｜sub｜= COMP(add,sub,COMP(sub,U22,U12)) 　　　 ) ｜sub｜(x,y)=COMP(add,sub,COMP(sub,U22,U12))(x,y) 　　　 =add(sub(x,y),COMP(sub,U22,U12)(x,y)) 　　　 =add(sub(x,y),sub(U22(x,y),U12(x,y))) 　　　 =add(sub(x,y),sub(y,x)) （add = PREC(U11,COMP(suc,U23))） C T）関数 　　　 ／0 (x=0) 　　　　　　　　　　　ｓq =､ ＼1 (x≠0) は原始帰納的である。 　　　　　　　　　　　 ／ｓq(0)=0 　､ ＼ｓq(suc(x))=1 と定義すると、 　　　　　　　 　　　　　　　　　　　ｓq = PREC(nil,(ｓq(0)=0) 噤jSq(0)=0 とする 　　　　　　　　　　　　Sq(suc(x))=COMP(suc,COMP(nil,U12))(x,Sq(x)) 　　　 　 =suc(COMP(nil,U12)(x,Sq(x))) 　　　　 =suc(nil(x)) 　　　　=suc(0) 　　　　=1 U）関数 ＿ ／1 (x=0) Sq(x) =､ ＼0 (x≠0) は原始帰納的である。 ＿ ／Sq(0)=1 ､ ＿ ＼Sq(suc(x))=0 と定義すると、 ＿ ＿ 　　　　　　　　　　　Sq = PREC(COMP(suc,nil),COMP(nil,U12)) (Sq(0)=1) ＿ 噤jSq(0)=1 とする ＿ ＿ Sq(suc(x)) = COMP(nil,U12)(x,Sq(x)) ＿ = nil(U12(x,Sq(x))) = nil(x) = 0 Dｘをｙで割ったときの余りを rm(x,y) で表す。 　　　　　　　　 このとき rm(x,y) は原始帰納的である。 　　　　　　　　　 ／rm(0,y)=0 ､ ＼rm(suc(x),y)=suc(rm(x,y)) Sq(｜y -suc(rm(x,y))｜) と定義できる。 　 　　　　　　　　　　rm = PREC(nil,COMP(mult,COMP(suc,U23), 　　　　　　　　　　　　　　　COMP(Sq,COMP(｜sub｜,U33,COMP(suc,U23))) 　　　 　) rm(0,y)=nil(y)=0 　　　　 rm(suc(x),y)=COMP(mult,COMP(suc,U23),COMP(Sq, 　　 　　 　　　 COMP(｜sub｜,U33,COMP(suc,U23)))) 　 (x,rm(x,y)) 　　　 =mult(COMP(suc,U23)(x,rm(x,y),y),COMP(Sq, 　　 COMP(｜sub｜,U33,COMP(suc,U23))) 　 (x,rm(x,y)) =mult(suc(U23(x,rm(x,y),y)), Sq(COMP(｜sub｜,U33,COMP(suc,U23)) (x,rm(x,y),y) =mult(suc(rm(x,y)),Sq(｜sub｜ (U33(x,rm(x,y),y),COMP(suc,U23) (x,rm(x,y)) 　　　 =mult(suc(rm(x,y)), 　　　　　　　　　　　　　　　　　　Sq(｜sub｜(y,suc(U23(x,rm(x,y),y)))) 　　 =mult(suc(rm(x,y)), 　　　　　　　　　　　　　　　　　　Sq(｜sub｜(y,suc(rm(x,y))))) 　［mult = PREC(nil,COMP(add,U23,U33))］ 　　　　　　 　abs : 　 ／abs(0,y) = (y) 　 ､ 　 ＼abs(x+1,y) = ((x+1)-y)+(y-(x+1)) 　 abs = PREC(U11,COMP(sub,COMP(add,U23,COMP(Sq,COMP(sub, 　　 　 COMP(sub,U33,U23),COMP(suc,nil))))) 　 　 以上の事より div(x,y) が原始帰納的であることを示す。 　　　　　　　 ／div(0,y)=0 ､ 　　　　　　　　　　　 ＿ ＼div(suc(x),y)=div(x,y)+Sq(｜y-suc(rm(x,y))｜) 　　と定義できる。 　　　　　　 div = PREC(nil,COMP(add,U23,COMP(Sq,COMP(｜sub｜,U33, 　　 　　　　　　　　　　　　COMP(rm,U13,U33)))) 　 　) div(0,y) = nil(y) = 0 　 　 div(suc(x),y) 　　　　　　　　　　　　 =COMP(add,U23,(x,div((x,y),y) ＿ COMP(Sq,COMP(｜sub｜,U33,COMP(suc, 　 COMP(rm,U13,U33) ￣ 　=add(U23(x,div(x,y),y),Sq(COMP(｜sub｜,U33, 　COMP(suc,COMP(rm,U13,U33)))(c,div(x,y),y) ＿ =add(div(x,y),Sq(｜sub｜(U33(x,div(x,y),y), 　COMP(suc,COMP(rm,U13,U33))(x,div(x,y),y)) ＿ =add(div(x,y),Sq(｜sub｜(y,suc( 　COMP(rm,U13,U33)(x,div(x,y),y))))) ＿ =add(div(x,y),Sq(｜sub｜(y,suc( rm(U13(x,div(x,y),y),U33(x,div(x,y),y))) ＿ =add(div(x,y),Sq(｜sub｜(y,suc(rm(x,y))))) 　ｮ｢定理７.４ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　､ ､ 　､　　ｆ：関数 ､ 　､ （１）ｆが帰納的 ＜＝＞ ｆは手続きで全域計算可能 ､ 　､ （２）ｆが部分帰納的 ＜＝＞ ｆは手続きで部分計算可能､ 　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 【証明】 　　　（１）(→) @基本関数は手続き計算可能 　　　　　　　 　 A　／ｆ,ｇ1,･･･,ｇn,ｇ　が手続き計算可能 　　　　　　　　　､　　 ／ＣＯＭＰ（ｆ,ｇ1,･･･,ｇn） ､ 　 ＝､ ＰＲＥＣ（ｆ,ｇ） ､ ＼ＭＩＮＳ（ｆ） ､ 　は手続きで計算可能 　　　　　　　　　 ＼　　　（計算する手続きを構成する）　 (←) Ｇｏｄｅｌ　ｎｕｍｂｅｒｉｎｇ による ｆ：Ａ→Ｂ　において ／全域関数： Ａの全ての要素に対してＢのある要素を対応させる ､ ＼部分関数： 必ずしもＡの全ての要素にＢの要素を対応させない §８．Ｔｕｒｉｎｇ　ａｕｔｏｍａｔｏｎ 　　 （Turing, 1935頃） 現在の computer に影響を　与えた "らしい" 手続きで計算可能　 　　　　　　　帰納関数族 　　　　ｮ｢｢｢ｲ ｮ｢｢｢ｲ ､ ､ 　＝ ､ ､ ､ ､ ､ ､ ｶ｢｢｢ｺ ｶ｢｢｢ｺ プログラム　　　　　　　　　　　関数 ‖ Taで計算可能 　　ｮ｢｢｢｢｢｢｢｢｢｢｢ｲ ｮ｢｢｢ｲ 　　､計算量（time,space）は､ ､ ､ 　　､Taの上で定義される。　､ ､ ､ ｶ｢｢｢｢｢｢｢｢｢｢｢ｺ ｶ｢｢｢ｺ 　計算機 　 　　文献 　　　細井　勉　　　　計算の基礎理論 　　　ﾎﾌﾟｸﾛﾌﾄ/ｳﾙﾏﾝ　　言語理論とオートマトン 　　　　　　・計算可能性の定義を考える。 　　　　　　　計算のモデル 　　　　　　・計算機数学の中の計算理論の一分野 ｮ｢｢ｲ 　､概略､ ｶ｢｢ｺ 　　　Turing automaton (machine) (pl.automata)は、次のような 　　　　データ処理系（→代数学）（データ構造） 　　　　（｛データ｝，｛操作｝）である。 　　i.〔データ〕 　　　　データ（様相という）は次の形： c(tape(c(location))) 　　 head location tape 　　　　　 　　　 ↑ ｮ｢｢ﾎ｢｢ｲ ｮ｢｢ﾎ｢｢ﾎ｢｢｢｢｢ﾎ｢｢ﾎ｢｢｢ Ｃ：､文字､､　､ ､文字､文字､ 　・・・ ､文字､ ｶ｢｢ﾖﾞ｢ｺ ｶ｢｢ﾖ｢｢ﾖ｢｢｢｢｢ﾖ｢｢ﾖ｢｢｢ ､ (1) (2) 　 ↑ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｡　 　 ii.〔操作〕 　　　　Taの操作は上のような様相の内容を書きかえるもの 　　　　　　　操作：Ｃ→Ｃ’　（Ｃ，Ｃ’は様相） で以下の３種： 　　 　　　a.　c(head)上の文字の書きかえ 　　　　　　b. c(tape)上の文字の書きかえ 　　　　　　　　　　但し、１回に書きかえる文字は、c(location)のさしている 　　　　　　　　　tape上の位置 c(tape(c(location)))のみ。 　　　　 c. c(location)の書きかえ　 　　　　　　　　　　但し、c'(location) = c(location)+1 　 〃 +0 　 〃 -1 のいずれか。 ｮ｢｢｢｢ｲ 　　　　以上の操作は、”状態”､c(head) ､と locationのさしている文字 ｮ｢｢｢｢｢｢｢｢｢｢ｲｶ｢｢｢｢ｺ ｮ｢｢ｲ 　　　､c(tape(c(location)))､　に対してあらかじめ定められた､規則､ ｶ｢｢｢｢｢｢｢｢｢｢ｺ ｶ｢｢ｺ 　　　　（”プログラム”という）に従ってえらばれる。 　　　　　　 Ｃｮ｢ﾎ｢ｲ　ｮ｢ﾎ｢ﾎ｢ﾎ｢｢　　 Ｃ'ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ ､□､､､　､ ､ ､回､… ｢→ ､ ､ ､ ､ ､ ､ ､… ｶ｢ﾖﾞｺ　ｶ｢ﾖ｢ﾖ｢ﾖ｢｢ 操作 ｶ｢ﾖ｢ｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ ､ ↑ ↑ 　　　　ｶ｢｢｢｢｢｢｢｡　　　　｜ ｮ｢｢｢｢｢｢｢｢｢｢｢ｲ ､書き換え規則プログラム､ ｶ｢｢｢｢｢｢｢｢｢｢｢ｺ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､Turing オートマトンの例： ､ ､　　　　 関数を実現する例 ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ Turing オートマトンは次の機能をもつ。 　　　(1) ｆ：Ｎk　→　Ｎ　（ｋ変数関数） 　　　 　　　　　　　　　　　いわゆる"計算" (2) ｆ：Ｎ　→　｛０，１｝ Ｎｮ｢｢｢｢｢｢｢｢ｲ ､ ｢｢｢｢ﾞ｢｢→０ ､ ｮ｢｢｢ｲ ､ ､ ､ ｢ﾞ｢｢ﾞ｢｢→１ ､ ｶ｢｢｢ｺ ､ ､ ､ いわゆる"識別" ｶ｢｢｢｢｢｢｢｢ｺ 以下で計算(1)の例をあげる。 【例】 　 ｙ＝２ｘ を計算するTa Ａ＝（ｋ，Σ，Ｒ，ｑ0，Ｆ） ここで ｋ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝…head上の文字 　　　　　Σ＝｛ｂ，１，１’｝ …tape上の文字 　　　　　ｑ0＝Ａ …最初のhead上の文字 　　　　　Ｆ＝｛Ｈ｝ …最終のhead上の文字 　　　　　Ｒ …書きかえrule ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､Ｃ0ｾCＣ１ｾC････ｾ Ｃn ､ ､ｘｾ｢｢｢｢｢｢｢｢→２ｘ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ Ｒ：Ｋ×Σ　→ Ｋ×Σ×｛−１，０，１｝ 　　　　　　　　　Ｒ：（ｑ，Ｓ）　→ （ｑ’，Ｓ’，ｍｏｖｅ） ｑ　　　　　　　　　Ｓ　　　　　　ｑ’　　　　　　　　Ｓ’　 ｮ｢ﾎ｢ｲ　ｮ｢｢ﾎ｢ﾎ｢｢ ｮ｢ﾎ｢ｲ　ｮ｢｢ﾎ｢ﾎ｢｢ ､ ､､､　､……､ ､… ｾ｢｢､ ､､､　､……､　､… ｶ｢ﾖﾞｺ　ｶ｢｢ﾖ｢ﾖ｢｢ ｶ｢ﾖﾞｺ　ｶ｢｢ﾖ｢ﾖ｢｢ ､ ↑ ､ ↑ ｶ｢｢｢｢｢｢｡ ｶ｢｢｢｢｢｢｡ ←→ｍｏｖｅ 　　　　ＲｮＫ×Σ×Ｋ×Σ×｛−１，０，１｝ 　 ｑ　　Ｓ　　　Ｑ’　Ｓ’　ｍｏｖｅ ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ 　 Ａ　　ｂ　　　Ｈ　　ｂ 　　　０ 　　　　　　　　 Ａ　　１　　　Ｂ　　ｂ　　　 １　　　　 　　 Ａ　　１’　　Ｈ　　１’　 ０ 　下の表で書く ｮ｢｢｢ﾎ｢｢｢｢｢｢｢｢ﾎ｢｢｢｢｢｢｢｢｢ﾎ｢｢｢｢｢｢｢｢ｲ　　 ､ｑ＼Ｓ､　　　ｂ　　　　､　　　　１　　　 ､　　　１’ ､ 　 ｾ｢｢｢ﾞ｢｢｢｢｢｢｢｢ﾞ｢｢｢｢｢｢｢｢｢ﾞ｢｢｢｢｢｢｢｢ﾆ　　 ､　 Ａ ､（Ｈ，ｂ，　０）､（Ｂ，ｂ　，　１）､（Ｈ，１’，０）､ 　 ､　 Ｂ ､（Ｆ，１，−１）､（Ｃ，１’，　１）､（Ｈ，１’，０）､ 　 ､　 Ｃ ､（Ｄ，ｂ，　１）､（Ｃ，１　，　１）､（Ｈ，１’，０）､ 　 ､　 Ｄ ､（Ｅ，１，−１）､（Ｄ，１　，　１）､（Ｈ，１’，０）､ 　 ､　 Ｅ ､（Ｅ，ｂ，−１）､（Ｅ，１　，−１）､（Ｂ，１　，１）､ 　 ､　 Ｆ ､（Ｇ，ｂ，　１）､（Ｆ，１　，−１）､（Ｈ，１’，０）､ 　 ､　 Ｇ ､（Ｈ，ｂ，　０）､（Ｈ，１　，　０）､（Ｈ，１’，０）､ 　 ､　 Ｈ ､（Ｈ，ｂ，　０）､（Ｈ，１　，　０）､（Ｈ，１’，０）､ 　 ｶ｢｢｢ﾖ｢｢｢｢｢｢｢｢ﾖ｢｢｢｢｢｢｢｢｢ﾖ｢｢｢｢｢｢｢｢ｺ　　 上のＡは、１x+1 を"入力"して　１2X+1 を"出力"することを確かめよ。 （→Ｘの１進表示） 　　ｘ＝２として考える。 １2+1＝１１１＝（２）1 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ､Ａ､､､ ､１､１､１､ｂ､… ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｂ､､､ ､ｂ､１､１､ｂ､… (A,1,B,b,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｡ ↓計算機の 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ １単位時間 ｾ｢｢｢｢｢｢｢　､Ｃ､､､ ､ｂ､1'､１､ｂ､… (B,1,C,1',R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｃ､､､ ､ｂ､1'､１､ｂ､… (C,1,C,1,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｄ､､､ ､ｂ､1'､１､ｂ､ｂ､ (C,b,D,b,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｅ､､､ ､ｂ､1'､１､ｂ､１､ｂ､ (D,b,E,1,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｅ､､､ ､ｂ､1'､１､ｂ､１､ｂ､ (E,b,E,b,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｅ､､､ ､ｂ､1'､１､ｂ､１､ｂ､ (E,1,E,1,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｂ､､､ ､ｂ､１､１､ｂ､１､ｂ､ (E,1',B,1,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｃ､､､ ､ｂ､１､1'､ｂ､１､ｂ､ (B,1,C,1',R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｄ､､､ ､ｂ､１､1'､ｂ､１､ｂ､ (C,b,D,b,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｄ､､､ ､ｂ､１､1'､ｂ､１､ｂ､ (D,1,D,1,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｅ､､､ ､ｂ､１､1'､ｂ､１､１､ｂ､ (D,b,E,1,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｅ､､､ ､ｂ､１､1'､ｂ､１､１､ｂ､ (E,1,E,1,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｅ､､､ ､ｂ､１､1'､ｂ､１､１､ｂ､ (E,b,E,b,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｂ､､､ ､ｂ､１､１､ｂ､１､１､ｂ､ (E,1',B,1,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｆ､､､ ､ｂ､１､１､１､１､１､ｂ､ (B,b,F,1,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｆ､､､ ､ｂ､１､１､１､１､１､ｂ､ (F,1,F,1,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｆ､､､ ､ｂ､１､１､１､１､１､ｂ､ (F,1,F,1,L) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｇ､､､ ､ｂ､１､１､１､１､１､ｂ､ (F,b,G,b,R) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｡ 　 ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ｾ｢｢｢｢｢｢｢　､Ｈ､､､ ､ｂ､１､１､１､１､１､ｂ､ (G,1,H,1,0) ｶ｢ﾖﾞｺ ｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｢｢｢｡ １5＝（４）1 ｮ｢｢ｲ ､定義､ ｶ｢｢ｺ 部分関数 ｆ：Ｎk→ＮがＴａ部分計算可能。 （ｆはｋ変数） def ＜＝＝＞次のようなＴａ Ａ（ｋ,,Ｒ,ｑ0,Ｆ）が存在する。 即ち、(ｘ1,…,ｘk)｢Dom ｆに対して、 ｆ(ｘ1,…,ｘr)＝ｙ ↑ ※ Dom ｆ：ｆの定義域。 ↓ 次の計算列がＡに存在。 ｘ1＋１個 ｘ2＋１個 ｘn＋１個 　　　　　ｮ｢｢｢｢｢｢｢ｲ　ｮ｢｢｢｢｢ｲ　　　　　ｮ｢｢｢｢｢ｲ ｮ｢ﾎ｢ｲｮ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ ､q0､､､､１､１､…､１､ｂ､１､…､１､ｂ､…､ｂ､１､…､１､ｂ… ｶ｢ﾖﾞｺｶ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ ､ ↑ ｶ｢｢｡ ｙ＋１個 ｮ｢｢｢｢｢｢｢｢｢ｲ Ｒ Ｒ ｮ｢ﾎ｢ｲ ｮ｢ﾎ｢｢｢｢｢ﾎ｢ﾎ｢ﾎ｢｢｢｢｢｢｢｢ ﾅ｣…ﾅ｣ ､ｑ､､､ ､１､‥‥‥‥‥､１､ｂ､‥‥‥‥‥‥‥ ｶ｢ﾖﾞｺ ｶ｢ﾖ｢｢｢｢｢ﾖ｢ﾖ｢ﾖ｢｢｢｢｢｢｢｢ ､ ↑ ｮ｢｢｢｢ｲ 但し、ｑ｢Ｆ ｶ｢｢｢｢｢｢｢｡ ､答え ｙ､ ｶ｢｢｢｢ｺ §９．帰納的集合族 　識別可能関数族 　　　　　　（この章）　　　　　　　　　　　（前章まで） ｮ｢｢｢｢｢｢ｲ ｮ｢｢｢｢｢｢｢｢ｲ 　　　　､　　　　　　､　　特長化 ､ ､ ､ ｮ｢｢ﾎ｢ﾞ｢｢｢←｢｢｢｢ﾞ｢ﾎ｢｢｢｢ｲ ､ 　　　　､　､　　､　､　　　 　　　　､　､帰納的 ､ ､ 　　　　､　､　　､　､　　　 　　　　､　､関数族 ､ ､ ､ ｶ｢｢ﾖ｢ﾞ｢｢｢←｢｢｢｢ﾞ｢ﾖ｢｢｢｢ｺ ､ ､ ､ ､ ､ ｶ｢｢｢｢｢｢ｺ ｶ｢｢｢｢｢｢｢｢ｺ ２N ｆ：Ｎk→Ｎの全体 　この章：２Nの分類 　　　　　　帰納的関数 　 　　　　　　計算可能関数 　　　 　　　　　に対応するものを明らかにする。 　　　 １対１ 　　　　（注）｛ｆ：Ｎ→Ｎ｝――→ ２N N ←→ Ｒ 　　　　　　　　　　　　　　　　　　↑ 　 　　　 ↓ 　　　　　　　　　　　　　　　　　 ２N 　９．１　帰納的集合族 　　／ｆ：Ｎ→｛１｝がＳｮＮ＼ def　 ／　　　　　／１（ｘ｢Ｓ） 　 ､　　　　　　　　　　　　､←―→､ｆ（ｘ）＝､ 　　＼の特長部分関数　　　　／　　 　 ＼ 　　　 　＼undefined（ｘﾃＳ） ｮ｢｢｢｢｢｢ｲ 　､定義９.１.１､ ｶ｢｢｢｢｢｢ｺ 　　　ＳｮＮが部分帰納的　　　 ＼　def　　／帰納的な特長部分関数が 　 （帰納可算的recursively）／ ←―→　＼Ｓに存在。 　　　enumerable semirecursive(RE) 　　／ｆ：Ｎ→｛０，１｝がＳｮＮ＼ ｄｅｆ ／　　　　 　／ １（ｘ｢Ｓ） 　　 ､ 　　　　　　　　　　 ､←―→､ｆ（ｘ）＝ ､ 　　　＼の特長（全域）関数　　　　／ 　　　 ＼　　　　 　＼ ０（ｘﾃＳ） ｮ｢｢｢｢｢｢ｲ 　､定義９.１.２､ ｶ｢｢｢｢｢｢ｺ 　　　ＳｮＮが帰納的　←―→　帰納的な特長全域関数がＳに存在 　　　　　　(REC) 　　　　　　　　　　球団全体 ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ｮ｢｢｢｢｢｢｢｢｢ｲ ､ 　　　　　､　､いつか優勝する球団ｾ｢ﾞ｢｢ＲＥ ､ ｶ｢｢｢｢｢｢｢｢｢ｺ ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ｮ｢｢｢｢｢｢｢｢ｲ ､ 　　　　　､　､来年優勝する球団ｾ｢｢ﾞ｢｢ＲＥＣ ､ ｶ｢｢｢｢｢｢｢｢ｺ ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　､　ｮ｢｢｢｢｢｢｢｢ｲ　　､ 　　　　　､　､いつまでたってもｾ｢｢ﾞ｢｢ＲＥでない 　　､　､ 優勝しない球団 ､　　､ ､ ｶ｢｢｢｢｢｢｢｢ｺ ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　ｮ｢定理８.１.１｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ 　､　　ＳｮＮが帰納的 ←→ ＳとＮ―Ｓが部分帰納的 ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　【証明】 　　　下の図を参照 ｮ｢｢｢｢｢ｲ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　 ､Ｓ：帰納的､→､ｆ　s.t. ､ ｶ｢｢｢｢｢ｺ右､　　　　　　 ／１(ｘ｢Ｓ) ､｢｢｢ｲ ｮ｢｢｢｢｢｢｢｢ｲ　､　ｆ（ｘ）＝､ ､ ､ ､ｆはＳの特長関数､←､ 　 ＼０(ｘﾃＳ) ､ ､ ｶ｢｢｢｢｢｢｢｢ｺ左ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ､ 　　　　 右↓ ､ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ 　　　､　　＿ ､ ､ ､ｇ，ｇ ､ ､ 　　　､　　　　　　　／１（ｘ｢Ｓ） ､ 左 ､ 　　　､　 ｇ（ｘ）＝､ ､ ､ 　　　､　　　　　　　＼undefined (ｘﾃＳ)､ ､ 　　　､　　　　　　　　 ､ ､ 　　　､　 ＿ 　／１ (ｘ｢Ｓ)､ ､ 　　　､　 ｇ（ｘ）＝､ ､ ､ 　　　､　　　　　　　＼undefined (ｘﾃＳ)､ ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ ､ 　 右↓　　左↑　　　　　　左↓ ､ ｮ｢｢｢｢｢｢｢｢｢｢ｲ ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　､ｇ：Ｓの特長部分関数､ ､　　＿ ､ 　､￣　￣ ､ ､ ｇ’s.t. ､ 　､ｇ：Ｓ（＝Ｎ−Ｓ） ､　､　　　　　　　　　　＿ ､ ｶ｢｢｢｢｢｢｢｢｢｢ｺ ､ ＿ 　／０(ｇ（ｘ）＝１) ､ 右↓　左↑　　　　　　　 ､ 　 ｇ'（ｘ）＝､ ､ ｮ｢｢｢｢｢ｲ ､ 　　　　 　＼undefined (その他)､ 　､Ｓ：ｒ.ｅ.､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　､￣ ､ 　　　　　　　　　　　　　　　　　　　　 　､Ｓ：ｒ.ｅ.､ 　＿ ｶ｢｢｢｢｢ｺ （ｇの１を０にする） ｮ｢定理９.１.２｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､ ､ 　､　　帰納的集合族ﾊ部分帰納的集合族 （ＲＥＣﾊＲＥ） ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　【証明】 　　　@ ｮは明らか 　　　A ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ 　　　　　､Ｓ＝｛入力０で停止する手続きのゲーデルコード全体｝､ ､ を考えると　Ｓ｢ＲＥ−ＲＥＣ ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　　　 ↓ 　　　ｮ｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ　ｮ｢｢｢｢｢｢｢｢ｲ 　　　　　､この手続きは計算可能でない､　､　Ｓ｢ＲＥ ､ 　　　､（１で止まる、０で無限）　､　､　ＳﾃＲＥＣ ､ 　　　ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ　､ ､ ､ ､　　　　　 ／１ ､ 　　　　　　　　　､　　　　　　　　　　　､ｆ（ｘ）＝､ ､ 　　　　　　　　　､　　　　　　　　　　　､　　　　　 ＼０ ､ ､ ｶ｢｢｢｢｢｢｢｢ｺ ､ ↓ 　 ｮ｢｢ｲ ｮ｢｢｢｢ｲ 　　　　　　　､矛盾､｢｢｢｢｢｢｢｢｢｢｢｢､計算可能､ ｶ｢｢ｺ ｶ｢｢｢｢ｺ 　９．２　識別可能集合族 ｮ｢｢｢｢｢｢ｲ 　､定義８.１.２､ ｶ｢｢｢｢｢｢ｺ 　　　　ＳｮＮとする 　　ｄｅｆ 　　　　Ｓが部分識別可能←―→Ｓに計算可能な特長部分関数が存在 　　　　　　　　　　　　　　ｄｅｆ 　　　　Ｓが（全域）識別可能←―→Ｓに計算可能な特長全域関数が存在 　　　　　　　　 　ｮ｢定理８.２.１｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｲ ､　　　　　　　 ､ 　､　　ＳｮＮとする ､ 　､　　　1) Ｓが部分識別可能←→Ｓは部分帰納的 ､ 　､　　　2) Ｓが全域識別可能←→Ｓは帰納的 ､ ｶ｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢｢ｺ 　例）１．偶数全体 　　　２．素数全体 　【問】 　　　　ｆ（ｘ,ｙ,ｚ）＝ｘｙ＋ｚ 　　　　ｆ（ｘ,ｙ）＝２ｘ＋ｙ 【練習問題】 次のオートマトン、言語理論における unsolvableな問題を説明せよ。 　 1. 　アルファベット｛０，１，Ｂ｝を持つＴＭが、テープ上に３つ並んだ 　　　１を書くことがあるか否かという問題は決定不能である。 　 2. 　帰納的可算集合が空であるのは決定不能である。 　 3. 帰納的可算集合が有限であるのは決定不能である。 　 4. 帰納的可算集合が正規であるのは決定不能である。 　 5. 帰納的可算集合が文脈自由であるのは決定不能である。 　 6. 　帰納的可算集合のＬ＝¢という性質は帰納的可算でない。 　 7. 　帰納的可算集合のＬ＝*という性質は帰納的可算でない。 　 8. 　帰納的可算集合のＬは単元集合（ちょうど一つの元を持つ）という性 　　　質は帰納的可算でない。 　 9. 　帰納的可算集合のＬは正則集合という性質は帰納的可算でない。 10. 　任意の文脈自由文法Ｇ1とＧ2について、Ｌ(Ｇ1)とＬ(Ｇ2)の共通集合 　　　が空集合であるか否かという決定問題は非可解である。　 11. 　二つの任意の文脈自由文法Ｇ1とＧ2について、Ｌ(Ｇ1)＝Ｌ(Ｇ2)であ 　　　るか否かという決定問題は非可解である。 12. 　任意の文脈自由文法Ｇと任意の正規集合Ｒについて、Ｌ(Ｇ)＝Ｒであ 　　　るか否かという決定問題は非可解である。 (注) 6.〜9.のＬは無限集合を意味する。 【練習問題の解答】 1. ｢｢ﾎ｢ﾎ｢ﾎ｢ﾎ｢｢ Ｔ （ …､１､１､１､… ） ｮ｢ｲ→ ｢｢ﾖ｢ﾖ｢ﾖ｢ﾖ｢｢ Ａ(ＴＭ)｢→､Ｐ､ ｶ｢ｺ→ Ｆ （その他） 2. Ｔ （Ｓ＝¢） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ Ｆ （Ｓ≠¢） 3. Ｔ （Ｓが有限） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ Ｆ （その他） 4. Ｔ （Ｓが正規） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ Ｆ （その他） 5. Ｔ （Ｓが文脈自由） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ Ｆ （その他） 6. Ｔ （Ｓ＝｡） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ undefined （その他） 7. 　　　　　　　　　　　 Ｔ （Ｓ＝*） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ undefined （その他） 　　　　　　　　　　　 8. Ｔ （Ｓが単元集合 ） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ undefined （その他） 　　　　　　　　　　　 9. Ｔ （Ｓが正則集合） ｮ｢ｲ→ 　　　　　　　　　　　 　 Ｓ 　｢→､Ｐ､ (r,e) ｶ｢ｺ→ undefined （その他） 　　　　　　　　　　　 10. Ｔ （(Ｌ(Ｇ1)宸k(Ｇ2))＝¢） ｮ｢ｲ→ 　　　　　　　　　　　 Ｇ1,Ｇ2 ｢→､Ｐ､ (cfg) ｶ｢ｺ→ Ｆ （その他） 　　　　　　　　　　　 11. Ｔ （(Ｌ(Ｇ1)＝Ｌ(Ｇ2)） ｮ｢ｲ→ 　　　　　　　　　　　 Ｇ1,Ｇ2 ｢→､Ｐ､ (cfg) ｶ｢ｺ→ Ｆ （その他） 　　　　　　　　　　　 12. 　 Ｔ （Ｌ(Ｇ)＝Ｒ） 　ｮ｢ｲ→ 　　　　　　　　　　　 Ｇ,　Ｒ ｢→､Ｐ､ (cfg) (r,s) ｶ｢ｺ→ 　Ｆ （その他）