Определение функции терминации (алгоритмы)

Question

Вопрос об определении функций терминации.

У нас есть относительно простая функция для вычисления ⌊log₂ n⌋ ввода.

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 

И мы спросили, являются ли некоторые функции терминации μ (г, п) являются правильными.

• μ (г, п) = п правильно: функция в конечное условие, когда п = 1, так как в этой точке г = ⌊log₂ n₀⌋.

• Однако μ (r, n) = 2n + r, по-видимому, также является правильным.

• Кроме того, μ (г, п) = п + г неверен

Это было мое понимание того, что функция прекращения μ (г, п) была просто переменная, что прекращение функций зависело от (В этом случае n достигает 1,) поэтому почему 2n + r функция терминации?

Каково точное определение функции завершения μ (r, n) в этом контексте?

Answer 1

Функция завершения μ должна быть положительной для состояний, в которых вводится цикл, и строго уменьшается на каждой итерации. Это, а также хорошо упорядоченность натуральных чисел, гарантирует, что ваш цикл будет всегда заканчиваться. (Обратите внимание, что не существует требование, чтобы μ (s) = 1 для с, который выходит из цикла, так что она всегда уменьшается на одну итерацию.)

Проблема с выбором μ (R, N) = п + г является то, что для п = 2, мы имеем

• п даже
• п> 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) 

так μ строго не уменьшатся.