- Richardson's theorem
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 theUniversity 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. [http://portal.acm.org/citation.cfm?id=190429]
References
* cite book
last = Petkovšek
first = Marko
authorlink = Marko Petkovšek
coauthors =Herbert S. Wilf ,Doron Zeilberger
title = A=B
publisher =A. K. Peters
url = http://www.cis.upenn.edu/~wilf/AeqB.html
year = 1996
isbn =
pages = 5
* Citation
last= Richardson
first= Daniel
year= 1968
title=Some unsolvable problems involving elementary functions of a real variable
periodical=Journal of Symbolic Logic
volume=33
issue=4
pages=514–520
url=http://links.jstor.org/sici?sici=0022-4812%28196812%2933%3A4%3C514%3ASUPIEF%3E2.0.CO%3B2-H.External links
*See also: "A counterexample to a generalization of Richardson's theorem" by A. Sánchez-Flores [http://portal.acm.org/citation.cfm?id=29205.29217]
Wikimedia Foundation. 2010.