Computableの定義？

Question

私は計算可能なものの「簡潔な」定義は何でしょうか？私は計算可能であるかどうか分からなくなってしまったので頼みます。それが停止した場合

にのみ計算可能なものですか？例えば

function foo(){ 
while(true); 
} 

計算ができないのは、決して停止しないからです。あるいは、計算可能な定義を停止問題と混同していますか？

ありがとうございました

Answer 1

何かが正式に計算可能です。

だから、計算可能で、コンピュータと、問題のではなく、コードの一部のプロパティです。勉強計算可能性の興味深い結果の

2：コンピューターの

• 特定のクラスは、それらの上に計算可能であるが、何についてで他のものより限られている（例えばチューリングマシンなど）にもいくつかの非常に単純なモデルすることができます計算方法を知っているすべてを計算します。
• いくつかの問題は、計算不可能であるか、または決定不能であることが判明する可能性があります。停止問題はこのような問題の1つです。

Answer 2

コンピューティビティは、プログラムの所有権ではありません。計算能力は数学的問題の性質であり、問​​題の各インスタンスに対して正しい答えを与えることで問題を効果的に解決するアルゴリズムが存在することを意味します。

（チューリング完全なプログラミング言語の）完全に解くアルゴリズムが存在することができないため、停止問題は計算可能ではないが、それは計算可能の定義はありません。特定の（多くの場合、純粋に理論的な）コンピュータの能力を与えられた、あなたは有限の時間でその問題を解決するアルゴリズムが存在することを示すことができ、場合