Richardson's theorem

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 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. [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.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Richardson extrapolation — In numerical analysis, Richardson extrapolation is a sequence acceleration method, used to improve the rate of convergence of a sequence. It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century. [cite… …   Wikipedia

  • Curtis–Hedlund–Lyndon theorem — The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund …   Wikipedia

  • Noisy-channel coding theorem — In information theory, the noisy channel coding theorem (sometimes Shannon s theorem), establishes that for any given degree of noise contamination of a communication channel, it is possible to communicate discrete data (digital information)… …   Wikipedia

  • Cheng's eigenvalue comparison theorem — In Riemannian geometry, Cheng s eigenvalue comparison theorem states in general terms that when a domain is large, the first Dirichlet eigenvalue of its Laplace–Beltrami operator is small. This general characterization is not precise, in part… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Risch algorithm — The Risch algorithm, named after Robert H. Risch, is an algorithm for the calculus operation of indefinite integration (i.e. finding antiderivatives). The algorithm transforms the problem of integration into a problem in algebra. It is based on… …   Wikipedia

  • Constant problem — In mathematics, the constant problem is the problem of deciding if a given expression is equal to zero. Contents 1 The problem 2 Results 3 See also 4 References …   Wikipedia

  • Scientific phenomena named after people — This is a list of scientific phenomena and concepts named after people (eponymous phenomena). For other lists of eponyms, see eponym. NOTOC A* Abderhalden ninhydrin reaction Emil Abderhalden * Abney effect, Abney s law of additivity William de… …   Wikipedia

  • Liste von Physikern — Die Liste von Physikern ist alphabetisch sortiert und enthält nur Forscher, die wesentliche Beiträge zum Fachgebiet geleistet haben. Die Liste soll neben den Lebensdaten das Fachgebiet des Forschers nennen und wenige Stichworte zu den Aspekten… …   Deutsch Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”