0

The given recursive algorithm is as follows:

If an algorithm $P$ has one argument $n$ of type natural, it terminates when called with the argument $0$. When called with an argument $x > 0$, it terminates, except possibly for a call to itself with argument $y$, with $y < x$.

The statement: Such algorithm eventually terminates for all input.

I am supposed to prove the validity of this rule by using a strong induction.

So, to begin, I believe I am supposed to use $P(0)$ as the base case. But I am having trouble understanding what am I supposed to be proving from $P(0)$. Is it just the given information that $P(0)$ terminates?

Community
  • 1
user2898453
  • 1

1 Answers1

0

The base case: Does the algorithm terminate when called for $x = 0$, i.e., does $P(0)$ terminate?

What happens when called for $x = 0$? The algorithm "terminates when called with argument $0$" (quote from your text), so the algorithm terminates for $x = 0$.

The Assumption: The algorithm terminates when called for any argument strictly less than some $x > 0$, i.e., $P(y)$ terminates for all $y < x$.

The inductive step: Does the algorithm terminate when called for $x$ (the same $x > 0$ from the assumption), i.e., does $P(x)$ terminate?

As written in the text above, "when called with argument $x > 0$, it terminates except possibly for a call to itself with argument $y$, with $y < x$".

So, we have two possible cases:

  1. $P(x)$ terminates right away; or

  2. $P(x)$ calls $P(y)$ for some $y < x$. What can we conclude in this case?

This is all but finished, so I'll let you do that little step yourself. If you have questions, please ask.

Vedran Šego
  • 11,372