Inmathematics,Richardson's theorem establishes theundecidability of the equality ofreal numbers defined byexpressions involvingintegers,π,ln 2, andexponential andsine functions. It was proved in 1968 by the mathematician and computer scientist Daniel Richardson of theUniversity of Bath.

Specifically, the class of expressions for which the theorem holds is that generated by rational numbers, the numberπ, the numberln 2, the variablex, the operations of addition, subtraction, multiplication,composition, and thesin,exp, andabs functions.

For some classes of expressions generated by other primitives than in Richardson's theorem, there exist algorithms that can determine whether an expression is zero.^[1]

Richardson's theorem can be stated as follows:^[2] LetE be a set of expressions that represent${\displaystyle \mathbb{R}\to \mathbb{R}}$ functions. Suppose thatE includes these expressions:

• x (representing the identity function)
• e^x (representing the exponential functions)
• sinx (representing the sin function)
• all rational numbers, ln 2, and π (representing constant functions that ignore their input and produce the given number as output)

SupposeE is also closed under a few standard operations. Specifically, suppose that ifA andB are inE, then all of the following are also inE:

• A +B (representing the pointwise addition of the functions thatA andB represent)
• A −B (representing pointwise subtraction)
• AB (representing pointwise multiplication)
• A∘B (representing the composition of the functions represented byA andB)

Then the followingdecision problems are unsolvable:

• Deciding whether an expressionA inE represents a function that is nonnegative everywhere
• IfE includes also the expression |x| (representing the absolute value function), deciding whether an expressionA inE represents a function that is zero everywhere
• IfE includes an expressionB representing a function whoseantiderivative has no representative inE, deciding whether an expressionA inE represents a function whose antiderivative can be represented inE. (Example:${\displaystyle e^{a{x}^2}}$ has an antiderivative in theelementary functions if and only ifa = 0.)

AfterHilbert's tenth problem was solved in 1970, B. F. Caviness observed that the use ofe^x and ln 2 could be removed.^[3]Wang later noted that under the same assumptions under which the question of whether there wasx withA(x) < 0 was unsolvable, the question of whether there wasx withA(x) = 0 was also unsolvable.^[4]

Miklós Laczkovich removed also the need for π and reduced the use of composition.^[5] In particular, given an expressionA(x) in the ring generated by the integers,x, sinxⁿ, and sin(x sin xⁿ) (forn ranging over positive integers), both the question of whetherA(x) > 0 for somex and whetherA(x) = 0 for somex are unsolvable.

By contrast, theTarski–Seidenberg theorem says that the first-order theory of the real field is decidable, so it is not possible to remove the sine function entirely.

• Constant problem – Problem of deciding whether an expression equals zero
• Elementary function – Type of mathematical function
• Tarski's high school algebra problem – Mathematical problem

• Petkovšek, Marko;Wilf, Herbert S.;Zeilberger, Doron (1996).A = B.A. K. Peters. p. 212.ISBN 1-56881-063-6. Archived fromthe original on 2006-01-29.

• Weisstein, Eric W."Richardson's theorem".MathWorld.

• Undecidable problems
• Functions and mappings
• Theorems in the foundations of mathematics

• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata