In mathematics, Richardson's theorem establishes a limit on the extent to which an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 can decide

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

 whether certain mathematical expressions are equal. It states that for a certain fairly natural class of expressions, it is undecidable

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....

 whether a particular expression E satisfies the equation E = 0, and similarly undecidable whether the functions defined by expressions E and F are everywhere equal. It was proved in 1968 by computer scientist Daniel Richardson of the University of Bath

University of Bath

The University of Bath is a campus university located in Bath, United Kingdom. It received its Royal Charter in 1966....

.

Specifically, the class of expressions for which the theorem holds is that generated by rational numbers, the number π

Pi

' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...

, the number log 2

Natural logarithm

The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...

, the variable x, the operations of addition, subtraction, multiplication, composition

Function composition

In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...

, and the sin

Sine

In mathematics, the sine function is a function of an angle. In a right triangle, sine gives the ratio of the length of the side opposite to an angle to the length of the hypotenuse.Sine is usually listed first amongst the trigonometric functions....

, exp

Exponential function

In mathematics, the exponential function is the function ex, where e is the number such that the function ex is its own derivative. The exponential function is used to model a relationship in which a constant change in the independent variable gives the same proportional change In mathematics,...

, and abs

Absolute value

In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...

functions.

For some classes of expressions (generated by other primitives than in Richardson's theorem) there exist algorithms that can determine whether expression is zero or not.

Calculation

The Richardson’s theorem can be calculated as follows
Let be E a set of real functions such that, if A(x), B(x) ∈ E, then A(x) ± B(x), A(x)B(x), A(B(x)) ∈ E.
The rational numbers are contained as constant functions. Then for expressions A(x) in E,

• if log 2, π, e^x, sin x ∈ E, then A(x) ≥ 0 for all x is unsolvable;
• if also ∈ E then A(x) = 0 is unsolvable.

If furthermore there is a function B(x) ∈ E without primitive in E then the integration problem is unsolvable. Example: exp(x²).