General impossibility of an exhaustive test

Example 1

The following example is an adaptation of the one provided by Dijkstra [14] in "On the reliability of mechanisms", where he demonstrates the general impossibility of an exhaustive test and states the famous corollary: Software testing can only be used to show the presence of bugs, but never to show their absence!.

Consider a simple Java method which takes two arguments of primitive double type, each one 64 bits long. This method has a clear finite input domain with 2^128 elements (2^64 ∗ 2^64 ), considering all possible combinations. Suppose we are running this method in a machine capable of performing 2^40 instructions per second. In this machine, which represents the current processor speed, this method will take (2^128/2^40 = 2^88 ≈ 10^26 ) seconds to be completed. Since one year corresponds to approximately 10^7 seconds, it will be finished on 10^26 / 10^7 = 10^19 years, clearly an infeasible deadline.


  • <bib>vincenzi-etal:2007</bib>

Example 2

Consider a Java compiler --­ the number of potential inputs to the compiler is not just all Java programs, or even all almost correct Java programs, but all strings. The only limitation is the size of the file that can be read by the parser. Therefore, the number of inputs is effectively infinite and cannot be explicitly enumerated.