翻訳と辞書
Words near each other
・ 原始元 (体論)
・ 原始元 (有限体)
・ 原始元の定理
・ 原始元定理
・ 原始共同
・ 原始共同体
・ 原始共産主義
・ 原始共産制
・ 原始再帰的
・ 原始再帰的関数
原始再帰関数
・ 原始函数
・ 原始動物
・ 原始卵胞
・ 原始卵黄嚢
・ 原始反射
・ 原始取得
・ 原始口唇
・ 原始口腔
・ 原始咽頭


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

原始再帰関数 : ミニ英和和英辞書
原始再帰関数[げんしさいきかんすう]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [はら, もと]
  1. (n,n-suf,n-t) (1) origin 2. basis 3. foundation
原始 : [げんし]
 【名詞】 1. origin 2. primeval 
: [さい]
  1. (pref) re- 2. again 3. repeated 
再帰 : [さいき]
 (n) recursive
: [せき, ぜき]
 (suf) honorific added to names of makuuchi and juryo division sumo wrestlers
関数 : [かんすう]
 (n) function (e.g., math, programming, programing)
: [すう, かず]
  1. (n,n-suf) number 2. figure 

原始再帰関数 : ウィキペディア日本語版
原始再帰関数[げんしさいきかんすう]
原始再帰関数(げんしさいきかんすう、)とは、原始再帰合成で定義される関数であり、再帰関数(計算可能関数)の部分集合である。原始帰納的関数とも。
再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。
数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法除法階乗指数、''n'' 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている(限界の節を参照)。
計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。
原始再帰関数のクラスはwhileプログラムでwhileループを使用せずに計算できる(すなわちloopプログラムで計算可能な)関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。
== 定義 ==
原始再帰関数は数論的関数(定義域と値域が自然数、つまり負でない整数 であるような関数)である。''n'' 個の引数をとる関数を ''n'' 項関数 (''n''-ary:-ary はアリティすなわち引数の個数を意味する) と呼ぶ。基本的な原始再帰関数は以下のような公理で与えられる:
#定数関数 (Constant Function) : 0 項の定数関数 0 〔つまり、0 項関数とは自然数のことであると取り決める。〕は原始再帰的である。
#後者関数(Successor Function): 1 項 の後者関数 ''S'' とは、引数の後者 (successor) を返す関数であり(ペアノの公理)、原始再帰的である。すなわち、''S'' (k) = k + 1.
#射影関数(Projection Function): ''n'' ≥ 1 の任意の ''n'' について、1 ≤ ''i'' ≤ ''n'' であるような各 ''i'' についての ''n'' 項射影関数 ''P''''i''''n''(''i'' 番目の引数を返す関数)は原始再帰的である。
より複雑な原始再帰関数は、以下の公理で与えられる作用素を適用することで得られる:
#合成 (Composition) : ''k'' 項原始再帰関数 ''f'' と ''k'' 個の ''m'' 項原始再帰関数 ''g''1, ..., ''g''''k'' について、''f'' と ''g''1, ..., ''g''''k''合成関数、すなわち ''m'' 項関数 ''h''(''x''1, ..., ''x''''m'') = ''f''(''g''1(''x''1, ..., ''x''''m''), ..., ''g''''k''(''x''1, ..., ''x''''m'')) は原始再帰的である。
#原始再帰 (Primitive Recursion) : ''k'' 項原始再帰関数 ''f'' と (''k'' + 2) 項原始再帰関数 ''g'' について、''f'' と ''g'' の原始再帰として定義される (''k'' + 1) 項関数、すなわち、''h''(0, ''x''1, ..., ''x''''k'') = ''f''(''x''1, ..., ''x''''k'') 、 ''h''(''S''(''n''), ''x''1, ..., ''x''''k'') = ''g''(''h''(''n'', ''x''1, ..., ''x''''k''), ''n'', ''x''1, ..., ''x''''k'') であるような関数 ''h'' は原始再帰的である。
上述の基本的な関数と、それに上述の作用素を有限回適用して得られる関数だけが原始再帰的関数である。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「原始再帰関数」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.