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 , , 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 ).

Référence

(en) Daniel Richardson, « Some undecidable problems involving elementary functions of a real variable », J. Symb. Logic, vol. 33, no 4, , p. 514-520 (JSTOR 2271358)

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.