0

何らかの関数f(簡単にするために 1 つの入力を受け取る) のコードがある場合、入力xが出力に影響するかどうかf(x)、つまり、f以下で定義される定数関数であるかどうかを判断する必要があります。

の出力がwrt に対して不変fである場合、定数関数であると定義します。これは、すべての入力に適用されます。したがって、たとえば、 がある場合、エラーを出力する可能性がある x = 0 を除くすべての入力に対して 0 を出力する可能性があります。定数関数ではありません。fxf(x) = 0 power xf

私はコードの静的分析しかできず、簡単にするためにコードが Java ソースであると想定しています。これは可能ですか？

4

3 に答える 3

1

これは明らかに、少なくとも停止問題を解くのと同じくらい難しい (証明は演習として残されています) ので、答えは「いいえ」です。これは不可能です。

于 2012-09-20T00:16:06.223 に答える
1

ほぼ確実に可能です。ほとんどの場合。おかしなことが起きていないところ。

通常の関数の場合、通常の便利な種類で、独自のささいなことを行うのではなく、実際に値を返します。

単純な関数で、再帰的ではなく、手動で行う場合、静的分析を符号チャートに相当するものにして、コードを調べて、境界条件である可能性のある x のすべての値を決定します。またはそのようなもの（たとえば、コードのif (x < 0)どこかにあるので、0に近いxの値について関数をチェックします）。この種の試みが失敗する運命にある場合は、何かに使用する前に教えてください.

ブルートフォースを使用してそれをすりつぶすことは、4倍の精度のx値または同様のサイズのものを使用しない限り、うまくいく可能性があります。ブルートフォースには何年もかかる可能性があるためです。その時点では、もはや静的分析ではありません。

静的分析とは一般に、コードを見てコンピューターに教えてもらうことを意味し、自分でコードを見るのではありません (少なくともそれほどではありません)。多くの言語でこれを行うためのアルゴリズムが存在します。ウィキペディアにはそのようなリストがあり、無料またはオープンソースのものもあります。何かができるという究極の証拠は、それがすでに行われているということです。

于 2012-09-20T00:26:00.503 に答える
0

非終了関数を非定数と呼ぶので、問題から停止問題への削減は次のとおりです。

void does_it_halt(...);

int f(int x) {
    if(x == 1) {
        does_it_halt();
    }
    return 0;
}

fis constant かどうかを尋ねることは、halts かどうかを尋ねることと同じですdoes_it_halt。したがって、停止問題は決定できないため、あなたが求めていることは不可能です。

于 2012-09-20T00:23:16.603 に答える