Théorème de Richardson

En mathématiques, le théorème de Richardson, datant de 1968, porte sur la possibilité de simplifier les expressions. Plus précisément, soit un ensemble E d'expressions représentant des fonctions d'une variable réelle, et E^* l'ensemble des fonctions ainsi représentées, le problème consiste à déterminer si partant d'une expression dans E on est ou non en mesure de déterminer si la fonction associée est la fonction constante nulle. Richardson montre que ce problème est indécidable sous les conditions suivantes :

1. E^* contient l'identité, les nombres rationnels (en tant que fonctions constantes), est stable par addition, soustraction, produit et composition, contient les constantes $\ln 2$, $\pi$, la fonction sinus, la fonction exponentielle, et la fonction valeur absolue.
2. A et B étant deux éléments de E donnés, on peut trouver (de manière effective) dans E des expressions représentant la somme, la différence, le produit et la composée des deux fonctions représentées par A et B.

Richardson démontre dans le même article l'indécidabilité de ce qu'il appelle le « problème d'intégration » (integration problem), à savoir, un élément A de E étant donné, déterminer s'il existe une fonction f dans E^* dont la dérivée soit égale à la fonction déterminée par A, sous la condition supplémentaire qu'il existe dans E^* une fonction définie sur R entier et n'admettant de primitive dans E^* sur aucun intervalle (par exemple la fonction $x\mapsto e^{x^2}$).