原始再帰関数の例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/20 10:14 UTC 版)
以下の例と定義の典拠は Kleene (1952) pp. 223-231 である。類似の一覧は Boolos-Burgess-Jeffrey 2002 pp. 63-70 にもある。 以下の例で、原始再帰関数は4種類に分類される: 関数 (Function) - 数論的関数、つまり自然数から自然数への関数 述語 (Predicate) - 自然数から真理値への関数 命題結合子 (Propositional Connective) - 真理値から真理値への関数。ブール関数 表現関数 (Representing Function) - 真理値から自然数への関数。述語の値を 0 や 1 に変換するのは表現関数である。φ の値が 0 か 1 で P が真のとき 0 となるなら、関数 φ(x) は述語 P(x) の表現関数と定義される。 以下の例で、a' のような " ' " 記号付きの記号は後者 (successor) を意味し、一般に "+1" を表す。つまり、a +1 =def a' である。16から21番の関数と #G の関数は原始再帰関数とゲーデル数の数値表現の相互変換に関わるものである。 加算: a+b 乗算: a*b べき乗: ab, 階乗 a! : 0! = 1, a'! = a!*a' pred(a): デクリメント: 「a の前者」は " a>0 なら a-1 → anew 、そうでなければ 0 → a " と定義される 減算: a ∸ b の定義は " a ≥ b なら a-b, そうでなければ 0 " 最小 (a1, ... an) 最大 (a1, ... an) 絶対値: | a-b | =def a ∸ b + b ∸ a ~sg(a): NOT[signum(a}]: a=0 なら sg(a)=1 、そうでなく a>0 なら sg(a)=0 sg(a): signum(a): a=0 なら sg(a)=0 そうでなく a>0 なら sg(a)=1 剰余 (a, b): a が b で割り切れない場合の余り 除算 [ a | b ]: 剰余が 0 の場合。 s = b: sg | a - b | a < b: sg( a' ∸ b ) a | b: 除算 Pr(a): a は素数 Pr(a) =def a>1 & NOT(Exists c)1<c
※この「原始再帰関数の例」の解説は、「原始再帰関数」の解説の一部です。
「原始再帰関数の例」を含む「原始再帰関数」の記事については、「原始再帰関数」の概要を参照ください。
- 原始再帰関数の例のページへのリンク
