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$
1
  • $\begingroup$ That depends on some things, but mainly on what whoever is reading the proof expects. $\endgroup$
    – Git Gud
    Aug 15, 2013 at 14:31

4 Answers 4

3
$\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$
1
  • $\begingroup$ Hi @Ixer, when encountering some algorithms in proofs, then the best way is to translate this algorithm in something more formal (e.g. translate loops into sequences) in order to obtain a very formal proof ? (Given the fact I want to write some formal mathematical proofs). $\endgroup$ Dec 4, 2020 at 14:20
2
$\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$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .