Richardson's theorem

From Wikipedia, the free encyclopedia

In mathematics, Richardson's theorem establishes a limit on the extent to which mathematics can demonstrate that certain expressions are equal. It states that for a certain fairly natural class of expressions, it is undecidable 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.

Specifically, the class of expressions for which the theorem holds is that generated by rational numbers, the number π, the number ln 2, the variable x, the operations of addition, subtraction, multiplication, and composition, and the sin(), exp(), and abs() functions.

It was proved in 1968 by computer scientist Daniel Richardson of the University of Bath.

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.[1][2]

See also: "A counterexample to a generalization of Richardson's theorem" by A. Sánchez-Flores [3]