Entscheidbarkeit der Überprüfung eines Antiderivativs?

Nehmen wir an, ich habe zwei Funktionen $F$ und $G$ und bin daran interessiert festzustellen, ob

Nehmen wir an, meine Funktionen bestehen aus Elementarfunktionen (Polynome, Exponentiale, Protokolle und trigonometrische Funktionen), aber nicht beispielsweise aus Taylorreihen.

Ist dieses Problem entscheidbar? Wenn nicht, ist es halbentscheidbar?

(Ich frage, weil ich eine Klasse zum Thema Berechenbarkeit unterrichte und ein Schüler mich fragte, ob ein TM Ihnen bei der Integration einer Funktion helfen könnte, deren Integral derzeit nicht bekannt ist. Ich vermute, dass die Funktionen, die wir nicht integrieren können, mehr sind richtig Funktionen, deren Integral nicht als Kombination der oben genannten Elementarfunktionen ausgedrückt werden kann, anstatt Funktionen, für die wir das Integral nicht wirklich kennen, aber das hat mich darüber nachdenken lassen, ob das allgemeine Problem der Überprüfung von Integralen entscheidbar war.)

Die kurze Antwort auf Ihre Frage lautet "Nein". Der Satz von Richardson und seine späteren Erweiterungen besagen grundsätzlich, dass, sobald Sie die elementaren trigonometrischen Funktionen einbeziehen, das Problem besteht, zu entscheiden, ob (und damit f ( x ) = g ( x ) , da dies dasselbe ist wie f ( x ) - g ( x ) = 0 ) ist unlösbar.$f(x) = 0$$f(x) = g(x)$$f(x) - g(x) = 0$

Das Interessante daran ist, dass die Theorie erster Ordnung realer geschlossener Felder entscheidbar ist. Intuitiv ist der Grund, warum das Hinzufügen trigonometrischer Funktionen das System erster Ordnung unentscheidbar macht, der, dass Sie die ganzen Zahlen über konstruieren können und die Theorie der ganzen Zahlen unentscheidbar ist.$\{ x \in R : \sin(\pi x) = 0 \}$

Ob die Theorie der realen geschlossenen Felder mit entscheidbar ist oder nicht, ist ein ziemlich berühmtes offenes Problem .$e^x$

Noch interessanter ist, dass, wenn Sie ein Orakel hatten, das das konstante Problem "löste" (dh ein Orakel, das Ihnen sagen kann, ob oder nicht), die Integration von Elementarfunktionen in endlichen Begriffen entscheidbar ist , und Ein praktischer Algorithmus ist bekannt. Wenn wir also G ( x ) geben , können wir F ( x ) finden oder wissen, dass es kein elementares Integral von G in endlichen Begriffen gibt.$f(x) = 0$$G(x)$$F(x)$$G$

Ihr Problem scheint die folgende einfachere Frage zu reduzieren:

Haben wir bei zwei Funktionen in der Funktionsklasse F ( x ) = G ( x ) für alle x ? (Mit anderen Worten, haben sie überall den gleichen Wert?)$F,G$$F(x)=G(x)$$x$

Ich weiß nicht, ob dies für diese Funktionsklasse entscheidbar ist. Wenn ja, sollte auch Ihr Problem entscheidbar sein.

Für Ihr Problem lautet ein allgemeiner Ansatz: Differenzieren Sie symbolisch , um F ' ( x ) zu erhalten , und prüfen Sie dann, ob für alle x F ' ( x ) = G ( x ) gilt .$F(x)$$F'(x)$$F'(x)=G(x)$$x$

Der Schlüsselschritt ist also die symbolische Differenzierung. Lassen Sie uns genauer herausfinden, wie das geht. Wir können die Klasse der zulässigen Funktionen rekursiv definieren:

Dabei liegt über Konstanten und über Funktionen.F , F 1 , F $c$$F,F_1,F_2$

Es ist dann möglich, einen rekursiven Algorithmus zur symbolischen Differenzierung dieser Funktionsklasse unter Verwendung der Standardregeln der Analysis (z. B. der Kettenregel usw.) zu entwickeln. Insbesondere können wir jeden obigen Fall behandeln und rekursiv zeigen, dass die Ableitung symbolisch als Funktion innerhalb dieser Klasse ausgedrückt werden kann. Zum Beispiel:

• Wenn , ist .F ' ( x ) = $F(x)=c$$F'(x)=0$

