Testing is an Unsolved Problem

State Space and Complexity

There is a big reason algorithms can’t logically prove that computer programs are correct, thanks to state spaces. Even a simple function such as one that takes a single number, adds one to it, and returns the result is difficult to prove correct.

Quick test code for f(x)
Simple Test code will run ‘forever’…

Formal Verification

While testing explores some of the possible scenarios and behaviors of a system, formal verification requires exhaustive exploration. Two types of formal verivication are:

  • Model Checking — using tools to verify if a model satisfies its specification.

Turing and the Halting Problem

Alan Turing, a pioneer in computer science, detailed the halting problem very early on. The halting problem shows we cannot prove that any program will actually ever finish executing, let alone give you the correct result.

Complexity and Chaos Theory

Chaos theory may sound like something from the movies or made up but it’s very real. The weather is a chaotic function of the inputs of temperature, pressure, humidity, etc. and we’ve all heard of that if a butterfly that flaps its wings it could cause a tornado. So software functions, especially ones that take or execute floating-point numbers, like pressure, humidity, with slight errors, or exhibit non-linearity (e.g. f(x) = e^x), are a huge problem from a testing perspective. This descriptions matches almost all code written.

What doest it mean?

If you feel overwhelmed as a manual/exploratory tester, you are in good company, and your intuition is correct. Algorithms can help — they are just not the complete story — testing will always need the human brain with its intuition, and experience. If you are a test automation engineer, realize that smartly permuting the inputs, and even attempts at auto-verification of test code without human review is folly. The answer is, as it always is — somewhere in the middle. Humans can’t verify the software on their own because they are too slow and expensive, but humans can do things that machines by definition can never do. The two need to work together and leverage each other's strengths. It is easy to develop a few lines, even millions of lines of code, the difficulty, and the most difficult engineering issue of the day is Software Testing, which is provably difficult.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
jason arbon

jason arbon


blending humans and machines. co-founder @testdotai eater of #tunamelts