Liczba obliczalna - Computable number

π można obliczyć z dowolną precyzją, podczas gdy prawie każda liczba rzeczywista nie jest obliczalna.

W matematyce , numery obliczalne są liczbami rzeczywistymi , które mogą być obliczone z dokładnością do dowolnej precyzji przez skończony, kończące algorytmu . Są one znane również jako rekurencyjnych liczb , skutecznych liczb (vanDerHoeven) lub obliczeniowych liczb rzeczywistych lub cyklicznych liczb rzeczywistych .

Równoważne definicje można podać za pomocą funkcji μ-rekurencyjnych , maszyn Turinga lub rachunku λ jako formalnej reprezentacji algorytmów. Liczby obliczalne tworzą rzeczywiste pole zamknięte 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, które zdefiniował Alan Turing w 1936 roku; tj. jako „sekwencje cyfr interpretowane jako ułamki dziesiętne” od 0 do 1:

Liczba obliczalna [to] taka, dla której istnieje maszyna Turinga, która, mając n na swojej początkowej taśmie, kończy się n- tą cyfrą tej liczby [zakodowaną na swojej taśmie].

Kluczowymi pojęciami w definicji są (1), że pewne n jest określone na początku, (2) dla każdego n obliczenie zajmuje tylko skończoną liczbę kroków, po których maszyna wytwarza żądane dane wyjściowe i kończy.

Alternatywna forma (2) – maszyna drukuje kolejno wszystkie n cyfr na swojej taśmie, zatrzymując się po wydrukowaniu n- tego – podkreśla obserwację Minsky’ego: (3) Że za pomocą maszyny Turinga definicja skończona – w formie tabeli maszyny – służy do zdefiniowania potencjalnie nieskończonego ciągu 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ąglania, zwanemu dylematem stolarza, podczas gdy współczesna definicja nie.

Formalna definicja

Liczba rzeczywista a jest obliczalna, jeśli może być aproksymowana przez jakąś obliczalną funkcję w następujący sposób: przy dowolnej dodatniej liczbie całkowitej n funkcja tworzy liczbę całkowitą f ( n ) taką, że: ${\ Displaystyle f: \ mathbb {N} \ do \ mathbb {Z}}$

${\ Displaystyle {f (n) -1 \ nad n} \ leq a \ leq {f (n) +1 \ nad n}.}$

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

• Istnieje obliczalna funkcja, która przy dowolnym dodatnim ograniczeniu błędu wymiernego daje liczbę wymierną r taką, że${\displaystyle \varepsilon}$ ${\displaystyle |ra|\leq \varepsilon.}$
• Istnieje obliczalny ciąg liczb wymiernych zbieżny do takiego, że dla każdego i .${\displaystyle q_{i}}$${\displaystyle a}$${\ Displaystyle | q_ {i}-q_ {i + 1} | <2 ^ {-i} \,}$

Istnieje inna równoważna definicja liczb obliczalnych za pomocą obliczalnych cięć Dedekinda . Obliczeniowy Dedekind cięcie to obliczeniowy funkcji , który po zaopatrzony liczba wymierna jak powraca wejściowych lub , które spełniają następujące warunki: ${\displaystyle D\;}$${\ Displaystyle r}$${\ Displaystyle D (r) = \ operatorname {prawda} \;}$${\ Displaystyle D (r) = \ operatorname {fałsz} \;}$

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

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

${\ Displaystyle (D (R) = \ operatorname {prawda} ) \ klin (D (s) = \ operatorname {fałsz}) \ Rightarrow r < s \;}$

${\ Displaystyle D (r) = \ operatorname {prawda} \ Rightarrow \ istnieje s> r, D (s) = \ operatorname {prawda}. \;}$

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

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

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

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

Liczba zespolona jest nazywany obliczalny, jeżeli jej rzeczywista i urojona są obliczalne.

Nieruchomości

Nie jest przeliczalna

