Obliczalna liczba

π można obliczyć z dowolną precyzją, podczas gdy prawie każdej liczby rzeczywistej nie da się obliczyć.

W matematyce liczby obliczalne to liczby rzeczywiste , które można obliczyć z dowolną precyzją za pomocą skończonego, kończącego algorytmu . Są one również znane jako liczby rekurencyjne , liczby efektywne lub obliczalne liczby rzeczywiste lub rekurencyjne liczby rzeczywiste . Pojęcie obliczalnej liczby rzeczywistej zostało wprowadzone przez Emile'a Borela w 1912 r., wykorzystując dostępne wówczas intuicyjne pojęcie obliczalności.

Równoważne definicje można podać za pomocą funkcji μ-rekurencyjnych , maszyn Turinga lub rachunku λ jako formalnej reprezentacji algorytmów. Obliczalne liczby tworzą rzeczywiste zamknięte pole i mogą być używane zamiast liczb rzeczywistych do wielu, ale nie wszystkich, celów matematycznych.

Nieformalna definicja na przykładzie maszyny Turinga

Poniżej Marvin Minsky definiuje liczby do obliczenia w sposób podobny do tych zdefiniowanych przez Alana Turinga w 1936 r .; tj. jako „ciągi cyfr interpretowane jako ułamki dziesiętne” między 0 a 1:

Obliczalna liczba [to] taka, dla której istnieje maszyna Turinga, której dane n na jej początkowej taśmie kończy się n- tą cyfrą tej liczby [zakodowanej na jej taśmie].

Kluczowymi pojęciami w definicji są: (1) pewne n jest określone na początku, (2) dla dowolnego n obliczenie obejmuje tylko skończoną liczbę kroków, po których maszyna generuje żądany wynik i kończy działanie.

Alternatywna postać (2) – maszyna kolejno drukuje wszystkie n cyfr na swojej taśmie, zatrzymując się po wydrukowaniu n- tej – podkreśla obserwacja Minsky'ego: (3) Że za pomocą maszyny Turinga skończona definicja – w postaci tablicy stanów maszyny – służy do określenia, czym jest potencjalnie nieskończony ciąg cyfr dziesiętnych.

Nie jest to jednak współczesna definicja, która wymaga jedynie, aby wynik był dokładny z określoną dokładnością. Powyższa nieformalna definicja podlega problemowi zaokrąglenia zwanemu dylematem twórcy stołu, podczas gdy współczesna definicja nie.

Definicja formalna

Liczba rzeczywista a jest obliczalna $,$ można ją przybliżyć jakąś obliczalną funkcją w następujący sposób: biorąc pod całkowitą n , funkcja daje liczbę całkowitą f ( n ) taką, że:

${\ Displaystyle {f (n) -1 \ nad n} \ równoważnik a \ równoważnik {f (n) + 1 \ nad n}.}$

Istnieją dwie podobne definicje, które są równoważne:

• Istnieje obliczalna funkcja, która przy dowolnym dodatnim błędzie wymiernym jest ograniczona $że$ daje liczbę wymierną r taką, ${\ Displaystyle | ra | \ równoważnik \ varepsilon.}$
• Istnieje obliczalna sekwencja $liczb$$,$ do że ${\ Displaystyle | q_ {i} -q_ {i + 1} | <2 ^ {-i} \,}$ dla każdego ja .

Istnieje inna równoważna definicja liczb obliczalnych za pomocą obliczalnych cięć Dedekinda . Obliczalny przekrój Dedekinda $)$ obliczalna funkcja $) =$ = t $mi$ lub ${\ Displaystyle D (r) = \ operatorname {fałsz} \;}$ , spełniając następujące warunki:

${\ Displaystyle \ istnieje rD (r) = \ operatorname {prawda} \;}$

$\ Displaystyle \ istnieje rD (r) =\ operatorname {fałsz} \;}$

${\ Displaystyle (D (r) = \ operatorname {true } )\klin (D(s)=\mathrm {fałsz} )\strzałka w prawo r<s\;}$

${\ Displaystyle D (r) = \ operatorname {prawda} \ Strzałka w prawo \ istnieje s> r, D (s) = \ operatorname {prawda}. \;}$

Przykład podaje program D , który definiuje pierwiastek sześcienny z 3. Zakładając, że jest to zdefiniowane przez: ${\ displaystyle q> 0 \;}$

${\ Displaystyle p ^ {3}<3q ^ {3} \ Strzałka w prawo D (p / q) = \ operatorname {true} \;}$

