終止函數定義（算法）

Question

有關終止函數定義的問題。

我們有一個相對簡單的函數來計算輸入的₂log2n⌋。

LOG2 
Configuration: {[r, n] | Integers r ≥ 0 and n ≥ 1} 
[r, n] -> [r + 1, n/2] if n > 1 ∧ n even 
[r, n] -> [r, n − 1] if n > 1 ∧ n odd 

而且我們問過一些終端功能μ（R，N）是否正確。

• μ（R，N）= N是正確的：該函數的結束條件是當n = 1的，如在該點R =⌊log₂n₀⌋。

• 然而，μ（r，n）= 2n + r顯然也是正確的。

• 此外，μ（R，N）= N + R是不正確

這是我的理解是，終端功能μ（R，N）只是變量，該函數終止依賴於（在這種情況下，n達到1），那麼爲什麼2n + r終止函數？

終止函數μ（r，n）在這方面的確切定義是什麼？

Answer 1

終止函數μ對於進入循環的狀態必須是正數，並且在每次迭代時嚴格遞減。那加上自然數的有序性，可以確保你的循環總是終止。 （請注意，存在用於小號即退出循環，只是它總是每次迭代減少不要求μ（S）= 1。）

問題與選擇μ（R，N）= N + R是，對於n = 2的，我們有

• ñ甚至
• n> 1時

等轉換[r, n] -> [r + 1, n/2]有效。然而，在這種情況下，我們不得不

μ(r',n') =   Definition of r' and n' 
μ(r+1,n/2) =  Definition of μ 
r + 1 + n/2 =  Rearrange via n = 2 
r + 2 = 
r + n =   Definition of μ 
μ(r, n) 

所以μ並不嚴格下降。