Testing Versus Proving Program Behavior

Many beginners believe that once a program has been shown to be correct, the job is finished and the program can be trusted to do what its users need. The belief sounds reasonable, but it quietly merges two different questions. The first question is whether the program does what it was asked to do. The second is whether what it was asked to do was the right thing in the first place. This article separates those questions, because the difference decides what a correctness proof can and cannot give you.

In some cases it is possible to demonstrate, mathematically, that the sequence of computations a program describes will always produce the correct result. This is the sense in which a program can be provably correct. The proof reasons about every possible run of the program, not just the few runs someone happened to try. That is what makes it stronger than testing alone.

Think of the specification as the target and the program as the thing being aimed. A program is provably correct when a proof shows that, for every possible run, the final result hits the target. The specification sits outside the program. The program can be faithful to every step it takes and still miss the target if the target was set wrongly.

The reasoning behind correctness proofs rests on two ideas: process and state. The state of a program is all the information relevant at one moment. A process is the sequence of states the computer passes through during execution. Each statement that runs moves the computation from one state to the next, so a run of a program is a chain of states.

The meaning of a statement can be expressed as its effect on the computer's state. This matters because that effect is a fact you can rely on when building a proof. To reason about a statement, ask two things: what changes in the state after the statement runs, and what stays the same. Everything the statement does not touch carries over unchanged from before to after.

The diagram shows the pattern. Only x changes, because the statement assigns to x. The value of y is the same before and after. A proof chains together facts like this one, each describing how a single statement moves the state, until it can say what the final state of every run must be.

Testing checks a program on some runs. Proving reasons about every possible run. The contrast is about coverage. A set of tests can show that a program behaves correctly on the cases tested, but the tests are only a sample. A proof is an argument about all runs at once, which is why it is stronger than testing alone.

Rigorous proof is genuinely hard. In practice, full mathematical proofs of correctness are typically limited to fairly small programs. The reason is the same one that makes proving stronger than testing: the proof must account for every possible run, and the reasoning has to be carried through each statement's effect on state until the final result is shown to match the specification.

This does not make the ideas useless for larger work. Even in everyday programming, the ideas and techniques used in correctness proofs can guide how you reason about code, even when you never write a formal proof. Asking what state a statement starts from, what it changes, and what result the specification demands are useful habits at any scale.

A correctness proof establishes that the program matches its specification. It does not establish that the specification describes what users need. A proof of correctness is only as trustworthy as the specification it relies on, and a correct program can still be useless if its specification is wrong. The program may be perfectly faithful to its process and states while the specification remains the weak point.