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, π, 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}$).

Référence

L'article de Richardson sur JStor