Understanding Richardson's Theorem

56 Views Asked by At

Richardson's Theorem states that (quoting from Wolfram MathWorld):

Let $\mathcal{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 \mathcal{R}$, the predicate "$E=0$" is recursively undecidable.

I'm not sure if I understand this correctly. It seems that I can select for example:

  • $\sin(x) \in \mathcal{R}$
  • $1 - \sin(x)^2 - \cos(x)^2 \in \mathcal{R}$

For the first choice, it is clear that $E\equiv 0$ is false while for the second choice, it is clear that $E\equiv 0$ is true. Both expressions are contained in the set $\mathcal{R}$, so I don't understand how the theorem can state that these are undecidable.