终止函数定义（算法）

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) 

所以μ并不严格下降。