Разрешимость проверки антипроизводных?

Предположим, у меня есть две функции $F$ и $G$ и я заинтересован в определении

Предположим, что мои функции состоят из элементарных функций (полиномов, экспонент, логарифмов и тригонометрических функций), но не, скажем, из ряда Тейлора.

Эта проблема разрешима? Если нет, то так ли это?

(Я спрашиваю, потому что я преподаю класс по вычислимости, и студент спросил меня, может ли ТМ помочь вам интегрировать функцию, интеграл которой в настоящее время неизвестен. Я подозреваю, что функции, которые мы не знаем, как интегрировать, более должным образом функции, интеграл которых не может быть выражен как комбинация вышеуказанных элементарных функций, а не функций, для которых мы фактически не знаем интеграл, но это заставило меня задуматься о том, была ли разрешима общая проблема проверки интегралов.)

Краткий ответ на ваш вопрос - «нет». Теорема Ричардсона и ее более поздние расширения в основном утверждают, что, как только вы включите элементарные тригонометрические функции, возникает проблема решения, если (и, следовательно, если f ( x ) = g ( x ) , так как это то же самое, что f ( x ) - g ( x ) = 0 ) неразрешима.$f(x) = 0$$f(x) = g(x)$$f(x) - g(x) = 0$

Интересно, что теория реальных замкнутых полей первого порядка разрешима. Интуитивно понятно, что добавление тригонометрических функций делает систему первого порядка неразрешимой, потому что вы можете построить целые числа через , а теория целых чисел неразрешима.$\{ x \in R : \sin(\pi x) = 0 \}$

Является ли теория реальных замкнутых полей с разрешимой - довольно известная открытая проблема .$e^x$

Еще более интересно то, что если у вас был оракул, который «решил» постоянную проблему (то есть оракул, который может сказать вам, если или нет), то интеграция элементарных функций в конечных терминах разрешима , и практический алгоритм известен. Поэтому, учитывая G ( x ) , мы могли бы найти F ( x ) или знать, что в конечных терминах нет элементарного интеграла от $f(x) = 0$$G(x)$$F(x)$$G$

Ваша проблема, кажется, уменьшает следующий простой вопрос:

Учитывая две функции в классе функций, имеем ли мы F ( x ) = G ( x ) для всех x ? (Другими словами, они имеют одинаковое значение везде?)$F,G$$F(x)=G(x)$$x$

Я не знаю, разрешимо ли это для этого класса функций. Если это так, то и ваша проблема должна быть решаемой.

$F(x)$$F'(x)$$F'(x)=G(x)$$x$

Таким образом, ключевым шагом является символическая дифференциация. Давайте разберемся, как сделать это более подробно. Мы можем определить класс допустимых функций рекурсивно:

где пределах констант, а в зависимости от функций.$c$$F,F_1,F_2$

Затем можно разработать рекурсивный алгоритм для символической дифференциации этого класса функций, используя стандартные правила исчисления (например, правило цепочки и т. Д.). В частности, мы можем обработать каждый описанный выше случай и рекурсивно показать, что производная может быть символически выражена как функция в этом классе. Например:

• Если , .$F(x)=c$$F'(x)=0$

• Если , .$F(x)=x$$F'(x)=1$

• Если , .$F(x)=e^x$$F'(x)=e^x$

• Если , .$F(x)=\log(x)$$F'(x)=1/x$

• Если , .$F(x)=\sin(x)$$F'(x)=\cos(x)$

• Если , .$F(x)=\tan(x)$$F'(x)=1 + (\tan(x))^2$

• Если , .$F(x)=F_1(x)+F_2(x)$$F'(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)$

• Если , (правило цепочки).$F(x) = F_1(F_2(x))$$F'(x) = F'_1(F_2(x)) F'_2(x)$

И так далее. В каждом случае, если находится в классе допустимых функций, то так же, как и , и вы можете рекурсивно составить символическое выражение для - это известно как символьное дифференцирование .$F(x)$$F'(x)$$F'(x)$

Наконец, остается только проверить, является ли для всех . Это проблема, которую я упоминаю в верхней части моего ответа.$F'(x)=G(x)$$x$

Существует простой метод проверки того, что две функции одинаково равны, и я ожидаю, что они будут работать довольно хорошо на практике. Алгоритм таков: многократно выбирайте случайное значение и проверяйте, выполняется ли для этого значения . Если он выполняется с равенством для многих случайно выбранных , выведите «они одинаково равны». Если вы найдете для которого , то выведите «они разные».F ( x ) = G ( x ) x x x F ( x ) ≠ G ( x $x$$F(x)=G(x)$$x$$x$$x$$F(x)\ne G(x)$

Нет гарантии, что это будет работать, но для многих классов функций вывод этой процедуры будет правильным с высокой вероятностью. В частности, предположим, что у нас есть некоторое распределение по представленное случайной величиной и некоторое число такое, что выполняется для всех в классе. Кроме того, предположим, что класс допустимых функций замкнут относительно вычитания (как и ваш класс). Из этого следует, что раундов описанной выше процедуры дает неправильный ответ с вероятностью не более .$x$$X$$\epsilon>0$F r ( 1 - ϵ ) $\Pr[F(X)=0] \ge \epsilon$$F$$r$$(1-\epsilon)^r$

Кроме того, если существует рандомизированная процедура для проверки полиномиального равенства, то проблема разрешима.

Осталось спросить, имеет ли место такой результат для вашего конкретного класса функций. Заявление выше, вероятно, не будет иметь места. Однако, если нам повезет, возможно, мы сможем доказать что-то вроде следующего:

Для всех , возможно, мы можем найти распределение по действительным числам, т. переменную и константу , такую, что выполняется для всех функций которые находятся в вашем классе и имеют «размер» не более .X s ϵ s > 0 Pr [ F ( X ) = 0 ] F $s \in \mathbb{N}$$X_s$$\epsilon_s > 0$$\Pr[F(X)=0]$$F$$s$

Если это так, то из этого следует, что существует рандомизированный алгоритм для проверки полиномиального равенства, и, следовательно, ваша проблема разрешима.