3

TMが言語を認識し、受け入れ状態または拒否状態になった場合、言語は決定可能です。開発者として これは、プログラムにバッファオーバーフローまたはデッドロックが含まれているかどうかを判断できることを意味するため、重要だと思います。また、次の問題は決定不可能です。

  • プログラムが初期化されていない変数にアクセスすることはありますか？
  • 2つの文脈自由文法が同じ言語を記述していますか。
  • サブルーチンへのパラメーターが参照またはコピー結果によって渡される場合、違いはありますか？

決定可能性の観点から、決定可能性の重要なポイントは何と言いますか。また、決定可能性が（特に開発者にとって）重要である理由は何ですか。

注：箇条書きは回答に問題はありません。トピックは自分で調べることができます。要点を知りたいだけです。

4

2 に答える 2

3

おそらくこれはcstheory exchangeに属しますが、とにかくやってみます。

重要な点は、一部の問題は決定不能、つまりアルゴリズムでは解決できないため、他の方法で対処する必要があるということです。これらの問題の中には、コンピューター言語に関する多くの「メタ問題」があります。たとえば、ウイルスの検出の問題です。

問題が決定不能であると判断した場合、いくつかのアクション コースが考えられます。

  1. 一部の問題は半決定可能である場合があります。つまり、一部のケースを解決する半アルゴリズムがありますが、他のケースでは永久にループします。半アルゴリズムを実装するときは、タイマーを入れてno answer、時間切れになると戻ります。
  2. 問題を単純化することで、問題のごく一部の、できれば重要な部分だけを解決します。
  3. 2 + 問題が複雑になりすぎた場合、ユーザーに入力を求めます。
  4. ほとんどの場合正しい答えが得られるヒューリスティックを使用します。
  5. おそらく非チューリング完全言語など、別の言語を使用してください。

1 から 3 は、プログラム検証ツールを含む自動推論ツールで人気があります。4 はウイルス スキャナの機能です。5 は、大規模なシステムを自動化するスクリプトをユーザーが作成できるようにする場合に適しています。それらに完全な JavaScript/Scheme/Lua/その他のものを与える代わりに、無制限の再帰/ループを許可しない制限されたサブセットを与えます。

于 2010-10-17T12:52:50.547 に答える
0

「実行時に、関数が直接的または間接的に自分自身を呼び出すことはない」という条件を満たすソフトウェアを作成する必要があるとします。

その条件は決定不可能ですが、より制限的な条件は決定可能かもしれません。たとえば、「関数ポインターを使用してはならず、関数に直接的または間接的にそれ自体への呼び出しを含めないでください」などです。

これは、システムの特定の必要なプロパティが強制可能になるように、決定可能性と柔軟性を交換できる場合があることを強調するためです。

プログラミング言語が決定可能である場合、プログラムがその言語に対して有効なプログラムであるかどうかを常に決定できます。

しかし、あるプログラムがその言語に対して有効なプログラムであっても、そのプログラムがバッファー オーバーフローやデッドロックを引き起こす可能性があるかどうかは判断できません。

于 2015-08-19T23:59:47.633 に答える