Décidabilité de la vérification d'un antidérivatif?

9

Supposons que j'ai deux fonctions et et je souhaite déterminer si $F$ $G$

F (X) = \int g (X) ré X .

$F(x) = \int G(x)dx.$

Supposons que mes fonctions soient composées de fonctions élémentaires (polynômes, exponentielles, logs et fonctions trigonométriques), mais pas, disons, série Taylor.

Ce problème est-il décidable? Sinon, est-ce semi-décidable?

(Je demande parce que j'enseigne une classe sur la calculabilité et un étudiant m'a demandé si une MT pourrait vous aider à intégrer une fonction dont l'intégrale n'était pas connue actuellement. Je soupçonne que les fonctions que nous ne savons pas intégrer sont plus correctement des fonctions dont l'intégrale ne peut pas être exprimée comme une combinaison des fonctions élémentaires ci-dessus plutôt que des fonctions pour lesquelles nous ne connaissons pas réellement l'intégrale, mais cela m'a amené à me demander si le problème général de la vérification des intégrales était décidable.)

computability undecidability mathematical-analysis computer-algebra templatetypedef
la source

Vous semblez poser des questions sur la différenciation symbolique. Vous pouvez jeter un œil à en.wikipedia.org/wiki/Symbolic_computation et en.wikipedia.org/wiki/Computer_algebra_system . Je ne sais pas quelle classe de fonctions vous autorisez. Quels types de composition autorisez-vous? par exemple, autorisé? Je vous suggère d'essayer de formaliser la classe de fonctions qui vous intéresse en utilisant une définition récursive. Avez-vous essayé de voir ce qui se passe lorsque vous utilisez la règle de chaîne et de voir si vous pouvez obtenir un algorithme récursif qui gère tous les cas?

F (x) = \sin (\cos (e^{x})) + \log (2 x^{3} + 3)

$F(x)=\sin(\cos(e^x)) + \log(2x^3+3)$

DW

3

Puisque la différenciation est facile, vous vous demandez vraiment si nous pouvons décider si une expression est identique à zéro. Il s'agit probablement d'un problème sur lequel les informations sont plus faciles à trouver.

F

$F$

Yuval Filmus

8

La réponse courte à votre question est "non". Le théorème de Richardson et ses extensions ultérieures indiquent essentiellement que dès que vous incluez les fonctions trigonométriques élémentaires, le problème de décider si (et donc si , puisque c'est la même chose que ) est insoluble. $f(x) = 0$ $f(x) = g(x)$ $f(x) - g(x) = 0$

Ce qui est intéressant à ce sujet, c'est que la théorie du premier ordre des champs fermés réels est décidable. Intuitivement, la raison pour laquelle l'ajout de fonctions trigonométriques rend le système du premier ordre indécidable est que vous pouvez construire les entiers via , et que la théorie des entiers est indécidable . $\{ x \in R : \sin(\pi x) = 0 \}$

Que la théorie des champs fermés réels avec soit décidable ou non est un problème ouvert assez connu . $e^x$

Encore plus intéressant, c'est que si vous aviez un oracle qui "résolvait" le problème constant (c'est-à-dire un oracle qui peut vous dire si ou non), alors l' intégration des fonctions élémentaires en termes finis est décidable , et un algorithme pratique est connu. Donc, étant donné , nous pourrions trouver ou savoir qu'il n'y a pas d'intégrale élémentaire de en termes finis. $f(x) = 0$ $G(x)$ $F(x)$ $G$

Pseudonyme
la source

6

Votre problème semble réduire la question plus simple suivante:

Étant donné deux fonctions dans la classe de fonctions, avons-nous pour tout ? (En d'autres termes, ont-ils la même valeur partout?) $F,G$ $F(x)=G(x)$ $x$

Je ne sais pas si c'est décidable, pour cette classe de fonctions. Si c'est le cas, votre problème devrait également être décidable.

Pour votre problème, une approche générale est la suivante: différencier symboliquement pour obtenir , puis vérifier si nous avons pour tout . $F(x)$ $F'(x)$ $F'(x)=G(x)$ $x$

L'étape clé est donc la différenciation symbolique. Voyons comment faire cela plus en détail. Nous pouvons définir la classe des fonctions autorisées de manière récursive:

F (x) ::= c | x | e^{x} | \log (x) | \sin (x) | \cos (x) | \tan (x) | F_{1} (x) + F_{2} (x) | F_{1} (x) \times F_{2} (x) | F_{1} (x) / F_{2} (x) | F_{1} (F_{2} (x))

$\newcommand{\or}{\;\vert\;} F(x) ::= c \or x \or e^x \or \log(x) \or \sin(x) \or \cos(x) \or \tan(x) \or F_1(x) + F_2(x) \or F_1(x) \times F_2(x) \or F_1(x)/F_2(x) \or F_1(F_2(x))$

où s'étend sur les constantes et sur les fonctions. $c$ $F,F_1,F_2$

Il est alors possible de concevoir un algorithme récursif pour différencier symboliquement cette classe de fonctions, en utilisant les règles de calcul standard (par exemple, la règle de chaîne, etc.). En particulier, nous pouvons traiter tous les cas ci-dessus, et montrer récursivement que la dérivée peut être exprimée symboliquement comme une fonction dans cette classe. Par exemple:

Si , . $F(x)=c$ $F'(x)=0$
Si , . $F(x)=x$ $F'(x)=1$
Si , . $F(x)=e^x$ $F'(x)=e^x$
Si , . $F(x)=\log(x)$ $F'(x)=1/x$
Si , . $F(x)=\sin(x)$ $F'(x)=\cos(x)$
Si , . $F(x)=\tan(x)$ $F'(x)=1 + (\tan(x))^2$
Si , . $F(x)=F_1(x)+F_2(x)$ $F'(x)=F'_1(x)+F'_2(x)$
Si , . $F(x)=F_1(x) \times F_2(x)$ $F'(x)=F'_1(x) F_2(x) +F_1(x) F'_2(x)$
Si , (règle de chaîne). $F(x) = F_1(F_2(x))$ $F'(x) = F'_1(F_2(x)) F'_2(x)$

Etc. Dans chaque cas, si est dans la classe des fonctions autorisées, alors , et vous pouvez récursivement trouver une expression symbolique pour - c'est ce que l'on appelle la différenciation symbolique . $F(x)$ $F'(x)$ $F'(x)$

Enfin, il ne reste plus qu'à vérifier si pour tout . C'est le problème que je mentionne en haut de ma réponse. $F'(x)=G(x)$ $x$

Il existe une méthode simple pour vérifier si deux fonctions sont identiques à l'identique et je m'attends à ce qu'elle fonctionne plutôt bien dans la pratique. L'algorithme est le suivant: choisissez à plusieurs reprises une valeur aléatoire de et vérifiez si est valable pour cette valeur de . S'il est identique pour de nombreux choisis au hasard , alors affichez "ils sont identiques de façon identique". Si vous trouvez un pour lequel , alors affichez "ils sont différents". $x$ $F(x)=G(x)$ $x$ $x$ $x$ $F(x)\ne G(x)$

Il n'y a aucune garantie que cela fonctionnera, mais pour de nombreuses classes de fonctions, la sortie de cette procédure sera correcte avec une forte probabilité. En particulier, supposons que nous ayons une distribution sur représentée par la variable aléatoire et un tel que valable pour tous les de la classe. Supposons en outre que la classe des fonctions autorisées soit fermée par soustraction (comme l'est votre classe). Ensuite, il s'ensuit que tours de la procédure ci-dessus donnent la mauvaise réponse avec probabilité au plus . $x$ $X$ $\epsilon>0$ $\Pr[F(X)=0] \ge \epsilon$ $F$ $r$ $(1-\epsilon)^r$

De plus, s'il existe une procédure aléatoire pour les tests d'égalité polynomiale, alors le problème est décidable.

Reste à savoir si un tel résultat vaut pour votre classe particulière de fonctions. La déclaration ci-dessus ne tiendra probablement pas. Cependant, si nous avons de la chance, nous pourrions peut-être prouver quelque chose comme ce qui suit:

Pour tout , nous pouvons peut-être trouver une distribution sur des nombres réels, c'est-à-dire une variable aléatoire et une constante , telle que vaut pour toutes les fonctions qui sont dans votre classe et qui ont au plus "taille" . $s \in \mathbb{N}$ $X_s$ $\epsilon_s > 0$ $\Pr[F(X)=0]$ $F$ $s$

Si cela est vrai, il s'ensuit qu'il existe un algorithme randomisé pour les tests d'égalité polynomiale et donc votre problème est décidable.

DW
la source

Décidabilité de la vérification d'un antidérivatif?

Réponses: