2
$\begingroup$

Can we prove a statement by providing an algorithm that is true for all conditions of the statement? Or do we need to prove the validity of the algorithm too?

As an example, suppose we need to prove that each number $n$ can be written as $2^km$ for integers $k, m$, such that $k$ is as large as possible.

We can state an algorithm that will take an integer $n$ and return $k, m$. Let $S = 0$

  1. If $n$ is even, add $1$ to $S$ and set $n$ equal to $\frac{n}{2}$. Else, $m = n$ and $k = S$ and exit.

  2. Repeat from step 1.

This algorithm will always give us valid values for any integer $n$. It can be seen that the algorithm will exit since $n$ is monotonically decreasing and can only take finite integral values.

For the proof of the statement, is it required to prove the validity of the algorithm?

$\endgroup$
  • $\begingroup$ That depends on some things, but mainly on what whoever is reading the proof expects. $\endgroup$ – Git Gud Aug 15 '13 at 14:31
1
$\begingroup$

Typically, such proofs will be phrased with some kind of well-ordering. For example, your proof could go:

Assume there are counter-examples. Since they are natural numbers, there is a smallest one, call it $S$. $S$ can't be odd, or it is $2^0\cdot S$. So $S$ is even. Consider $S/2$. Since it's smaller, it can't be a counter-example. $S/2 = 2^k m$ for some $k$,$m$. Thus, $S = 2^{k+1} m$, and it isn't a counter-example. Contradiction. Our only assumption was that there were counter-examples. Thus, there are no counter-examples.

However, if there isn't a nice way to put it in terms of well-ordering, one should prove the algorithm terminates at some point.

$\endgroup$
1
$\begingroup$

You need to prove that the algorithm terminates (it does not terminate if we feed it $n=0$, and indeed for $n=0$ the original claim is also false). And you need to prove that the output your algorithm produces is an answer to the problem (that is, why is $2^km$ the original $n$? And why is $k$ as large as possible?)

$\endgroup$
1
$\begingroup$

An algorithm represents an statement but the results produced by the algorithm can't proof the statement. You must to demonstrate using logical statements propositions and/or predicates that your algorithm fits with the statement the, so may be simpler if you proof directly the statement.

$\endgroup$
0
$\begingroup$

If the validity of the algorithm is not immediately obvious, then yes, it would be advisable to prove it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.