${\ Displaystyle p ^ {3}> 3q ^ {3} \ Strzałka w prawo D (p / q) = \ operatorname {fałsz}. \;}$

Liczba rzeczywista jest obliczalna wtedy i tylko wtedy, gdy odpowiada jej obliczalny przekrój Dedekinda D. Funkcja D jest unikalna dla każdej obliczalnej liczby (chociaż oczywiście dwa różne programy mogą zapewniać tę samą funkcję).

Liczbę zespoloną nazywamy obliczalną, jeśli jej części rzeczywista i urojona są obliczalne.

Nieruchomości

Nieobliczalnie policzalne

Przypisanie liczby Gödla do $maszyny$ Turinga tworzy podzbiór liczb naturalnych odpowiadających liczbom obliczalnym i identyfikuje $surjekcję$ od liczb . Istnieje tylko policzalnie wiele maszyn Turinga, co pokazuje, że liczby obliczalne są przeliczalne . Zbiór tych liczb Gödla nie jest jednak $przeliczalny$$,$ a co za tym idzie, nie są to również podzbiory są zdefiniowane na jego podstawie). Dzieje się tak, ponieważ nie ma algorytmu określającego, które liczby Gödla odpowiadają maszynom Turinga, które wytwarzają obliczalne liczby rzeczywiste. Aby wytworzyć obliczalną liczbę rzeczywistą, maszyna Turinga musi obliczyć funkcję całkowitą , ale odpowiadający jej problem decyzyjny jest w stopniu Turinga 0′′ . W konsekwencji nie ma surjektywnej obliczalnej funkcji od liczb naturalnych do obliczalnych liczb rzeczywistych, a argumentu Cantora dotyczącego przekątnej nie można konstruktywnie użyć do wykazania niezliczonej liczby z nich.

Podczas gdy zbiór liczb rzeczywistych jest niepoliczalny , zbiór liczb obliczalnych jest klasycznie policzalny , a zatem prawie wszystkie liczby rzeczywiste nie są obliczalne. Tutaj, dla dowolnej liczby obliczalnej $x ,$ zasada dobrego uporządkowania przewiduje, że istnieje minimalny element w $x$ który odpowiada , a zatem istnieje podzbiór składający się z { $}$ minimalnych elementów, na których mapa jest bijekcją . Odwrotnością tej bijekcji jest wstrzyknięcie do liczb naturalnych liczb obliczalnych, co dowodzi, że są one policzalne. Ale znowu ten podzbiór nie jest obliczalny, mimo że same obliczalne liczby rzeczywiste są uporządkowane.

Właściwości jako pole

Operacje arytmetyczne na liczbach obliczalnych same w sobie są obliczalne w tym sensie, że ilekroć liczby rzeczywiste a i b są obliczalne, obliczalne są również następujące liczby rzeczywiste: a + b , a - b , ab i a/b, jeśli b jest niezerowe. Operacje te są w rzeczywistości jednostajnie obliczalne ; na przykład istnieje maszyna Turinga, która na wejściu ( ZA , b , ${\ displaystyle \ epsilon}$ ) wytwarza wynik r , gdzie A jest opisem maszyny Turinga przybliżającej a , B jest opisem maszyny Turinga przybliżającej b , a r jest $_$ a + b .

Fakt, że obliczalne liczby rzeczywiste tworzą ciało , został po raz pierwszy udowodniony przez Henry'ego Gordona Rice'a w 1954 roku.

Obliczalne liczby rzeczywiste nie tworzą jednak pola obliczeniowego, ponieważ definicja pola obliczeniowego wymaga efektywnej równości.

Nieobliczalność zamówienia

Relacja porządku na liczbach obliczalnych nie jest obliczalna. Niech A będzie opisem maszyny Turinga $przybliżającym$ . Wtedy nie ma maszyny Turinga, która na wejściu A wyprowadza „TAK”, jeśli ${\ Displaystyle a> 0}$ i „NIE”, jeśli ${\ Displaystyle a \ leq 0.}$ Aby zobaczyć dlaczego, załóżmy, że maszyna opisana przez A nadal wyprowadza 0 $jako$ . Nie jest jasne, jak długo należy czekać, zanim zdecydujemy, że maszyna nigdy nie wygeneruje przybliżenia, które wymusza dodatnią wartość a . Tak więc maszyna będzie musiała ostatecznie zgadnąć, że liczba będzie równa 0, aby wytworzyć dane wyjściowe; sekwencja może później stać się różna od 0. Pomysł ten można wykorzystać do pokazania, że ​​maszyna jest niepoprawna w niektórych sekwencjach, jeśli oblicza funkcję całkowitą. Podobny problem pojawia się, gdy obliczalne liczby rzeczywiste są reprezentowane jako przekroje Dedekinda . To samo dotyczy relacji równości: test równości nie jest obliczalny.

