Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?

Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational?

Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie liczby są równe, ale nie widzę, jak to udowodnić.

Edycja: Liczbę obliczalną podaje funkcja która może zwrócić racjonalne przybliżenie z dokładnością : , dla każdego . Biorąc pod uwagę taką funkcję, czy można sprawdzić, czy czy ?$x$$f_x(\epsilon)$$x$$\epsilon$$|x - f_x(\epsilon)| \leq \epsilon$$\epsilon > 0$$x \in \mathrm{Q}$$x \in \mathrm{Z}$

Łatwo jest pomylić, co to znaczy „reprezentować” lub „implementować” liczbę rzeczywistą. W rzeczywistości jesteśmy świadkami dyskusji w komentarzach, w których reprezentacja jest sporna. Więc pozwól mi zająć się tym pierwszym.

Skąd wiemy, że wdrożenie jest prawidłowe?

Teorią, która wyjaśnia, jak reprezentować rzeczy w komputerze, jest wykonalność . Podstawową ideą jest to, że biorąc pod uwagę zbiór , wybieramy typ danych τ i każdemu x ∈ X zbiór wartości typu τ, które go realizują . Piszemy v ⊢ x ∈ X, gdy v jest wartością, która realizuje x . Na przykład (użyję Haskell bez powodu) rozsądną implementacją może być typ danych, gdzie gdy ma wartość liczbową$X$$\tau$$x \in X$$\tau$$v \vdash x \in X$$v$$x$ v ⊢ k ∈ N v ¯ k T r u e ⊢ 42 ∈ N F a l s e ⊢ n ∈ N dla n ≠ 42 . Dlaczego to jest nieprawidłowe? Potrzebujemykryterium.$\mathbb{N}$Integer$v \vdash k \in \mathbb{N}$$v$$\overline{k}$ (a zatem w szczególności -42nie reprezentuje liczby naturalnej, podobnie jak program rozbieżny). Ale jakiś joker mógłby przejść obok i zasugerować, że używamy Booldo reprezentowania liczb naturalnych za pomocą i$\mathtt{True} \vdash 42 \in \mathbb{N}$$\mathtt{False} \vdash n \in \mathbb{N}$$n \neq 42$

W przypadku „liczb jokera” łatwo zauważyć, że dodawanie nie może zostać zaimplementowane. Przypuśćmy, że powiem ci, że mam dwie liczby, obie reprezentowane przez . Czy możesz podać realizatora za ich sumę? Zależy to od tego, czy suma wynosi 42, ale nie można powiedzieć. Ponieważ dodawanie jest „istotną częścią liczb naturalnych”, jest to niedopuszczalne. Innymi słowy, implementacja nie polega na zestawach, ale na strukturach , tzn. Musimy reprezentować zestawy w taki sposób, aby możliwe było również zaimplementowanie odpowiedniej struktury. Pozwól mi podkreślić:$\mathtt{False}$

Wdrażamy struktury, a nie nagie zestawy. Dlatego musimy być w stanie zaimplementować całą strukturę, wraz z operacjami i wszystkimi aksjomatami, aby implementacja była poprawna.

Jeśli nie przestrzegasz tej zasady, musisz zasugerować alternatywne matematyczne kryterium poprawności. Nie znam żadnego.

Przykład: reprezentacja liczb naturalnych

W przypadku liczb naturalnych odpowiednią strukturę opisują aksjomaty Peano, a kluczowym aksjomatem, który należy zaimplementować, jest indukcja (ale także , następca, + i × ). Możemy obliczyć, wykorzystując wykonalność, to, co robi implementacja indukcyjna. Okazuje się, że jest to mapa (gdzie jest jeszcze nieznany typ danych reprezentujący liczby naturalne)$0$$+$$\times$nat

induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

satysfakcjonujący induction x f zero = xi induction x f (succ n) = f n (induction x f n). Wszystko to wynika z wykonalności. Mamy kryterium: implementacja liczb naturalnych jest poprawna, gdy pozwala na implementację aksjomatów Peano. Podobny wynik można by uzyskać, jeśli stosuje się charakterystykę liczb jako początkowy Algebra do funktora .$X \mapsto 1 + X$

Prawidłowa implementacja liczb rzeczywistych

