6

再帰を学習しているときに、すべての整数引数 n <= 101 に対して値 91 を返し、n > 101 に対して n - 10 を返す McCarthy 91 関数に出くわしました。

 int McCarthy(int n)
 {
   if (n > 100)
     return n - 10;
   return McCarthy(McCarthy(n+11));
 }

int main()
{
  printf(" %d ", McCarthy(45));
  return 0;
}

コンピュータサイエンスにおけるその重要性を知りたいだけでしたか? ウィキペディアの記事によると、正式な検証のテストケースとして使用されています。どういう意味ですか。？

誰かが私のためにその使用法を簡素化できますか?

4

1 に答える 1

8

あなたが書いたようなプログラムを受け入れ、実行可能なコードを生成する C コンパイラを書いていると想像してください。コンパイラが正しく動作することをテストしたいとします。作成した関数の再帰的定義であるテスト ケースを作成し、コンパイルされたコードを実行すると、簡単に計算できる結果が得られることをアサートします (この場合、プログラムは 91 を出力するはずです)。このような難しいテスト ケースは、再帰呼び出しをコンパイルするための最適化を書き始めている場合に特に役立ちます。

コンパイラを書く代わりに、数学の授業で書くように、証明を書こうとするプログラムを書いていると想像してください。プログラムへの入力は、証明を書くために使用する代数法則のような一連の変換と、プログラムが証明しようとするステートメントである可能性があります。コンピューター サイエンスのこの分野は、正式な検証と呼ばれます。McCarthy 91 関数を含むステートメントを証明することは困難です。たとえば (すべての x <= 100 に対して、M(x) == 91) を証明するのは非常に困難です。これは、プルーフ ライティング プログラムとトランスフォーメーションでプルーフを生成するのが非常に難しい問題です。

于 2013-08-12T17:20:02.350 に答える