Decidability untuk mengecek antiderivative?

Misalkan saya memiliki dua fungsi dan dan saya tertarik untuk menentukan apakah$F$$G$

Misalkan fungsi saya terdiri dari fungsi-fungsi dasar (polinomial, eksponensial, log, dan fungsi trigonometri), tetapi tidak, katakanlah, deret Taylor.

Apakah masalah ini dapat diputuskan? Jika tidak, apakah itu bisa ditentukan?

(Saya bertanya karena saya sedang mengajar kelas tentang kemampuan komputasi dan seorang siswa bertanya kepada saya apakah TM dapat membantu Anda mengintegrasikan fungsi yang integralnya saat ini tidak diketahui. Saya menduga bahwa fungsi yang tidak kita ketahui cara memadukannya lebih banyak. benar fungsi yang integral tidak dapat diekspresikan sebagai kombinasi dari fungsi-fungsi dasar di atas daripada fungsi yang kita tidak benar-benar tahu integral, tapi itu membuat saya berpikir tentang apakah masalah umum memeriksa integral dapat ditentukan.)

Jawaban singkat untuk pertanyaan Anda adalah "tidak". Teorema Richardson dan ekstensi selanjutnya pada dasarnya menyatakan bahwa begitu Anda memasukkan fungsi trigonometri elementer, masalah menentukan apakah $f(x) = 0$ (dan karenanya jika $f(x) = g(x)$ , karena ini sama dengan $f(x) - g(x) = 0$ ) tidak dapat dipecahkan.

Yang menarik tentang ini adalah bahwa teori orde pertama bidang tertutup nyata dapat dipilih. Secara intuitif, alasan mengapa menambahkan fungsi trigonometrik membuat sistem urutan pertama tidak dapat diputuskan adalah karena Anda dapat membuat bilangan bulat melalui $\{ x \in R : \sin(\pi x) = 0 \}$ , dan teori bilangan bulat tidak dapat diputuskan.

Apakah teori bidang tertutup nyata dengan $e^x$ dapat dianggap sebagai masalah terbuka yang cukup terkenal .

Yang lebih menarik lagi adalah bahwa jika Anda memiliki oracle yang "memecahkan" masalah konstan (yaitu oracle yang dapat memberi tahu Anda jika atau tidak), maka integrasi fungsi-fungsi dasar dalam istilah yang terbatas dapat ditentukan , dan algoritma praktis dikenal. Jadi diberikan G ( x ) , kita bisa menemukan F ( x ) atau tahu bahwa tidak ada integral dasar G dalam istilah yang terbatas.$f(x) = 0$$G(x)$$F(x)$$G$

Masalah Anda tampaknya mengurangi pertanyaan sederhana berikut ini:

Diberikan dua fungsi di kelas fungsi, apakah kita memiliki F ( x ) = G ( x ) untuk semua x ? (Dengan kata lain, apakah mereka memiliki nilai yang sama di mana-mana?)$F,G$$F(x)=G(x)$$x$

Saya tidak tahu apakah ini decidable, untuk kelas fungsi ini. Jika ya, maka masalah Anda juga harus diperhitungkan.

Untuk masalah Anda, pendekatan umum adalah: secara simbolis membedakan untuk mendapatkan F ′ ( x ) , lalu periksa apakah kami memiliki F ′ ( x ) = G ( x ) untuk semua x .$F(x)$$F'(x)$$F'(x)=G(x)$$x$

Jadi langkah kuncinya adalah diferensiasi simbolis. Mari kita cari tahu bagaimana melakukannya secara lebih rinci. Kita dapat mendefinisikan kelas fungsi yang diizinkan secara rekursif:

di mana berkisar pada konstanta dan rentang F , F 1 , F 2 atas fungsi.$c$$F,F_1,F_2$

Maka dimungkinkan untuk merancang algoritma rekursif untuk secara simbolis membedakan kelas fungsi ini, menggunakan aturan standar kalkulus (misalnya, aturan rantai, dll.). Secara khusus, kami dapat menangani setiap kasus di atas, dan menunjukkan secara berulang bahwa turunan dapat diekspresikan secara simbolis sebagai fungsi dalam kelas ini. Contohnya:

• Jika , F ′ ( x ) = 0 .$F(x)=c$$F'(x)=0$

• Jika , F ′ ( x ) = 1 .$F(x)=x$$F'(x)=1$

• Jika , F ′ ( x ) = e x .$F(x)=e^x$$F'(x)=e^x$

• Jika , F ′ ( x ) = 1 / x .$F(x)=\log(x)$$F'(x)=1/x$

• Jika , F ′ ( x ) = cos ( x ) .$F(x)=\sin(x)$$F'(x)=\cos(x)$

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

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

• Jika , 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)$

• Jika , F ′ ( x ) = F ′ 1 ( F 2 ( x ) ) F ′ 2 ( x ) (aturan rantai).$F(x) = F_1(F_2(x))$$F'(x) = F'_1(F_2(x)) F'_2(x)$

Dan seterusnya. Dalam setiap kasus, jika berada dalam kelas fungsi yang diizinkan, maka begitu juga F ′ ( x ) , dan Anda dapat secara rekursif menyusun ekspresi simbolik untuk F ′ ( x ) - ini dikenal sebagai diferensiasi simbolis .$F(x)$$F'(x)$$F'(x)$

Akhirnya, yang tersisa adalah memeriksa apakah untuk semua x . Itulah masalah yang saya sebutkan di bagian atas jawaban saya.$F'(x)=G(x)$$x$

Ada metode sederhana untuk memeriksa apakah dua fungsi identik sama yang saya harapkan akan bekerja dengan baik dalam praktiknya. Algoritmanya adalah ini: berulang kali memilih nilai acak , dan periksa apakah F ( x ) = G ( x ) berlaku untuk nilai x tersebut . Jika itu berlaku dengan kesetaraan untuk banyak x yang dipilih secara acak , maka output "mereka sama identik". Jika Anda menemukan x yang F ( x ) ≠ G ( x ) , maka output "mereka berbeda".$x$$F(x)=G(x)$$x$$x$$x$$F(x)\ne G(x)$

Tidak ada jaminan bahwa ini akan berhasil, tetapi untuk banyak kelas fungsi, output dari prosedur ini akan benar dengan probabilitas tinggi. Secara khusus, misalkan kita memiliki beberapa distribusi pada diwakili oleh variabel acak X dan beberapa ε > 0 sehingga Pr [ F ( X ) = 0 ] ≥ ε berlaku untuk semua F di kelas. Anggap pula kelas fungsi yang diizinkan ditutup dengan pengurangan (seperti kelas Anda). Maka r putaran prosedur di atas memberikan jawaban yang salah dengan probabilitas paling banyak $x$$X$$\epsilon>0$$\Pr[F(X)=0] \ge \epsilon$$F$$r$ .$(1-\epsilon)^r$

Juga, jika ada prosedur acak untuk pengujian kesetaraan polinomial, maka masalahnya dapat diputuskan.

Tetap bertanya apakah hasil seperti itu berlaku untuk kelas fungsi khusus Anda. Pernyataan di atas mungkin tidak berlaku. Namun, jika kita beruntung, mungkin kita bisa membuktikan sesuatu seperti berikut:

$s \in \mathbb{N}$$X_s$$\epsilon_s > 0$$\Pr[F(X)=0]$$F$$s$

Jika ini benar, maka akan mengikuti bahwa ada algoritma acak untuk pengujian kesetaraan polinomial dan dengan demikian masalah Anda dapat ditentukan.