高橋正子「計算論」近代科学社 (1991)

１．計算可能な関数

• 定義 primitive recursive function (PRF)
  1. 
     
     
     は PRF．
  2. (substitution) PRF に対し，
     は PRF．
  3. (primitive recursion) PRF に対し，
     
     
     は PRF．

• に対し，
  を， をみたす最小の の値とする．
  これは の部分集合上の関数 を与える．
  これを の minimization とよぶ．

• 定義 PRF と PRF の minimization をすべて含み， substitution と primitive recursion で閉じている最小の関数のクラスを，recursive function という．

• universal function とは，recursive であって，任意の n 変数 recursive function f に対し， が存在して となるもの．

• 定理 任意の に対し，n+1 変数 universal function が存在する．

• 定理 n > 0 に対し，n+1 変数 universal function の への拡張は recursive ではない．

• 定理 に対し，次は同値：
  1. A はある recursive function の定義域
  2. A は空集合か，1 変数 PRF が存在して，

• • このとき A は enumerable であるという．

• 定理 に対し，f が recursive であることと f のグラフが enumerable であることは同値．