Zwróćmy uwagę na liczby rzeczywiste i pytanie. Pierwszym pytaniem, jakie należy zadać, jest: „jaka jest odpowiednia struktura liczb rzeczywistych?” Odpowiedź brzmi: Archimedesowe Cauchy wypełnia uporządkowane pole . Takie jest ustalone znaczenie „liczb rzeczywistych”. Nie możesz go zmienić, zostało to naprawione przez innych dla ciebie (w naszym przypadku alternatywne realia Dedekinda okazują się izomorficzne z realiami Cauchy'ego, które rozważamy tutaj.) Nie możesz go zabrać, nie wolno Ci mówić „Nie dbam o wdrożenie dodawania” lub „Nie dbam o zamówienie”. Jeśli to zrobisz, nie możesz nazywać go „liczbami rzeczywistymi”, ale coś w rodzaju „liczb rzeczywistych, w których zapominamy o porządku liniowym”.

Nie będę wchodził w wszystkie szczegóły, ale wyjaśnię, w jaki sposób różne części struktury dają różne operacje na rzeczywistych elementach:

• Archimedesa aksjomat jest o obliczenie racjonalnych przybliżenia liczb rzeczywistych
• struktura pola daje zwykłe operacje arytmetyczne
• kolejność liniowa daje nam półdecydowalną procedurę testowania $x < y$
• kompletność Cauchy daje nam funkcję lim : (nat -> real) -> real, która pobiera (reprezentacji) szybki ciągiem Cauchy'ego i zwraca swój limit. (Sekwencja jest szybka, jeśli | x n - x m | ≤ 2 min ( n , m ) dla wszystkich m , n .)$(x_n)_n$$|x_n - x_m| \leq 2^{\min(n,m)}$$m, n$

Czego nie otrzymujemy, to funkcja testowa równości. Nie ma nic w aksjomatów dla liczb rzeczywistych, które prosi być rozstrzygalne. (Przeciwnie, aksjomaty Peano sugerują, że liczby naturalne są rozstrzygalne, a można to udowodnić, stosując ćwiczenie wyłącznie jako zabawę).$=$eq : nat -> nat -> Boolinduction

Faktem jest, że zwykła dziesiętna reprezentacja rzeczywistości, której używa ludzkość, jest zła, ponieważ nie możemy nawet wprowadzić dodawania. Punkt zmiennoprzecinkowy z nieskończoną mantysą również zawodzi (ćwiczenie: dlaczego?). Co działa, jednak jest podpisany cyfrową reprezentację, czyli ten, w którym pozwoli negatywne cyfr, jak również pozytywne. Lub możemy użyć sekwencji racjonalnych, które spełniają szybki test Cauchy'ego, jak stwierdzono powyżej.

Reprezentacja Tsuyoshi również coś implementuje, ale nie $\mathbb{R}$

Rozważmy następującą reprezentację liczb rzeczywistych: rzeczywisty jest reprezentowany przez parę ( q , b ), gdzie ( q n ) n jest szybką sekwencją Cauchyego zbiegającą się z x, a b jest wartością logiczną wskazującą, czy x jest liczbą całkowitą. Aby było to przedstawienie rzeczywistych wartości, musielibyśmy zaimplementować dodawanie, ale jak się okazuje, nie możemy obliczyć flag boolowskich. To nie jest przedstawienie rzeczywistości. Ale nadal coś reprezentuje, a mianowicie podzbiór rzeczywistości Z ∪ ( R ∖ Z$x$$(q,b)$$(q_n)_n$$x$$b$$x$$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$. Rzeczywiście, zgodnie z interpretacją realizowalności związek jest realizowany z flagą wskazującą, które część unii jesteśmy w. Przy okazji, jest nie równa się R , chyba że wierzą w wyłączonego środka, który nie może zostać wdrożony i dlatego jest dość nieistotny dla tej dyskusji. Jesteśmy zmuszeni przez komputery do robienia rzeczy intuicyjnie.$\mathbb{Z} \cup (\mathbb{R} \setminus \mathbb{Z})$$\mathbb{R}$

Nie możemy sprawdzić, czy wartość rzeczywista jest liczbą całkowitą

Na koniec pozwól mi odpowiedzieć na zadane pytanie. Wiemy teraz, że akceptowalną reprezentacją reali są szybkie sekwencje racjonalne Cauchy'ego. (Ważne twierdzenie głosi, że dowolne dwa przedstawienia rzeczywistości, które są dopuszczalne, są w rzeczywistości obliczalne izomorficzne.)

Twierdzenie: Testowanie, czy real jest liczbą całkowitą, nie jest rozstrzygalne.

Dowód. Załóżmy, że moglibyśmy sprawdzić, czy rzeczywista jest liczbą całkowitą (oczywiście rzeczywista jest realizowana przez szybką sekwencję Cauchy'ego). Ideą, która pozwoli ci udowodnić znacznie bardziej ogólne twierdzenie, jeśli chcesz, jest skonstruowanie szybkiej sekwencji Cauchy'ego liczb całkowitych, która zbiega się w liczbę całkowitą. Jest to łatwe, wystarczy wziąć x n = 2 - n . Następnie rozwiąż problem zatrzymania w następujący sposób. Biorąc pod maszyną Turinga T , określa się nową sekwencję ( R n ) n o r n = { X n jeżeli  $(x_n)_n$$x_n = 2^{-n}$$T$$(y_n)_n$ Oznacza to, że nowy wygląd sekwencji lubią sekwencji(xn)ntak długo, jakTtras, ale potem robi się „Stuck” naxmifTzatrzymuje się w krokum. Co bardzo ważne, nowa sekwencja jest również szybką sekwencją Cauchy'ego (i możemy to udowodnić, nie wiedząc, czyT sięzatrzyma). Dlatego możemy obliczyć jego limitz=limny

Ćwiczenie: dostosuj powyższy dowód, aby pokazać, że nie możemy testować liczb wymiernych. Następnie dostosuj go, aby pokazać, że nie możemy testować niczego nietrywialnego (jest to nieco trudniejsze).

Czasami ludzie są zdezorientowani całym tym biznesem testowania. Uważają, że udowodniliśmy, że nigdy nie możemy sprawdzić, czy rzeczywista liczba całkowita. Ale z pewnością 42 to prawda i możemy stwierdzić, czy jest liczbą całkowitą. W rzeczywistości każdy szczególności rzeczywistym możemy wymyślić, , 88 ln 89 , e gatunku $\sin 11$$88 \ln 89$ itd., Możemy doskonale stwierdzić, czy są to liczby całkowite. Dokładniemożemypowiedzieć, ponieważmamydodatkowe informacje: te liczby nie są nam przekazywane jako sekwencje, ale raczej jako wyrażenia symboliczne, z których możemy obliczyć bit Tsuyoshi. Tak szybko, jak tylko mamy informacji o rzeczywistym jest sekwencją racjonalnych przybliżeń zbieżnych z nim (i mamnieznaczy symboliczny wyraz opisujący sekwencję, ale czarną skrzynkę, która wyprowadzan-tej termin na wejściun) wtedy będzie tak samo bezradny jak maszyny.$e^{\pi \sqrt{163}}$$n$$n$

Morał tej historii

Nie ma sensu rozmawiać o implementacji zestawu, chyba że wiemy, jakie operacje chcemy na nim wykonać.

Wydaje mi się, że jest to nierozstrzygalne:

Niech będzie obliczalną liczbą niewymierną. Rozważmy TM M . Możesz zbudować funkcję, która uruchamia M na ϵ i równolegle oblicza x z rosnącą precyzją. Jeśli M zatrzyma się, przestanie obliczać x , w przeciwnym razie będzie kontynuowane.$x$$M$$M$$\epsilon$$x$$M$$x$

Decyzja, czy ta funkcja oblicza liczbę wymierną, jest równoważna problemowi zatrzymania.

Zakładając, że rzeczywistość jest podana jako sekwencja racjonalnych aproksymacji z błędem ograniczonym przez pewną znaną funkcję obliczeniową, która dąży do zera (wszystkie takie aproksymacje są równoważne i odpowiadają zwykłej topologii na liczbach rzeczywistych).

Funkcje obliczalne są ciągłe. IsRational i IsInteger nie są ciągłe i dlatego nie są obliczalne.

IsInteger jest częściowo obliczalny: istnieje procedura, która ostatecznie wyśle ​​„fałsz”, jeśli dane wejściowe nie są liczbami całkowitymi, ale będą działać wiecznie, jeśli dane wejściowe będą liczbami całkowitymi. Ta procedura po prostu sprawdza każde przybliżenie i sprawdza, czy w granicach błędu występuje liczba całkowita. Ta funkcja jest ciągła, gdy używamy topologii Sierpińskiego na {prawda, fałsz} (tj. {Fałsz} jest zbiorem otwartym, ale {prawda} nie jest).

Nie można rozstrzygnąć, czy dana liczba obliczalna jest równa zero .

(Więc twoja wyrocznia racjonalnego przybliżenia zwraca 0 za każde ε, którego próbowałeś? Może po prostu nie dałeś jej wystarczająco małej ε.)

Dlatego nierozstrzygalne jest, czy dana liczba obliczalna między -½ a + ½ jest liczbą całkowitą.

Funkcja podlegająca obliczeniu jest silniejsza niż funkcja ciągła, tzn. Każda funkcja obliczalna musi być ciągła w topologii informacji.

$F:\mathbb{R} \to \{Yes,No\}$

jest obliczalny.

$r$$\frac{k}{2^{n}}$$r \in [\frac{k}{2^n},\frac{k+1}{2^n}]$$n$

Zatem twoja funkcja nie jest ciągła i dlatego nie można jej obliczyć.

$M$$0$$n$$[-\frac{1}{2^n},\frac{1}{2^n}]$$M$$M$$m$$M$$[-\frac{1}{2^m},\frac{1}{2^m}]$$M$$M$$NO$$YES$$M$$[-\frac{1}{2^m},\frac{1}{2^m}]$$M$$YES$$M$

Dowód, że każda funkcja obliczeniowa musi być ciągła, jest podobny.