1

次の再帰的階乗関数を考えてみましょう。

fact(n) =
    if (n = 0) return 1
    return n * fact(n - 1)

上記の関数は、ゼロを含むすべての正の整数に対して収束します。ただし、負の整数の場合は収束しません。

次に、次のプログラムについて考えてみます。

fact(n) =
    if (n < 0) return 0
    if (n = 0) return 1
    return n * fact(n - 1)

上記の関数は、すべての整数に対して収束します。

再帰関数が収束するかどうかを静的に判断する方法を知りたいと思いました。

4

2 に答える 2

3

一般的な場合、できません。その質問はまさに停止性問題です。

これは、末尾再帰スタイルで記述された、すべての正の入力で終了する可能性のある再帰関数の簡単な例です（すべての正で停止するという主張nは、コラッツの推測です）。

stop(n, a=0) =
  if (n == 1) return a
  if (n % 2 == 0) return stop(n / 2, a + 1)
  return stop(3 * n + 1, a + 1)
于 2013-01-21T02:43:34.653 に答える
1

言語を指定せず、無制限の整数を考えていることを暗示したのは良いことです。これは、Webアプリとして利用できるおもちゃの言語用のこのプロトタイプアナライザーを紹介できることを意味します。

無制限の整数では、riciは正しいです、これは停止性問題です。ただし、静的アナライザーによって解決される他のほとんどの問題も、停止問題と同等です。それは、問題の静的アナライザーの有用性を妨げるものではありません。それらは、偽陰性、偽陽性、またはその両方を持つことを受け入れることによって、決定不能性を回避します。

Cのような構文を使用したい場合は、Frama-Cの値分析を使用して、単純なCプログラムが終了するかどうかを判別することもできます。このアナライザーは再帰関数を処理せず、整数型を有界（それらがそうである）として扱います。制限付き整数型は、理論的には問題を容易にします（入力言語の一部の定義では、決定可能になります）が、実際にはそれでも困難です。

于 2013-01-21T03:01:49.123 に答える