Skip to main content
3 of 4
Oops, adding a "computable"
Henry Cohn
  • 16.8k
  • 2
  • 74
  • 77

In full generality, there provably isn't any method for complete simplification (i.e., bringing an expression into a canonical simplest form). Simplifying should have two key properties: it should be algorithmic, and simplifying two different expressions for the same thing should give the same simplified form. If you have a simplification method with these properties, then it gives an algorithm for deciding whether two expressions are equivalent. However, Richardson proved that there is no algorithm to decide whether two closed-form expressions define the same function. (Of course you have to specify what you consider "closed-form". See D. Richardson, Some Undecidable Problems Involving Elementary Functions of a Real Variable, Journal of Symbolic Logic 33 (1968), 514-520, http://www.jstor.org/stable/2271358.)

Of course simplifying becomes easy if you give up on these properties. If you don't care about algorithms, just choose a representative for each equivalence class arbitrarily and declare it simplified. If you don't care whether equivalent expressions simplify to the same result, then just declare everything is already simplified.

This argument rules out only a very general notion of simplification. It still makes sense in many important special cases, and as Joel David Hamkins observes in the comments, one could still define a notion of simplicity even if there is no full simplification method.

Added in response to comments: Let's state things more precisely. Let the class $E$ of closed-form expressions contain $\log 2$, $\pi$, $e^x$, $\sin x$, and $|x|$ and be closed under addition, subtraction, multiplication, and composition of functions. These expressions all define continuous functions that are numerically computable (in the sense that one can algorithmically compute arbitrarily close approximations to their values at any given points). Call expressions $e_1$ and $e_2$ equivalent if they define the same function.

Richardson proved that there is no algorithm that can test whether two expressions in $E$ are equivalent. It follows immediately that no algorithm can bring elements of $E$ into any canonical form. I.e., there is no computable function $f$ from $E$ to $E$ such that $f(e_1)=f(e_2)$ iff $e_1$ and $e_2$ are equivalent.

Furthermore, one cannot even do it in the gradual sense described in the comments: there is no computable function $f$ from $\mathbb{N} \times E$ to $E$ with the property that expressions $e_1$ and $e_2$ define the same function iff $f(n,e_1)=f(n,e_2)$ for all sufficiently large $n$. Think of $n$ as describing how hard you have tried to simplify your input, with the idea being that you eventually reach the canonical simplest form when $n$ is large enough, but you won't know when you've reached it (so you'll always be left wondering whether increasing $n$ would lead to further simplifications).

This observation requires a different proof, but it is not difficult. If such an $f$ existed, you could computably enumerate all the equivalent pairs $(e_1,e_2)$: to do so, loop through all triples $(e_1,e_2,n) \in E \times E \times \mathbb{N}$ and output $(e_1,e_2)$ whenever $f(n,e_1)=f(n,e_2)$. However, it is easy to computably enumerate the inequivalent pairs: loop through all expressions $e_1$ and $e_2$, rational numbers $x$, and natural numbers $k$, and output $(e_1,e_2)$ if numerically computing the corresponding functions at $x$ to within error less than $1/k$ shows that these functions differ at $x$. All inequivalent pairs will occur in this list, so if we could separately enumerate all the equivalent pairs (using the magic simplification function $f$), then we could solve the equivalence problem by seeing which list $(e_1,e_2)$ turned up in. That would contradict Richardson's theorem, and consequently $f$ does not exist.

What makes this tricky is that it's tempting to think the equivalent pairs should be computably enumerable. Can't you write down a list of all the expressions equivalent to $e$ by manipulating $e$ in all possible ways? Richardson's theorem implies that you cannot (for example, high school algebra manipulations are insufficient to get all equivalences, so high school classes give entirely the wrong impression). Proving two functions are different is easy, but proving two functions are the same is not, and there is no systematic way to do it.

Henry Cohn
  • 16.8k
  • 2
  • 74
  • 77