Chociaż pełna relacja porządku nie jest obliczalna, jej ograniczenie do par nierównych liczb jest obliczalne. Oznacza to, że istnieje program, który pobiera jako dane wejściowe dwie maszyny Turinga $}$${\ displaystyle a <b}$ B aproksymujące liczby $b$ gdzie i wyprowadza, czy $displaystyle a \ neq$ \ lub ${\ Displaystyle a> b.}$$Wystarczy$ użyć , gdzie ${\ Displaystyle \ epsilon <| ba |/2,}$ więc biorąc coraz mniejsze $) ,$ ostatecznie można zdecydować, czy ${\ displaystyle a <b$${\ Displaystyle a> b.}$

Inne właściwości

Obliczalne liczby rzeczywiste nie mają wszystkich właściwości liczb rzeczywistych używanych w analizie. Na przykład najmniejsza górna granica ograniczonej rosnącej, obliczalnej sekwencji obliczalnych liczb rzeczywistych nie musi być obliczalną liczbą rzeczywistą. Sekwencja o tej właściwości jest znana jako sekwencja Speckera , ponieważ pierwsza konstrukcja jest dziełem Ernsta Speckera w 1949 r. Pomimo istnienia takich kontrprzykładów, części rachunku różniczkowego i analizy rzeczywistej można rozwijać w dziedzinie liczb obliczalnych, prowadząc do badania analizy obliczeniowej .

Każda liczba obliczalna jest definiowalna arytmetycznie , ale nie odwrotnie. Istnieje wiele definiowalnych arytmetycznie liczb rzeczywistych, których nie można obliczyć, w tym:

• dowolna liczba, która koduje rozwiązanie problemu zatrzymania (lub dowolnego innego problemu nierozstrzygalnego ) zgodnie z wybranym schematem kodowania.
• Stała Chaitina , która jest rodzajem liczby rzeczywistej, która jest $odpowiednikiem$ problemu zatrzymania.

Oba te przykłady w rzeczywistości definiują nieskończony zbiór definiowalnych, nieobliczalnych liczb, po jednej dla każdej uniwersalnej maszyny Turinga . Liczba rzeczywista jest obliczalna wtedy i tylko wtedy, gdy reprezentowany przez nią zbiór liczb naturalnych (zapisany binarnie i postrzegany jako funkcja charakterystyczna) jest obliczalny.

Zbiór obliczalnych liczb rzeczywistych (jak również każdy policzalny, gęsto uporządkowany podzbiór liczb rzeczywistych obliczalnych bez końców) jest rzędem izomorficzny ze zbiorem liczb wymiernych.

Ciągi cyfr i przestrzenie Cantora i Baire'a

Oryginalna praca Turinga zdefiniowała liczby obliczalne w następujący sposób:

Liczba rzeczywista jest obliczalna, jeśli jej ciąg cyfr może być utworzony przez jakiś algorytm lub maszynę Turinga. Algorytm przyjmuje liczbę całkowitą $dane$ wejściowe i generuje -tą $rozwinięcia$ dziesiętnego liczby rzeczywistej jako dane

(Rozwinięcie dziesiętne a odnosi się tylko do cyfr następujących po przecinku.)

$,$ że ta definicja jest równoważna podanej powyżej definicji . Argument przebiega następująco: jeśli liczba $jest$ obliczalna w sensie Turinga, to jest również obliczalna w sensie jeśli $/\ epsilon)} ,$${\ Displaystyle n> \ log _ {10} ($ 1 $a$ następnie pierwsze n cyfr rozwinięcia dziesiętnego dla a zapewniają a . Na odwrót, wybieramy $a$ liczbę rzeczywistą i generujemy coraz dokładniejsze przybliżenia, aż n- ta cyfra po przecinku jest pewna. To zawsze generuje rozwinięcie dziesiętne równe a , ale może niewłaściwie zakończyć się nieskończoną sekwencją dziewiątek, w którym to przypadku musi mieć skończone (a zatem obliczalne) właściwe rozwinięcie dziesiętne.

${\ Displaystyle [0,1]}$ są istotne, często wygodniej jest zajmować się elementami (całkowita funkcja o wartości 0,1 $)$ zamiast liczb rzeczywistych w . Członków ${\ Displaystyle 2 ^ {\ omega}}$ można zidentyfikować za pomocą binarnych rozwinięć dziesiętnych, ale od rozwinięć dziesiętnych ${\ Displaystyle .d_ {1} d_ {2} \ ldots d_ {n} 0111 \ ldots}$ i ${\ Displaystyle .d_ {1} d_ {2} \ ldots d_ {n} 10}$ oznacza tę samą liczbę rzeczywistą, przedział ${\ Displaystyle [0,1]}$ może $być bijektywnie (i homeomorficznie w topologii$ ) identyfikowany tylko z podzbiorem nie kończącym się na wszystkich jedynkach

Należy zauważyć, że ta właściwość rozwinięć dziesiętnych oznacza, że ​​​​niemożliwe jest skuteczne zidentyfikowanie obliczalnych liczb rzeczywistych zdefiniowanych za pomocą rozwinięcia dziesiętnego i tych zdefiniowanych w $przybliżenia$ . Hirst wykazał, że nie ma algorytmu, który przyjmuje jako dane wejściowe opis maszyny Turinga, która wytwarza $a$ liczby obliczalnej i wytwarza jako dane wyjściowe maszynę Turinga, która wylicza cyfry a w sensie definicji Turinga. Podobnie oznacza to, że operacje arytmetyczne na obliczalnych liczbach rzeczywistych nie działają na ich reprezentacje dziesiętne, jak przy dodawaniu liczb dziesiętnych. Aby wygenerować jedną cyfrę, może być konieczne spojrzenie arbitralnie daleko w prawo, aby określić, czy istnieje przeniesienie do bieżącej lokalizacji. Ten brak jednolitości jest jednym z powodów, dla których współczesna definicja liczb obliczalnych wykorzystuje $.$ zamiast rozwinięć dziesiętnych

Jednak z $teorii$ obliczalności lub $teorii$ miary dwie i zasadniczo Dlatego teoretycy obliczalności często odnoszą się do członków $rzeczywistych$ . Chociaż jest całkowicie odłączony , $w$ przypadku pytań dotyczących $2^{\omega}}$$^ {0}}$ \ ${1}$ .

