info prev up next book cdrom email home

Richardson's Theorem

Let $R$ be the class of expressions generated by

1. The Rational Numbers and the two Real Numbers $\pi$ and $\ln 2$,

2. The variable $x$,

3. The operations of Addition, Multiplication, and composition, and

4. The Sine, Exponential, and Absolute Value functions.
Then if $E\in R$, the predicate ``$E=0$'' is recursively Undecidable.

See also Recursion, Undecidable


References

Caviness, B. F. ``On Canonical Forms and Simplification.'' J. Assoc. Comp. Mach. 17, 385-396, 1970.

Petkovsek, M.; Wilf, H. S.; and Zeilberger, D. A=B. Wellesley, MA: A. K. Peters, 1996.

Richardson, D. ``Some Unsolvable Problems Involving Elementary Functions of a Real Variable.'' J. Symbolic Logic 33, 514-520, 1968.




© 1996-9 Eric W. Weisstein
1999-05-25