Here is something else: provably correct code can demonstrate unacceptable complexity for some input cases. We know from the proof that it will halt and the result will be correct: in 200 years on the given hardware. You have to add a time bound as a requirement specification to avoid this, or a constraint on the complexity (e.g. &quot;the implementation must use no algorithm slower than quadratic time in such and such inputs&quot;).