• Wenn , ist .F ' ( x ) = $F(x)=x$$F'(x)=1$

• Wenn , ist .F ' ( x ) = e $F(x)=e^x$$F'(x)=e^x$

• Wenn , ist .F ' ( x ) = 1 /$F(x)=\log(x)$$F'(x)=1/x$

• Wenn , ist .F ' ( x ) = cos ( x $F(x)=\sin(x)$$F'(x)=\cos(x)$

• Wenn , ist .F ' ( x ) = 1 + ( tan ( x ) ) $F(x)=\tan(x)$$F'(x)=1 + (\tan(x))^2$

• Wenn , ist .F ' ( x ) = F ' 1 ( x ) + F ' 2 ( x $F(x)=F_1(x)+F_2(x)$$F'(x)=F'_1(x)+F'_2(x)$

• Wenn , ist .F ' ( x ) = F ' 1 ( x ) F 2 ( x ) + F 1 ( x ) F ' 2 ( x $F(x)=F_1(x) \times F_2(x)$$F'(x)=F'_1(x) F_2(x) +F_1(x) F'_2(x)$

• Wenn , ist (Kettenregel).F ' ( x ) = F ' 1 ( F 2 ( x ) ) F ' 2 ( x $F(x) = F_1(F_2(x))$$F'(x) = F'_1(F_2(x)) F'_2(x)$

Und so weiter. Wenn in jedem Fall zur Klasse der zulässigen Funktionen gehört, gilt dies auch für , und Sie können rekursiv einen symbolischen Ausdruck für - dies wird als symbolische Differenzierung bezeichnet .F ' ( x ) F ' ( x $F(x)$$F'(x)$$F'(x)$

Schließlich muss nur noch geprüft werden, ob für alle . Das ist das Problem, das ich oben in meiner Antwort erwähne.$F'(x)=G(x)$$x$

Es gibt eine einfache Methode, um zu überprüfen, ob zwei Funktionen identisch sind, von der ich erwarten würde, dass sie in der Praxis ziemlich gut funktioniert. Der Algorithmus lautet wie folgt: Wählen Sie wiederholt einen Zufallswert von und prüfen Sie, ob für diesen Wert von . Wenn es für viele zufällig ausgewählte , geben Sie "sie sind identisch gleich" aus. Wenn Sie ein für das , geben Sie "sie sind unterschiedlich" aus.F ( x ) = G ( x ) x x x F ( x ) ≤ G ( x $x$$F(x)=G(x)$$x$$x$$x$$F(x)\ne G(x)$

Es gibt keine Garantie dafür, dass dies funktioniert, aber für viele Funktionsklassen ist die Ausgabe dieser Prozedur mit hoher Wahrscheinlichkeit korrekt. Nehmen wir insbesondere an, wir haben eine Verteilung auf die durch die Zufallsvariable und eine so dass für alle in der Klasse gilt. Angenommen, die Klasse der zulässigen Funktionen wird unter Subtraktion geschlossen (wie Ihre Klasse). Daraus folgt, dass Runden des obigen Verfahrens mit höchstens einer Wahrscheinlichkeit die falsche Antwort geben .X ϵ > 0 Pr [ F ( X ) = 0 ] ≥ ϵ F r ( 1 - ϵ ) $x$$X$$\epsilon>0$$\Pr[F(X)=0] \ge \epsilon$$F$$r$$(1-\epsilon)^r$

Wenn es ein randomisiertes Verfahren für die Prüfung der Polynomgleichheit gibt, ist das Problem entscheidbar.

Es bleibt zu fragen, ob ein solches Ergebnis für Ihre spezielle Funktionsklasse gilt. Die obige Aussage wird wahrscheinlich nicht gelten. Wenn wir jedoch Glück haben, können wir möglicherweise Folgendes beweisen:

Für alle können wir vielleicht eine Verteilung auf reelle Zahlen finden, dh eine Zufallsvariable und eine Konstante , so dass gilt für alle Funktionen , die in Ihrer Klasse sind und höchstens "Größe" haben .X s ϵ s > 0 Pr [ F ( X ) = 0 ] F $s \in \mathbb{N}$$X_s$$\epsilon_s > 0$$\Pr[F(X)=0]$$F$$s$

Wenn dies zutrifft, folgt daraus, dass es einen randomisierten Algorithmus für die Prüfung der Polynomgleichheit gibt und Ihr Problem daher entscheidbar ist.