search
Prove the program correct
It is the era when software begins flying planes, and no amount of testing can cover the infinity of inputs a program will meet. You must verify that a flight-control routine can NEVER divide by zero or overflow — not for the cases you happened to try, but for every possible input, proven. Testing shows the presence of bugs, never their absence; you need a mathematical proof that the bad states are unreachable. Reason about the program's logic directly, with invariants and preconditions, establishing correctness for all inputs at once. Get it wrong and a corner case no tester imagined triggers in flight, with lives aboard — when a single failure is catastrophic, 'we tested it a lot' is no answer; only proof will do.
Who this problem belongs to
The two figures whose methods fit it best, out of 68 in contention.
This problem is essentially Hoare's life work stated as a scenario. His 1969 'An Axiomatic Basis for Computer Programming' introduced Hoare triples — precondition, program, postcondition — precisely the machinery for proving that a routine can never reach a bad state on any input. Absence of division by zero and overflow are exactly the kind of partial-correctness and safety assertions his logic was built to discharge: annotate the flight-control routine with invariants, prove each statement preserves them, and correctness for all inputs follows by induction over program structure rather than by enumeration of test cases. His later work on CSP and on the 'verifying compiler' grand challenge extended the same program. His Turing lecture line — make the design so simple there are obviously no deficiencies — is the safety-critical ethos this problem demands. The toolkit fits almost without translation.
Dijkstra is the source of this problem's central slogan: testing shows the presence of bugs, never their absence. His response was to make proof the primary act of programming — weakest-precondition calculus and predicate transformers (A Discipline of Programming, 1976) let you derive a program and its correctness proof together, computing exactly the condition under which a flight-control routine cannot overflow or divide by zero. His structured-programming campaign ('Go To Statement Considered Harmful,' 1968) existed precisely to make programs amenable to such reasoning, and THE's layered design showed the discipline scaling to a real operating system. If anything he would refuse the after-the-fact framing: one does not verify a finished program, one constructs a correct one. For establishing that bad states are unreachable for every input, his methods apply directly and completely.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
68 figures are scored on this problem. Draw it in a battle to see where you land.