Loading article…
論理学、数学、コンピュータサイエンス、特にメタ論理と計算可能性理論において、効果的な方法[1]または効果的な手順とは、特定のクラスからの直感的に「効果的な」手段によって問題を解決する手順です。[2]効果的な方法は、機械的な方法または手順と呼ばれることもあります。[3]
意味
効果的な方法の定義には、方法そのもの以上のものが含まれます。方法が効果的であると判断されるためには、問題のクラスに関して考慮されなければなりません。このため、ある方法は、あるクラスの問題に対しては効果的でも、別のクラスの問題に対しては効果的でない場合 があります。
ある方法が、以下の基準を満たす場合、その方法は正式には一連の問題に対して効果的であるといわれます。
- 有限の数の正確で有限の命令で構成されます。
- クラスの問題に適用すると次のようになります。
- 有限数のステップの後に必ず終了します。
- 常に正しい答えを出します。
- 原理的には、筆記用具以外の補助なしに人間が行うことができます。
- 成功するには、その指示に厳密に従うだけでよい。言い換えれば、成功するために創意工夫は必要ない。[4]
オプションとして、メソッドがそのクラスの外部から問題に適用されたときに、メソッドが答えであるかのように結果を返さないことも要求される場合があります。この要件を追加すると、有効なメソッドが存在するクラスのセットが削減されます。
アルゴリズム
関数の値を計算するための効果的な方法はアルゴリズムです。効果的な方法が存在する関数は、効果的に計算可能であると呼ばれることもあります。
計算可能な関数
実効計算可能性の形式的な特徴付けを行うためのいくつかの独立した取り組みにより、さまざまな定義（一般再帰関数、チューリングマシン、λ計算）が提案され、後にそれらは同等であることが示されました。これらの定義によって捉えられる概念は、再帰的計算可能性または実効計算可能性として知られています。
チャーチ＝チューリングのテーゼは、 2つの概念が一致することを述べています。つまり、効果的に計算可能な任意の数論的関数は、再帰的に計算可能であるということです。これは数学的なステートメントではないため、数学的な証明によって証明することはできません。[要出典]
参照
参考文献
- ^ ハンター、ジェフリー、メタロジック：標準一階述語論理のメタ理論入門、カリフォルニア大学出版、1971年
- ^ ガンディ、ロビン (1980)。「チャーチのテーゼとメカニズムの原理」。クリーネシンポジウム。論理学と数学の基礎研究。101 : 123–148。doi :10.1016/S0049-237X(08) 71257-6。ISBN 978-0-444-85345-5. 2024年4月19日閲覧。
- ^ Copeland, BJ ; Copeland, Jack; Proudfoot, Diane (2000 年 6 月)。「チューリング・チャーチのテーゼ」。AlanTuring.net 。コンピューティングの歴史に関するチューリング アーカイブ。2013年3 月 23 日閲覧。
- ^ ケンブリッジ哲学辞典、効果的な手順
- SC Kleene (1967)、「数学的論理学」。再版、Dover、2002年、ISBN 0-486-42533-9、233ページ以降、特に231ページ。