確定一個遞歸函數是否收斂

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)

上述功能收斂。

我想知道你將如何靜態確定遞歸函數是否收斂。

這是一個好東西，你沒有指定一種語言，並暗示你正在考慮無限的整數，因爲這意味着我可以指出你作爲一個Web應用程序可用的this prototype analyzer for a toy language。

無限的整數，rici是對的，這是停滯的問題。然而，靜態分析儀解決的大多數其他問題也等同於暫停問題。這並不妨礙所討論的靜態分析儀的有用性。他們通過接受假陰性，假陽性或兩者兼顧來解決不確定性問題。

如果您更喜歡使用C語法語法，也可以使用Frama-C的值分析來確定whether a simple C program terminates。此分析器不處理遞歸函數，並將整數類型視爲有界（它們是）。有界整數類型使問題在理論上更容易（對於輸入語言的某些定義，它變得可確定），但在實踐中仍然很難。

2013-01-21 03:01:49

你不能在一般情況下。這個問題恰恰是halting problem。

這裏是一個遞歸函數，它可能終止了一切積極投入，寫成尾遞歸風格的一個簡單的例子（這將暫停一切積極n斷言是Collatz conjecture）：

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-21 02:43:34 rici

回答