コトバンクはYahoo!辞書と技術提携しています。

帰納的関数 きのうてきかんすう

1件 の用語解説(帰納的関数の意味・用語解説を検索)

世界大百科事典 第2版の解説

きのうてきかんすう【帰納的関数】

〈実際effectiveに計算可能な関数〉に関する数学的概念であるリカーシブ関数recursive functionに対して,日本で定着している術語。1931年,K.ゲーデル原始帰納的関数として初めて定式化し,これを用いて不完全性定理の証明を得た。自然数{0,1,2,……}の上で定義され,自然数を値とする関数f(x1,……,xn)が, f(x)=x+1  ……(1)  f(x1,……,xn)=q (qは定数)  ……(2)  f(x1,……,xn)=xi (1≦in)  ……(3)  f(x1,……,xn)=g(h1(x1,……,xn),……,  hm(x1,……,xn))  ……(4)  (ここで,gm変数の関数で,g,h1,……,  hmはすでに与えられた関数) (ここで,g,hはすでに与えられた関数で,  n=1のときg( )は定数を表すものとする)を有限回適用して定義されるとき,原始帰納的関数primitive recursive functionという。

出典|株式会社日立ソリューションズ・クリエイト
All Rights Reserved. Copyright (C) 2015, Hitachi Solutions Create,Ltd. 収録データは1998年10月に編集製作されたものです。それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。また、本文中の図・表・イラストはご提供しておりません。

世界大百科事典内の帰納的関数の言及

【計算モデル】より

… RAMより計算できる関数と,チューリング機械によって計算できる関数と,ラムダ計算で計算できる関数はすべて同じであることを示すことができる。また,これは帰納的関数として定義できる関数であることを証明することができる。これらのことから,コンピューターにおいて計算するアルゴリズムが存在するという直観的な概念を,これらの計算モデルで計算できることとして定義してよいことがわかる。…

※「帰納的関数」について言及している用語解説の一部を掲載しています。

出典|株式会社日立ソリューションズ・クリエイト
All Rights Reserved. Copyright (C) 2015, Hitachi Solutions Create,Ltd. 収録データは1998年10月に編集製作されたものです。それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。また、本文中の図・表・イラストはご提供しておりません。

帰納的関数の関連キーワード関数論実際原価計算初等関数正則関数多価関数超越関数ラグランジュ関数複素関数チューリング機械有効需要(effective demand )

今日のキーワード

トランスアジア航空

台湾・台北市に本拠を置く航空会社。中国語名は復興航空。1951年、台湾初の民間航空会社として設立。83年に台湾の国産実業グループに経営移管され、組織改編を実施した。92年に国際チャーター便の運航を始め...

続きを読む

コトバンク for iPhone