終了関数定義（アルゴリズム）

Question

終了関数の定義に関する質問。

私たちは入力の計算のために比較的簡単な関数を持っています。入力のloglog2 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 

そして、いくつかの終了関数μ（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ための要件μ（S）= 1が存在しないことに注意してください。）

問題をμ（R、N）を選択して= N + Rはため、N = 2、我々は

• Nも
• 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) 

のでμは厳密には減少しないを持っていると思います。