Przypisywanie numeru Gödel do każdej definicji maszyna Turinga produkuje podzbiór tych liczb naturalnych odpowiadających obliczalnych liczb i identyfikuje surjection od do obliczalnych liczb. Istnieje tylko przeliczalnie wiele maszyn Turinga, co pokazuje, że liczby obliczalne są przeliczalne . Zbiór tych liczb Gödla nie jest jednak przeliczalny (i w konsekwencji podzbiory nie są w nim definiowane). Dzieje się tak, ponieważ nie ma algorytmu określającego, które liczby Gödla odpowiadają maszynom Turinga, które wytwarzają obliczalne liczby rzeczywiste. W celu wytworzenia obliczalnej liczby rzeczywistej maszyna Turinga musi obliczyć funkcję całkowitą , ale odpowiadający jej problem decyzyjny jest w stopniu Turinga 0′′ . W konsekwencji nie ma suriektywnej funkcji obliczalnej od liczb naturalnych do liczb rzeczywistych obliczalnych, a argument diagonalny Cantora nie może być użyty konstruktywnie do wykazania niezliczonej ich liczby. ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

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 danego numeru obliczeniowego zasada dobrze zamawiania zapewnia, że istnieje minimalny element , który odpowiada , a zatem istnieje podzbiór składający się z minimalnymi elementami, na które Mapa jest bijection . Odwrotnością tej bijekcji jest wstrzyknięcie do liczb naturalnych liczb obliczalnych, udowadniając, że są one policzalne. Ale znowu ten podzbiór nie jest obliczalny, mimo że obliczalne liczby rzeczywiste same w sobie są uporządkowane. ${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$

Właściwości jako pole

Operacje arytmetyczne na liczbach obliczalnych są same w sobie obliczalne w tym sensie, że ilekroć liczby rzeczywiste a i b są obliczalne, to 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ą faktycznie jednolicie obliczalne ; na przykład istnieje maszyna Turinga, która na wejściu ( A , B , ) wytwarza na wyjściu r , gdzie A jest opisem maszyny Turinga aproksymującym a , B jest opisem maszyny Turinga aproksymującym b , a r jest aproksymacją a + b . ${\displaystyle \epsilon}$${\displaystyle \epsilon}$

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

Obliczalne reals jednak nie tworzą pole obliczalny , ponieważ definicja pola obliczeniowego wymaga skutecznej 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 liczbę . Wtedy nie ma maszyny Turinga, która na wejściu A wyprowadza "TAK", jeśli i "NIE", jeśli Aby zobaczyć dlaczego, załóżmy, że maszyna opisana przez A nadal wyprowadza 0 jako przybliżenia. Nie jest jasne, jak długo trzeba czekać, zanim zdecyduje, że maszyna nigdy nie wygeneruje przybliżenia, które zmusza a do dodatniego. W ten sposób maszyna będzie musiała w końcu odgadnąć, że liczba będzie równa 0, aby uzyskać wynik; sekwencja może później stać się różna od 0. Ten pomysł może być użyty do pokazania, że ​​maszyna jest niepoprawna w niektórych sekwencjach, jeśli oblicza funkcję całkowitą. Podobny problem występuje, gdy obliczalne liczby rzeczywiste są reprezentowane jako cięcia Dedekinda . To samo dotyczy relacji równości: test równości nie jest obliczalny. ${\displaystyle a}$${\displaystyle a>0}$${\displaystyle a\leq 0.}$${\displaystyle \epsilon}$

Chociaż relacja pełnego rzędu nie jest obliczalna, ograniczenie jej do par o nierównych liczbach jest obliczalne. Oznacza to, że istnieje program, który przyjmuje jako dane wejściowe dwie maszyny Turinga A i B przybliżające liczby a i b , gdzie a ≠ b , i wyprowadza czy lub Wystarczy użyć aproksymacji ε tam , gdzie tak jest, przyjmując coraz mniejsze ε (zbliżając się do 0 ), ostatecznie można zdecydować, czy lub${\displaystyle a<b}$${\displaystyle a>b.}$${\displaystyle \varepsilon <|ba|/2,}$${\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 ograniczonego rosnącego, obliczalnego ciągu obliczalnych liczb rzeczywistych nie musi być obliczalną liczbą rzeczywistą (Bridges i Richman, 1987:58). Sekwencja z tą właściwością jest znana jako sekwencja Speckera , ponieważ pierwsza konstrukcja pochodzi od E. Speckera (1949). Pomimo istnienia takich kontrprzykładów, części rachunku różniczkowego i analizy rzeczywistej mogą być rozwijane w dziedzinie liczb obliczalnych, co prowadzi do badania analizy obliczalnej .

Każda liczba obliczalna jest definiowalna , ale nie odwrotnie. Istnieje wiele definiowalnych, nieobliczalnych liczb rzeczywistych, w tym:

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

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 zbiór liczb naturalnych, które reprezentuje (zapisany binarnie i postrzegany jako funkcja charakterystyczna) jest obliczalny.

Każda obliczalna liczba jest arytmetyczna .

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

Cyfry oraz spacje Cantora i Baire'a

Oryginalny papier Turinga zdefiniował liczby obliczalne w następujący sposób:

Liczba rzeczywista jest obliczalna, jeśli jej ciąg cyfr może zostać wytworzony przez jakiś algorytm lub maszynę Turinga. Algorytm pobiera liczbę całkowitą jako dane wejściowe i generuje jako wynik -tą cyfrę rozwinięcia dziesiętnego liczby rzeczywistej.${\displaystyle n\geq 1}$${\ Displaystyle n}$

(Rozszerzenie dziesiętne a odnosi się tylko do cyfr po przecinku).

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

O ile pewne topologiczne własności liczb rzeczywistych nie są istotne, często wygodniej jest zajmować się elementami (w sumie funkcji o wartości 0,1) zamiast liczb rzeczywistych w . Członkowie mogą być identyfikowani za pomocą rozwinięć binarnych dziesiętnych, ale ponieważ rozwinięcia dziesiętne i oznaczają tę samą liczbę rzeczywistą, przedział może być tylko bijektywnie (i homeomorficznie w topologii podzbioru) zidentyfikowany z podzbiorem, który nie kończy się wszystkimi jedynkami. ${\ Displaystyle 2 ^ {\ omega}}$${\displaystyle [0,1]}$${\ Displaystyle 2 ^ {\ omega}}$${\displaystyle.d_{1}d_{2}\ldots d_{n}0111\ldots}$${\displaystyle.d_{1}d_{2}\ldots d_{n}10}$${\displaystyle [0,1]}$${\ Displaystyle 2 ^ {\ omega}}$

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 sensie aproksymacyjnym. Hirst wykazał, że nie ma algorytmu, który przyjmuje jako dane wejściowe opis maszyny Turinga, która wytwarza przybliżenia dla liczby obliczalnej a , a jako dane wyjściowe wytwarza maszynę Turinga, która wylicza cyfry a w sensie definicji Turinga (patrz Hirst 2007) . Podobnie oznacza to, że operacje arytmetyczne na obliczalnych liczbach rzeczywistych nie są efektywne na ich reprezentacjach dziesiętnych, tak jak przy dodawaniu liczb dziesiętnych, w celu uzyskania jednej cyfry może być konieczne spoglądanie dowolnie daleko w prawo, aby określić, czy istnieje przeniesienie do aktualna lokalizacja. Ten brak jednolitości jest jednym z powodów, dla których współczesna definicja liczb obliczalnych używa przybliżeń, a nie rozwinięć dziesiętnych. ${\displaystyle \epsilon}$${\displaystyle \epsilon}$${\displaystyle \epsilon}$

Jednak z obliczeń lub środka teoretycznego punktu widzenia obie konstrukcje i są w zasadzie identyczne, a teoretycy obliczalności często odnoszą się do członków jako liczb rzeczywistych. Chociaż jest całkowicie odłączony , w przypadku pytań dotyczących klas lub losowości praca jest znacznie mniej kłopotliwa . ${\ Displaystyle 2 ^ {\ omega}}$${\displaystyle [0,1]}$${\ Displaystyle 2 ^ {\ omega}}$${\displaystyle [0,1]}$ ${\ Displaystyle 2 ^ {\ omega}}$${\ Displaystyle \ Pi _ {1} ^ {0}}$${\ Displaystyle 2 ^ {\ omega}}$

Elementy z są czasami nazywane również rzeczywistymi i chociaż zawierają homeomorficzny obraz i są całkowicie oderwane, nie są nawet lokalnie zwarte. Prowadzi to do rzeczywistych różnic we właściwościach obliczeniowych. Na przykład spełnienie z kwantyfikatorem free musi być obliczalne, podczas gdy unikatowe spełnienie uniwersalnej formuły może znajdować się dowolnie wysoko w hierarchii hiperarytmetycznej . ${\ Displaystyle \ omega ^ {\ omega}}$${\ Displaystyle \ mathbb {R}}$ ${\ Displaystyle \ omega ^ {\ omega}}$${\ Displaystyle x \ w \ mathbb {R} }$${\ Displaystyle \ forall (n \ w \ omega ) \ phi (x, n)}$${\ Displaystyle \ phi (x, n)}$${\ Displaystyle x \ w \ omega ^ {\ omega}}$

Użyj zamiast prawdziwych

Liczby obliczalne obejmują konkretne liczby rzeczywiste występujące w praktyce, w tym wszystkie liczby rzeczywiste 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 dotyczących liczb rzeczywistych. Naturalnie powstaje pytanie, czy możliwe jest dysponowanie pełnym zbiorem liczb rzeczywistych i używanie liczb obliczalnych dla całej matematyki. Idea ta jest atrakcyjna z konstruktywistycznego punktu widzenia i jest realizowana przez to, co Bishop i Richman nazywają rosyjską szkołą matematyki konstruktywnej.

Aby faktycznie opracować analizę na liczbach obliczalnych, należy zachować pewną ostrożność. Na przykład, jeśli używa się klasycznej definicji ciągu, zbiór liczb obliczalnych nie jest zamykany w ramach podstawowej operacji przyjmowania supremum ciągu ograniczonego (rozważmy na przykład ciąg Speckera , patrz sekcja powyżej). Tę trudność rozwiązuje się, biorąc pod uwagę tylko sekwencje, które mają obliczalny moduł zbieżności . Powstała teoria matematyczna nazywana jest analizą obliczeniową .

Realizacja

Istnieje kilka pakietów komputerowych, które pracują z obliczalnymi liczbami rzeczywistymi, reprezentującymi liczby rzeczywiste jako programy obliczające przybliżenia. Jednym z przykładów jest pakiet RealLib Lambov (2015) .

Zobacz też

• Definiowana liczba
• Funkcja półobliczalna
• Problem transkomputerowy

Bibliografia