Elementy ${\ Displaystyle \ omega ^ {\ omega}}$ są czasami nazywane liczbami rzeczywistymi i chociaż zawierają homeomorficzny obraz ${\ Displaystyle \ mathbb {R}}$ , ${\ Displaystyle \ omega ^ {\ omega }}$ nie jest nawet lokalnie zwarty (oprócz tego, że jest całkowicie rozłączony). Prowadzi to do rzeczywistych różnic we właściwościach obliczeniowych. Na przykład satysfakcjonujące ${\ Displaystyle x \ in \ mathbb {R}}$ satysfakcjonujące ${\ Displaystyle \ forall (n \ in \ omega) \ phi (x, n) }$ , z $ω$$}$ \ Displaystyle formuła może zajmować dowolnie wysoką pozycję w hierarchii hiperarytmetycznej .

Użyj zamiast liczb rzeczywistych

Liczby obliczalne obejmują określone liczby rzeczywiste, które pojawiają się w praktyce, w tym wszystkie rzeczywiste liczby algebraiczne , a także e , π i wiele innych liczb przestępnych . Chociaż obliczalne liczby rzeczywiste wyczerpują te liczby rzeczywiste, które możemy obliczyć lub przybliżyć, założenie, że wszystkie liczby rzeczywiste są obliczalne, prowadzi do zasadniczo różnych wniosków na temat liczb rzeczywistych. Naturalnie powstaje pytanie, czy możliwe jest pozbycie się pełnego zestawu liczb rzeczywistych i użycie liczb obliczalnych w całej matematyce. Pomysł ten jest atrakcyjny z konstruktywistycznego punktu widzenia i był realizowany przez to, co Errett Bishop i Fred Richman nazywają rosyjską szkołą matematyki konstruktywnej.

Aby rzeczywiście opracować analizę liczb obliczalnych, należy zachować ostrożność. Na przykład, jeśli użyje się klasycznej definicji ciągu, zbiór liczb obliczalnych nie jest zamknięty w ramach podstawowej operacji polegającej na pobraniu supremumu z ograniczonej sekwencji (na przykład rozważ sekwencję Speckera , patrz sekcja powyżej). Trudność tę rozwiązuje się, biorąc pod uwagę tylko ciągi, które mają obliczalny moduł zbieżności . Powstała w ten sposób teoria matematyczna nazywana jest analizą obliczeniową .

