|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計算 ： [けいさん] 1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast ・ 可 ： [か] 1. (n,n-suf) passable ・ 可能 ： [かのう] 1. (adj-na,n) possible 2. practicable 3. feasible ・ 能 ： [よく, のう] 1. (adv,n,vs) being skilled in 2. nicely 3. properly 4. well 5. skillfully 6. thoroughly ・ 関 ： [せき, ぜき] (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
計算可能関数（けいさんかのうかんすう、）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は ''effectively computable''（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。 == 定義 == 計算可能関数は、自然数についての部分関数である。計算可能関数 は引数として固定個の自然数をとり、個々の計算可能関数によって引数の個数は異なる。部分関数なので、あらゆる入力の組合せについて定義されているとは限らない。計算可能関数は出力として1つの自然数を返す（この出力を対関数を使って自然数のリストに変換することもできる）。 と記した場合、引数 についての部分関数を表し、 と記した場合、 が引数 について定義されていて返す値が であることを示している。これらの関数を部分再帰関数（Partial recursive function）と呼ぶ。再帰理論では、関数の定義域はその関数が定義されているあらゆる入力の集合とされる。 全ての引数について定義されている関数を全域関数と呼ぶ。計算可能関数のうち全域関数であるものを全域計算可能関数（Total computable function）または全域再帰関数（Total recursive function）と呼ぶ。 計算可能関数のクラスを定義する等価な方法がいくつも存在する。以下では、チューリングマシンで計算される部分関数として定義された計算可能関数を扱うものとする。同等の計算可能関数のクラスを定義する等価な計算模型はいくつもある。以下に一部を列挙する。 * チューリングマシン * μ再帰関数 * ラムダ計算 * コンビネータ論理 * タグシステム - ポストマシンとも * レジスタマシン 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「計算可能関数」の詳細全文を読む スポンサード リンク
|