Loading article…
メタ論理、数理論理学、計算可能性理論において、有効な方法[ 1 ]または有効な手順とは、特定のクラスの問題を解決するための有限時間で決定論的な手順のことである[ 2 ] [ 3 ]。有効な方法は、機械的方法または手順とも呼ばれることがある[ 4 ] 。有効な方法が存在する関数は、有効に計算可能であるとも呼ばれることがある。
正式には、ある手法が特定の問題群に対して有効であるとは、以下の基準を満たす場合をいう。
オプションとして、メソッドがクラス外から問題に適用された場合、メソッドが結果を解答として返さないことを要求することもできます。この要件を追加すると、有効なメソッドが存在するクラスのセットが縮小されます。
関数の値を計算するための効果的な方法を「アルゴリズム」と呼びます。
有効計算可能性を形式的に特徴づけようとする複数の独立した試みにより、様々な定義（一般再帰関数、チューリングマシン、λ計算など）が提案され、後にそれらが等価であることが示された。これらの定義によって捉えられる概念は、再帰的計算可能性または有効計算可能性として知られている。
チャーチ＝チューリングのテーゼは、この2つの概念が一致すると述べている。すなわち、効果的に計算可能な数論的関数はすべて再帰的に計算可能である。