計算可能関数
計算可能関数（けいさんかのうかんすう、）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。

計算可能関数の正確な定義が与えられる以前から、数学者は "effectively computable"（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。

チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。

ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。
Q818930
計算可能性理論
Concept
Q8366
アルゴリズム
Concept
Q163310
チューリングマシン
Concept
Q1930388
レジスタマシン
Concept
Q2651576
計算モデル
Concept
Q170790
数学者
Concept
Q205084
計算複雑性理論
Concept
Q309157
チャーチ＝チューリングのテーゼ
Concept
Q8366
アルゴリズム
Concept
Q4059945
ブラムの公理
UNK
Q205084
計算複雑性
Concept
Q906766
函数問題
UNK
Q1148456
計算可能関数
Concept
Q1148456
計算可能関数
Concept
Q1148456
計算可能関数
Concept
Q1148456
計算可能関数
Concept
Q1148456
計算可能関数
Concept
Q1148456
計算可能関数
Concept
Q1148456
計算可能関数
Concept
Q1148456
計算可能関数
Concept
subclass of
subclass of