Implementacje arytmetyki dokładnej

Pakiety komputerowe przedstawiające liczby rzeczywiste jako programy obliczające przybliżenia zostały zaproponowane już w 1985 roku pod nazwą „arytmetyka dokładna”. Współczesne przykłady obejmują bibliotekę CoRN (Coq) i pakiet RealLib (C++). Powiązany zakres prac opiera się na wzięciu rzeczywistego programu RAM i uruchomieniu go z liczbami wymiernymi lub zmiennoprzecinkowymi o wystarczającej precyzji, na przykład pakiet iRRAM.

Zobacz też

• Liczba konstrukcyjna
• Definiowalna liczba
• Funkcja półobliczalna
• Problem transkomputacyjny

Notatki

•   Mosty, Douglas; Richman, Fred (1987). Odmiany konstruktywnej matematyki . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-31802-0 .
• Hirst, Jeffry L. (2007). „Reprezentacje liczb rzeczywistych w matematyce odwrotnej” . Biuletyn Polskiej Akademii Nauk, Matematyka . 55 (4): 303–316. doi : 10.4064/ba55-4-2 .
• Lambov, Branimir (5 kwietnia 2015). „RealLib” . GitHub.
•    Minsky, Marvin (1967). „9. Obliczalne liczby rzeczywiste”. Obliczenia: maszyny skończone i nieskończone . Prentice Hall. ISBN 0-13-165563-9 . OCLC 0131655639 .
•   Ryż, Henry Gordon (1954). „Rekurencyjne liczby rzeczywiste” . Proceedings of the American Mathematical Society . 5 (5): 784–791. doi : 10.1090/S0002-9939-1954-0063328-5 . JSTOR 2031867 .
•    Specker, E. (1949). „Nicht konstruktiv beweisbare Sätze der Analysis” (PDF) . Dziennik logiki symbolicznej . 14 (3): 145–158. doi : 10.2307/2267043 . JSTOR 2267043 . S2CID 11382421 . Zarchiwizowane (PDF) od oryginału w dniu 2018-07-21.
• 
    Turinga AM (1936). „O liczbach obliczeniowych, z zastosowaniem do problemu Entscheidungs”. Proceedings of London Mathematical Society . Seria 2 (opublikowana 1937). 42 (1): 230–65. doi : 10.1112/plms/s2-42.1.230 . S2CID 73712 . Turinga AM (1938). „O liczbach obliczeniowych, z zastosowaniem do problemu Entscheidungs: poprawka” . Proceedings of London Mathematical Society . Seria 2 (opublikowana 1937). 43 (6): 544–6. doi : 10.1112/plms/s2-43.6.544 . Liczby obliczalne (i a-maszyny Turinga) zostały wprowadzone w tym artykule; definicja liczb obliczalnych wykorzystuje nieskończone ciągi dziesiętne.
• van der Hoeven, Joris (2006). „Obliczenia z efektywnymi liczbami rzeczywistymi” . Informatyka teoretyczna . 351 (1): 52–60. doi : 10.1016/j.tcs.2005.09.060 .

Dalsza lektura

•   Aberth, Oliver (1968). „Analiza w polu liczb obliczeniowych”. Dziennik Stowarzyszenia Maszyn Komputerowych . 15 (2): 276–299. doi : 10.1145/321450.321460 . S2CID 18135005 . Artykuł ten opisuje rozwój rachunku różniczkowego nad obliczalnym polem liczbowym.
•   Biskup, Errett; Mosty, Douglas (1985). Analiza konstruktywna . Skoczek. ISBN 0-387-15066-8 .
•   Stoltenberg-Hansen, V.; Tucker, JV (1999). „Obliczalne pierścienie i pola” . W Griffor, ER (red.). Podręcznik teorii obliczalności . Elsevier. s. 363–448. ISBN 978-0-08-053304-9 .
•   Weihrauch, Klaus (2000). Analiza obliczeniowa . Teksty z informatyki teoretycznej . Skoczek. ISBN 3-540-66817-9 . §1.3.2 wprowadza definicję przez zagnieżdżone sekwencje przedziałów zbieżne do pojedynczej liczby rzeczywistej. Inne oświadczenia zostały omówione w §4.1.
• Weihrauch, Klaus (1995). Proste wprowadzenie do analizy obliczeniowej . Fernuniv., Fachbereich Informatik.