Posts Tagged ‘Dijkstra’

There is less than a 1% chance that your program is correct … program contains 500 components and each component has a 99% chance of being correct

September 28, 2013

As we build ever larger and more powerful systems it becomes ever more important that those systems, and the components of which they are made, should be transparently simple and self-evidently correct. As Professor Dijkstra points out (Structured Programming, Academic Press 1972):

                If the chance of correctness of an individual
                component equals p, the chance of correctness
                of a whole program, composed of N such
                components, is something like

                                P = pN

                As N will be very large, p should be very, very
                close to 1 if we desire P to differ significantly
                from zero!

The purpose of this book is to present a coherent method and procedure for designing systems, programs and components which are transparently simple and self-evidently correct.

                Principles of Program Design
                by M.A. Jackson

Example: Suppose the chance of correctness of an individual component is 99% (p=0.99) and the program is composed of 500 such components (N=500). The chance of correctness of the program is

                                P=(0.99)500
                                               
P = 0.007

There is less than a 1% chance that the program is correct!