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

18

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 ?xfx(ϵ)xϵ|xfx(ϵ)|ϵϵ>0xQxZ

dbarbosa
źródło
3
Jak podawana jest liczba obliczalna?
Tsuyoshi Ito
10
Sposób podania numeru jest oczywiście istotny. Jako głupi przykład, jeśli wejście zawiera flagę, czy liczba jest liczbą całkowitą, czy nie, decydowanie, czy dane wejściowe są liczbą całkowitą, czy nie, jest banalne.
Tsuyoshi Ito
3
Podobne pytanie: cstheory.stackexchange.com/questions/10495/...
Kristoffer Arnsfelt Hansen
3
(1) „Skąd wiesz, że jest to liczba całkowita?” Dlaczego mam się przejmować? Nie powiedziałeś nic o wymaganiach dotyczących operacji. (2) „Jeśli do tej pory widzisz dwie odpowiedzi, nie wspominają nic o implementacji.” Nie wiem, co rozumiesz przez „implementację” tutaj, ani dlaczego to zdanie jest istotne dla moich komentarzy.
Tsuyoshi Ito
16
Mam nadzieję, że moja odpowiedź kryje w sobie tę dyskusję. Tsuyoshi, mylisz się, ważne jest, jakie operacje są obliczalne. Nie implementujemy liczb rzeczywistych w próżni, ale w celu manipulowania nimi . Według ciebie możemy po prostu użyć typu jednostki do wdrożenia wszystkiego. Tak, moglibyśmy, ale wtedy niektóre operacje nie byłyby obliczalne, i to jest właśnie kryterium, według którego oceniamy reprezentacje.
Andrej Bauer,

Odpowiedzi:

32

Ł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τxXτvxXvx v k N v ¯ k T r u e42 N F a l s en N dla n 42 . Dlaczego to jest nieprawidłowe? Potrzebujemykryterium.NIntegervkNvk¯ (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ą iTrue42NFalsenNn42

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ć: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+×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 .X1+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 .)(xn)n|xnxm|2min(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 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( RZ )x(q,b)(qn)nxbxZ(RZ). 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.Z(RZ)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  T(xn)nxn=2nT(yn)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=limnyn

yn={xnif T has not stopped within n stepsxmif T stopped in step m and mn
(xn)nTxmTmTz=limnyn, ponieważ nasza reprezentacja reali jest poprawna. Sprawdź, czy jest liczbą całkowitą. Jeśli tak, to musi być 0, a dzieje się tak tylko wtedy, gdy T działa wiecznie. W przeciwnym razie z nie jest liczbą całkowitą, więc T musiał się zatrzymać. CO BYŁO DO OKAZANIA.z0TzT

Ć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 sin1188ln89 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π163nn

Morał tej historii

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

Andrej Bauer
źródło
16
Gdyby moje odpowiedzi były żonami, mógłbym odpowiedzieć tylko raz. A przynajmniej musiałbym usunąć poprzednią odpowiedź, zanim napisałem następną.
Andrej Bauer,
5
@Max: pierwsze tego rodzaju twierdzenia zostały podane przez Kreisela, Lacombe i Shoenfielda (patrz twierdzenie KLS). Niezależnie Tsteitin podał twierdzenie, które uogólniło KLS i było wyraźnie w formie „każda obliczalna mapa jest obliczalna ciągła”.
Andrej Bauer,
6
Muszę napisać podręcznik - (Google Google Google). Okej, dobrze, masz kadencję. Idź po to!
Jeffε
10
@Tsuyoshi: W pytaniu wykorzystano ustaloną frazę „liczba rzeczywista” bez kwalifikacji. Struktura liczb rzeczywistych jest standardowa. Możesz rozważać inne struktury, ale nie możesz źle interpretować standardowej terminologii.
Andrej Bauer,
21
Technicznie rzecz biorąc, masz rację, słowo „prawdziwy” nie zostało użyte. Ale mylisz się co do definicji liczb rzeczywistych. Innymi słowy: zła matematyka uważa, że ​​liczby rzeczywiste są szczególnym zestawem, który pojawia się na pierwszym miejscu, po którym następuje jakaś struktura. Tak jak definiujemy grupy, pierścienie, przestrzenie topologiczne itp. Pod względem ich struktury, więc powinniśmy definiować obiekty specjalne pod względem ich uniwersalnych właściwości (liczby naturalne to początkowe semiery, liczby całkowite początkowy pierścień, liczby początkowe racjonalne, liczby rzeczywiste .....).
Andrej Bauer,
10

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.xMMϵxMx

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

Shaull
źródło
Nie rozumiem twojej odpowiedzi, czy mógłbyś rozwinąć więcej? Nie rozumiem, jak odnosisz to do problemu zatrzymania, a co ważniejsze, myślę, że nie ma powodu, aby kiedykolwiek się zatrzymywał (nawet jeśli x jest liczbą całkowitą). Mx
dbarbosa
Jak zauważył Tsuyoshi, odpowiedź zależy od reprezentacji i modelu obliczeń. Twoja odpowiedź poprawnie mówi, że jeśli weźmiesz dane wejściowe za obliczalne liczby rzeczywiste podane przez TM obliczające je, równość nie będzie rozstrzygalna. Jest to poprawne, jednak nie jest zbliżone do żadnego modelu stosowanego w praktyce.
Kaveh
2
Rzeczywiście, moja odpowiedź dotyczy oświadczeń przedstawionych w pytaniu, czy to praktyczne, czy nie. @dbarbosa - wyjaśnię: biorąc pod uwagę TM , postępuj zgodnie z konstrukcją w odpowiedzi. Następnie, zakładając sprzeczność, możesz zdecydować, czy wyprowadzona maszyna reprezentuje racjonalność, czy nie. Jeśli jest to racjonalne, oznacza to, że w pewnym momencie M zatrzymał się i przestajemy obliczać liczbę. Z drugiej strony, jeśli jest to irracjonalne, to M się nie zatrzymuje. Wiemy zatem, czy M zatrzymuje się, rozwiązując problem zatrzymania, o którym wiadomo, że jest nierozstrzygalny. MMMM
Shaull,
10

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).

Max
źródło
Dziękuję za odpowiedź. Nie rozumiem nieciągłego => niemożliwego do obliczenia, domyślam się, że użyłeś (prawdopodobnie powszechnie znanego) twierdzenia, którego nie jestem świadomy lub którego nie pamiętam. Czy możesz podać więcej szczegółów na temat tego kroku?
dbarbosa
1
„obliczalny => ciągły” wydaje się być twierdzeniem ludowym - nie mogę znaleźć oryginalnego cytatu. Teoria obliczeń na obiektach nieskończonych i połączenia z topologią są dość dobrze opisane (IMO) w tych slajdach kursu przez Brattkę ( math.uni.wroc.pl/~pkowa/slides/brattka.pdf ). Twierdzenie 2 na slajdach stwierdza, że ​​wszystkie funkcje obliczeniowe w sekwencjach naturali są ciągłe; w połączeniu z Twierdzeniem 12 otrzymuje się wynik dla funkcji innych typów.
Maks.
6

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ą.

Jeffε
źródło
2

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:R{Yes,No}

F(r)={YESrQNOo.w.

jest obliczalny.

rk2nr[k2n,k+12n]n

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

M0n[12n,12n]MMmM[12m,12m]MMNOYESM[12m,12m]MYESM

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

Kaveh
źródło