Rozstrzygalność sprawdzania pierwotnego?

Załóżmy, że mam dwie funkcje i i jestem zainteresowany ustaleniem, czy$F$$G$

Załóżmy, że moje funkcje składają się z funkcji elementarnych (wielomiany, wykładnicze, logi i funkcje trygonometryczne), ale nie, powiedzmy, szereg Taylora.

Czy można rozwiązać ten problem? Jeśli nie, czy jest to w połowie rozstrzygalne?

(Pytam, ponieważ prowadzę zajęcia na temat obliczalności, a uczeń zapytał mnie, czy baza TM mogłaby pomóc w integracji funkcji, której całka nie była obecnie znana. Podejrzewam, że funkcje, których nie umiemy zintegrować, są bardziej właściwie funkcje, których całki nie można wyrazić jako kombinację powyższych funkcji elementarnych zamiast funkcji, dla których tak naprawdę nie znamy całki, ale to sprawiło, że pomyślałem o tym, czy ogólny problem sprawdzania całek był rozstrzygalny.)

Krótka odpowiedź na twoje pytanie brzmi „nie”. Twierdzenie Richardsona i jego późniejsze rozszerzenia zasadniczo stwierdzają, że jak tylko uwzględnisz elementarne funkcje trygonometryczne, problem decydowania o tym, czy (a zatem czy , ponieważ jest to to samo, co ) jest nierozwiązywalne.$f(x) = 0$$f(x) = g(x)$$f(x) - g(x) = 0$

Interesujące w tym jest to, że teoria pierwszego rzędu rzeczywistych pól zamkniętych jest rozstrzygalna. Intuicyjnie powodem, dla którego dodanie funkcji trygonometrycznych sprawia, że ​​system pierwszego rzędu jest nierozstrzygalny, jest to, że można konstruować liczby całkowite za pomocą , a teoria liczb całkowitych jest nierozstrzygalna .$\{ x \in R : \sin(\pi x) = 0 \}$

To, czy teoria rzeczywistych zamkniętych pól za pomocą jest rozstrzygalna, jest dość znanym otwartym problemem .$e^x$

Jeszcze bardziej interesujące jest to, że jeśli miałeś wyrocznię, która „rozwiązała” stały problem (tj. Wyrocznię, która może powiedzieć ci, czy czy nie), to rozstrzygająca jest integracja funkcji elementarnych w kategoriach skończonych , i praktyczny algorytm jest znany. Biorąc pod uwagę , możemy znaleźć lub wiedzieć, że nie ma elementarnej całki w kategoriach skończonych.$f(x) = 0$$G(x)$$F(x)$$G$

Twój problem wydaje się redukować następujące prostsze pytanie:

Biorąc pod uwagę dwie funkcje w klasie funkcji, czy mamy dla wszystkich ? (Innymi słowy, czy mają one wszędzie tę samą wartość?)$F,G$$F(x)=G(x)$$x$

Nie wiem, czy jest to rozstrzygalne dla tej klasy funkcji. Jeśli tak, to twój problem również powinien być rozstrzygalny.

W przypadku twojego problemu ogólne podejście to: symbolicznie różnicuj aby uzyskać , a następnie sprawdź, czy mamy dla wszystkich .$F(x)$$F'(x)$$F'(x)=G(x)$$x$

Zatem kluczowym krokiem jest różnicowanie symboliczne. Dowiedzmy się, jak to zrobić bardziej szczegółowo. Możemy zdefiniować klasę dopuszczalnych funkcji rekurencyjnie:

gdzie rozciąga się ponad stałe, a zakres ponad funkcje.$c$$F,F_1,F_2$

Możliwe jest zatem opracowanie algorytmu rekurencyjnego do symbolicznego różnicowania tej klasy funkcji, przy użyciu standardowych reguł rachunku różniczkowego (np. Reguła łańcuchowa itp.). W szczególności możemy obsłużyć każdy powyższy przypadek i rekurencyjnie pokazać, że pochodną można wyrazić symbolicznie jako funkcję w tej klasie. Na przykład:

• Jeśli , .$F(x)=c$$F'(x)=0$

• Jeśli , .$F(x)=x$$F'(x)=1$

• Jeśli , .$F(x)=e^x$$F'(x)=e^x$

• Jeśli , .$F(x)=\log(x)$$F'(x)=1/x$

• Jeśli , .$F(x)=\sin(x)$$F'(x)=\cos(x)$

• Jeśli , .$F(x)=\tan(x)$$F'(x)=1 + (\tan(x))^2$

• Jeśli , .$F(x)=F_1(x)+F_2(x)$$F'(x)=F'_1(x)+F'_2(x)$

• Jeśli , .$F(x)=F_1(x) \times F_2(x)$$F'(x)=F'_1(x) F_2(x) +F_1(x) F'_2(x)$

• Jeśli , (reguła łańcuchowa).$F(x) = F_1(F_2(x))$$F'(x) = F'_1(F_2(x)) F'_2(x)$

I tak dalej. W każdym przypadku, jeśli należy do klasy dozwolonych funkcji, to także i można rekurencyjnie wypracować wyrażenie symboliczne dla - jest to znane jako różnicowanie symboliczne .$F(x)$$F'(x)$$F'(x)$

Na koniec pozostaje tylko sprawdzić, czy dla wszystkich . O tym problemie wspominam na początku mojej odpowiedzi.$F'(x)=G(x)$$x$

Istnieje prosta metoda sprawdzenia, czy dwie funkcje są identyczne, i spodziewałbym się, że zadziała całkiem dobrze w praktyce. Algorytm jest następujący: wielokrotnie wybierz losową wartość i sprawdź, czy utrzymuje dla tej wartości . Jeśli zachowuje równość dla wielu losowo wybranych , to wypisz „są identyczne”. Jeśli znajdziesz dowolne dla którego , to wypisz „są różne”.$x$$F(x)=G(x)$$x$$x$$x$$F(x)\ne G(x)$

Nie ma gwarancji, że to zadziała, ale dla wielu klas funkcji wynik tej procedury będzie poprawny z dużym prawdopodobieństwem. W szczególności załóżmy, że mamy pewien rozkład na reprezentowany przez zmienną losową i niektóre takie, że zachowuje się dla wszystkich w klasie. Przypuśćmy ponadto, że klasa dopuszczalnych funkcji jest zamknięta odejmując (tak jak twoja klasa). To stąd, że rund powyższej procedury daje złe odpowiedź z prawdopodobieństwem najwyżej .$x$$X$$\epsilon>0$$\Pr[F(X)=0] \ge \epsilon$$F$$r$$(1-\epsilon)^r$

Ponadto, jeśli istnieje randomizowana procedura testowania równości wielomianowej, problem jest rozstrzygalny.

Pozostaje pytanie, czy taki wynik odnosi się do konkretnej klasy funkcji. Powyższe stwierdzenie prawdopodobnie się nie utrzyma. Jeśli jednak będziemy mieli szczęście, być może uda nam się udowodnić coś takiego:

Dla wszystkich być może możemy znaleźć rozkład na liczbach rzeczywistych, tj. zmienną i stałą , taką, że obowiązuje dla wszystkich funkcji które są w twojej klasie i mają „rozmiar” co najwyżej .$s \in \mathbb{N}$$X_s$$\epsilon_s > 0$$\Pr[F(X)=0]$$F$$s$

Jeśli jest to prawda, oznacza to, że istnieje losowy algorytm do testowania równości wielomianowej, a zatem twój problem jest rozstrzygalny.