Na ile rzeczywiste są liczby rzeczywiste

Na ile rzeczywiste są liczby rzeczywiste

Gregory Chaitin

tłumaczenie z języka angielskiego lion137

[Od tłumacza. Esej pochodzi z “Thinking about Godel and Turing Essays on Complexity,

1970 - 2007”. Dokonałem minimalnych skrótów materiału, bez straty dla sensu rozważań - czym są liczby rzeczywiste.]

1.Wstęp

Fizycy eksperymentalni wiedzą, jak trudno wykonać dokładny pomiar. Żadna wielkość fizyczna nie została, jak dotąd zmierzona z dokładnością większą niż do 15-go miejsca po przecinku. Matematycy, jednak, snują rozważania o nieskończenie dokładnych liczbach. Ale jednak w czystej matematyce pojęcie liczby rzeczywistej jest wyjątkowo problematyczne.

Przedstawimy podobieństwa i różnice dwóch równoległych historycznie podejść:

1. diagonalny i probabilistyczny dowód, że liczby rzeczywiste są nieprzeliczalne;

2. diagonalny i probabilistyczny dowód na istnienie nieobliczalnych liczb rzeczywistych.

Obydwie te historie otwierają szczelinę w podstawach matematyki. W pierwszym przypadku mamy do czynienia ze słynnym paradoksem Ricarda (1905),Borela “wszystko - wiedzącą” liczbą, z faktem, również badanym przez Emila Borela, że większość liczb rzeczywistych jest niemożliwa do nazwania (unnamable), co było tematem jego książki [Borel 1952], ostatniej opublikowanej w wieku 81 lat [James 2002].

Niepokojące cechy drugiego przypadku to nierozwiązywalność problemu stopu [Turing 1936], fakt, że większość liczb rzeczywistych jest nieobliczalna, i ostatni, ale nie mniej ważny, problem stopu Ω, liczby nieredukowalnie złożonej (algorytmicznie losowej) i maksymalnie niepoznawalnej, dramatycznie ukazującej ograniczenia naszych rozumowań [Chaitin, 2005].

W dodatku do tych matematyczno-duchowych poszukiwań w dziedzinie liczb rzeczywistych, niektórzy fizycy zaczęli podejrzewać, że wszechświat jest dyskretny [Smolin, 2000], a nawet, że jest gigantycznym komputerem [Fredkin, 2004, Wolfram, 2002]. Będzie interesujące zobaczyć, jak daleko zaprowadzi nas analogia “informacyjnego wszechświata” czy “informacyjnej fizyki”.

Nota bene: Dla uproszczenia w dalszym ciągu tej pracy, przez liczbę rzeczywistą, będziemy rozumieć liczbę z przedziału od 0 do 1. W związku z tym, identyfikujemy liczbę rzeczywistą z nieskończonym ciągiem cyfr albo bitów po punkcie dziesiętnym lub dwójkowym.

2. Reakcje na Teorię Zbiorów Cantora. Paradoksy Teorii Mnogości

Teoria zbiorów nieskończonych Cantora, rozwinięta pod koniec XIX stulecia, była zdecydowanym postępem matematyki, ale była też pełna prowokujących konsekwencji i obfita w paradoksy. Jedną z pierwszych książek wybitnego francuskiego matematyka Emila Borela (1871 - 1956) były jego Le ̧ons sur la Th ́orie des Fonctions [Borel 1950], oryginalnie wydane w 1898 roku z podtytułem principes de la ́ la th ́orie des ensembles en vue des applications a la th ́orie des fonctions.

Była to jego pierwsza książka promująca Teorię Zbiorów Cantora, Borel, jednakże, miał poważne wątpliwości o pewnych aspektach teorii Cantora, które dodawał do późniejszych wydań jego książki. Jej wersja końcowa została wydana przez Gauthier - Villars w 1950 roku. To ta którą posiadam i jest to skarbnica interesujących wiadomości historycznych, matematycznych i filozoficznych.

Jedną z najistotniejszych idei Cantora było pokazanie różnicy między przeliczalnymi, nieskończonymi zbiorami, takimi jak zbiór liczb naturalnych czy wymiernych, a dużo liczniejszymi nieprzeliczalnymi zbiorami nieskończonymi, jak zbiór liczb rzeczywistych czy zbiór punktów płaszczyzny lub przestrzeni. Borel, który miał tendencje konstruktywistyczne, dużo pewniej czuł się posługując się zbiorami przeliczalnymi, niż nieprzeliczalnymi. A jednym z kluczowych, omawianych przez Borela, rezultatów Cantora był jego dowód na to, że liczby rzeczywiste są nieprzeliczalne, t.j. nie istnieje jedno - jednoznaczne odwzorowanie zbioru liczb rzeczywistych na zbiór liczb naturalnych. Udowodnię to dwoma sposobami.

2.1 Argument przekątniowy Cantora. Liczby rzeczywiste są niepoliczalne.

Dowód Cantora jest dowodem reductio ad absurdum.

Załóżmy, przeciwnie do naszej tezy, że możemy wypisać listę wszystkich liczb rzeczywistych (z przedziału od zero do jeden), w pierwszej linijce pierwsza liczba w drugiej druga, etc. Niech d(i, j) będzie j - tą cyfrą w rozwinięciu dziesiętnym i - tej liczby rzeczywistej na naszej liście. Rozważmy liczbę rzeczywistą r, której k - tą cyfrą jest 4, jeśli d(k, k) = 3, a 3 w przeciwnym przypadku. Innymi słowy, tworzymy r biorąc wszystkie cyfry na przekątnej listy wszystkich liczb i zmieniając je.
Liczba rzeczywista r różni się od i - tej liczby rzeczywistej na naszej, jak założyliśmy na początku, kompletnej liście, ponieważ jej i - ta cyfra inna. Zatem nasza pierwotna lista nie może być kompletna, dlatego też liczby rzeczywiste są nieprzeliczalne. Q. E. D.
Nota bene: Najdelikatniejszym punktem dowodu jest uniknięcie takiej liczby r, która ma od pewnego momentu do nieskończoności same zera lub dziewiątki, upewnienie się, że posiadamy liczbę, która ma k - tą cyfrę różną od k - tej cyfry k - tej liczby rzeczywistej na naszej liście, gwarantuje, że liczba r jest różna od k - tej liczby z listy. W ten sposób omijamy problem niejednoznaczności reprezentacji dziesiętnej liczb.

2.2 Dowód alternatywny: Dowolny przeliczalny zbiór liczb rzeczywistych ma miarę zero.

Teraz pokażemy radykalnie różny dowód faktu, że liczby rzeczywiste są niepoliczalne. Dowód, który znam pochodzi z [Courant & Robbins, 1947], został prawdopodobnie odkryty przez Borela, gdyż użyte jest w nim matematyczne pojęcie miary, odkryte przez Borela i później dopracowane przez jego ucznia Lebesgue, któremu zazwyczaj teraz przypisuje się to osiągnięcie.

Teoria miary i teoria prawdopodobieństwa, to tak naprawdę ta sama teoria - to tylko dwie nazwy tego samego pojęcia. Borel interesował się technicznymi, matematycznymi i również wieloma ważnymi praktycznymi zastosowaniami jego teorii, które omawiał w wielu swych książkach.

Załóżmy, że mamy daną liczbę rzeczywistą ε > 0, którą możemy uczynić dowolnie małą. Rozważmy znowu, hipotetycznie kompletną, listę wszystkich liczb rzeczywistych, ułożonych w ciąg, pierwsza liczba, druga, etc. Pokryjmy każdą z nich przedziałem, weźmy długość przedziału do pokrycia i - tej liczby równą ε/2ⁱ Całkowita długość przedziałów pokrywających wszystkie liczby rzeczywiste, wynosi:

ε/2 + ε/4 + ... ε/2ⁱ + … = ε

i może być, zgodnie z założeniem, dowolnie mała.
Inaczej, dowolny, przeliczalny zbór liczb rzeczywistych jest miary zero i jest tzw. zbiorem zerowym tzn. ma prawdopodobieństwo zerowe, jest infinitezymalnym podzbiorem zbioru liczb rzeczywistych. Q. E. D.
Poznaliśmy dwa fundamentalnie różne sposoby pokazania, że liczby rzeczywiste są nieskończenie bardziej liczne niż liczby naturalne, tzn. zbiór wszystkich liczb rzeczywistych jest nieskończonością wyższego rzędu niż liczb naturalnych.

2.3 Paradoks Ricardo: Diagonalizacja po wszystkich wyrażalnych liczbach rzeczywistych →wyrażalne, niewyrażalne liczby rzeczywiste

Zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny, zbiór wszystkich możliwych tekstów w języku, np. angielskim lub francuskim jest przeliczalny, i, w związku z tym, przeliczalny jest również zbiór wszystkich możliwych definicji matematycznych i wszystkich możliwych pytań w matematyce, ponieważ formułowane mogą one być tylko wewnątrz jakiegoś języka, dając co najwyżej przeliczalny zbiór możliwości. Mamy więc za dużo liczb, a za mało tekstów, żeby je wyrazić.

Pierwszy, zauważył tę trudność Jules Richard w 1905 roku, a sposób, w jaki ją wyraził jest znany teraz, jako paradoks Ricardo.

Jak to działa. Ponieważ wszystkie możliwe teksty w języku francuskim (Ricardo był Francuzem) mogą być ułożone, zgodnie z porządkiem alfabetycznym, w ciąg, pierwszy tekst, drugi, etc., można w takim razie diagonalizować po wszystkich możliwych liczbach rzeczywistych, które mogą zostać nazwane lub zdefiniowane po francusku i otrzymać w ten sposób liczbę rzeczywistą, której nie ma w naszym ciągu, więc jest ona niewyrażalna. Jednakże, właśnie wskazaliśmy, jak ją zdefiniować lub nazwać!

Innymi słowy, paradoksalna liczba rzeczywista Ricarda różni się od każdej liczby, która może być zdefiniowana w języku francuskim, jednakże może być zdefiniowana, przez pokazanie w szczegółach, jak zaadoptować metodę diagonalizacji Cantora do ciągu wszystkich możliwych definicji indywidualnych liczb rzeczywistych w języku francuskim!

Ależ to kłopotliwe! Oto liczba rzeczywista, która jednocześnie może być i nie może być nazwana używając dowolnego tekstu z języka francuskiego.

2.4 Wszystko - wiedząca liczba Borela

Możliwość ułożenia w ciąg wszystkich możliwych tekstów danego języka to silne narzędzie, i było badane przez Borela w 1927 roku [Tasić 2001, Borel, 1950], w związku ze zdefiniowaniem liczby, która może odpowiedzieć na każde pytanie typu tak/nie!

Wystarczy, zwyczajnie zapisać ją w formie binarnej i użyć jej n - tego bitu do odpowiedzi na n - te pytanie w języku francuskim.

Borel mówi o tej liczbie z ironią. Daje do zrozumienia, że jest to nielegalna, nienaturalna, sztuczna, “nie- rzeczywista” liczba rzeczywista, i, że nie ma żadnego powodu, aby wierzyć w jej istnienie.[...]

2.5 “Niedostępne liczby” Borela: Większość liczb rzeczywistych jest, z prawdopodobieństwem równym 1 niewyrażalna

Credem Borela, często przez niego powtarzanym, było to, że liczba rzeczywista jest prawdziwa jedynie wtedy, gdy może być w sposób jednoznaczny zdefiniowana, przy użyciu skończonej ilości słów[Borel, 1960]. Tylko to jest prawdziwe, co może być nazwane i wyspecyfikowane, jako unikalny obiekt matematyczny. Aby to uczynić musimy koniecznie użyć jakiegoś szczególnego języka, np., francuskiego. Jakikolwiek wybierzemy język będzie on zawierał jedynie przeliczalną, nieskończoną liczbę tekstów (gdyż mogą być one ułożone w ciąg rosnący zgodnie z długością napisów, a pomiędzy napisami o takiej samej długości wprowadzamy porządek alfabetyczny).

To ma niszczące konsekwencje, gdy mamy tylko przeliczalną nieskończoność “dostępnych” liczb rzeczywistych, a, jak widzieliśmy w Sekcji 2.2, zbiór dostępnych liczb rzeczywistych ma miarę zero.

W opinii Borela, większość, z prawdopodobieństwem równym 1, liczb rzeczywistych jest matematyczną fantazją, ponieważ nie ma sposobu, na jednoznaczne ich zdefiniowanie. Większość liczb jest nam niedostępna i nigdy nie będzie dostępna poprzez żadne przekonujące narzędzie matematyczne, ponieważ jakichkolwiek narzędzi byśmy nie użyli zawsze mogą one być wyrażone w języku, np, francuskim , i dlatego możemy indywidualnie “dotknąć jedynie przeliczalny zbiór liczb, zbiór liczb rzeczywistych miary zero, infinitezymalny podzbiór zbioru wszystkich liczb rzeczywistych.

Wybierzmy losowo dowolną liczbę rzeczywistą, prawdopodobieństwo, że jest ona dostępna wynosi zero, i nigdy nie będzie nam dostępna jako indywidualny obiekt matematyczny.

3. Historia Się Powtarza: Teoria Obliczeń i Ograniczające Ją Meta - Twierdzenia

To był ekscytujący rozdział z historii idei, czyż nie! Ale opowieść idzie naprzód, zainteresowanie ludzkości rozszerza się, jak osoby studiującej duży obraz.

Idea komputera kompletnie zmieniła sytuację, komputer jako pojęcie matematyczne, nie urządzenie, choć teraźniejsza wszechobecność komputerów jakoś bardzo nie przeszkadza. Wyróżnianie pojedynczej osoby jest, na ogół, nie fair, ale w moim zdaniem kluczowym momentem w rozwoju komputerów była publikacja Alan Turinga z 1936 roku “On computable numbers” , a faktycznie Turing odnosi się do obliczalnych liczb rzeczywistych. [...]

Historia powtarza się i przetwarza idee z Sekcji 2. Tym razem naszym językiem będzie sztuczny formalny język komputerowych programów i dowodów w formalnych aksjomatycznych systemach. Nie będziemy analizować tekstów w językach naturalnych jak polski czy angielski. Tym razem nie uzyskamy paradoksów, zamiast nich meta - teorię i twierdzenia ograniczające, pokazujące granice obliczalności i formalnego, aksjomatycznego podejścia. W aktualnej formie, w jakiej prezentujemy je teraz, idee z Sekcji 2 definitywnie stają się wyrazistsze.

Z języków formalnych można wyeliminować paradoksy, ale płaci się za to pewną cenę. Naturalne języki zawierają paradoksy, ale są otwartymi, rozwijającymi się systemami. Sztuczne języki są zamkniętymi systemami, podatnymi na twierdzenia je ograniczające. Unikasz paradoksów, ale zostajesz z martwym korpusem!

Następująca tablica symbolizuje zmiany(przesunięcie paradygmatu):

• Języki naturalne → Języki formalne.
• Pewne zdanie jest prawdziwe → Pewne zdanie jest tezą danego systemu formalnego.
• Zdefiniowanie liczby rzeczywistej → Obliczenie jej bit po bicie.
• Liczba słów potrzebna, aby cos nazwać → Rozmiar w bitach najmniejszego programu do obliczenia tego czegoś(złożoność obliczeniowa).
• Lista wszystkich możliwych tekstów francuskich → Lista wszystkich możliwych programów, lub
• Lista wszystkich mozliwych tekstów francuskich → Lista wszystkich możliwych dowodów.
• Paradoksy → Meta - twierdzenia.

Przeanalizujmy Sekcję 2 jeszcze raz. Najpierw zbadamy dwa różne dowody na niepoliczalność zbioru liczb rzeczywistych: dowód z użyciem argumentu przekątniowego i dowód z zastosowaniem teorii miary. Nastepnie wykażemy, jak z paradoksu Ricarda uzyskać nierozwiązywalność problemu stopu. Na koniec przedyskutujemy prawdopodobieństwo stopu Ω [Liczba rzeczywista, która reprezentuje prawdopodobieństwo tego, że losowo skonstruowany program komputerowy się zatrzyma. Przyp. tłumacza], która, w skrócie, pełni taką samą rolę, jak, omówiona wcześniej “wszystko wiedzaca” liczba Borela.

3.1. Diagonalizacja Turinga po wszystkich obliczalnych liczbach rzeczywistych → nieobliczalna liczba rzeczywista.

Ziór wszystkich możliwych programow komputerowych jest przeliczalny, dlatego zbiór wszystkich obliczalnych liczb rzeczywistych też jest przeliczalny, a diagonalizacja po wszystkich obliczalnych liczbach rzeczywistych natychmiastowo daje liczbe nieobliczalną. Q. E. D.

Przeprowadźmy ten dowód dokładniej.

Zróbmy listę wszystkich możliwych programów komputerowych. Posortujmy je według rozmiaru, a te o równych rozmiarach uporządkujmy alfabetycznie. Najprościej zrobić to ze wszystkimi możliwymi znakami, które mogą być utworzone ze skończonej ilości, jaką zawiera jezyk programowania, nawet jeśli większość z nich będzie niepoprawna składniowo.

Aby zdefiniować nieobliczalną liczbę diagonalną 0 < r < 1, rozważmy k - ty program z naszej listy. Jeśli jest niepoprawny syntaktycznie lub k - ty program nigdy nie daje na wyjściu k -tej cyfry lub jeśli k - tą cyfrą na wyjściu k - tego programu nie jest 3, ustawmy 3 jako k - tą cyfrę r. W przeciwnym przypadku, jeśli k - tą cyfrą na wyjściu k - tego porogramu jest 3, ustawmy 4, jako k - tą cyfrę r.

To r nie może być obliczalne, ponieważ jego k - ta cyfra różni się od k - tej cyfry obliczanej przez k - ty program na naszej liście, jeśli taki istnieje. To dowodzi, że istnieją nieobliczalne liczby rzeczywiste, liczby, które nie mogą być wyliczone bit po bicie przez żaden program komputerowy.

3.2 Dowód alternatywny: Liczby rzeczywiste są nieobliczalne z prawdopodobieństwem 1

W skrócie, zbiór programów komputerowych jest przeliczalny, co implikuje, że zbiór obliczalnych liczb rzeczywistych jest przeliczalny, dlatego też, zgodnie z 2.2, jest miary zero. Q.E.D.

Zwolnijmy trochę, rozważmy znowu k - ty program komputerowy. Jeśli jest niepoprawny składniowo lub nie daje w wyniku liczby rzeczywistej pomińmy go. Jeśli daje na wyjściu liczbę rzeczywistą, pokryjmy ją odcinkiem o długości ε/2^k. Całkowita długość odcinków pokrywających jest mniejsza niż , które możemy uczynić dowolnie małym, i obliczalne liczby rzeczywiste tworzą zbiór zerowy.

Inaczej, prawdopodobieństwo, że trafimy na obliczalną liczbę rzeczywistą wynosi zero, a prawdopodobieństwo, że na nieobliczalną 1.

Co, jesli dopuścimy silnie niekonstruktywne metody, a nie tylko progrmy komputerowe do konstrukcji liczb rzeczywistych? Argument z Sekcji 2.5, przeprowadzony w nowych ramach, dalej pozostaje w mocy. Większośc liczb rzeczywistych dalej pozostaje niewyrażalna z prawdopodobieństwem 1[Chaitin, 2005].

3.3. Problem stopu Turinga: Żaden algorytm nie rozwiąże problemu stopu; nie da się go rozwiązać w ramach żadnej formalnej, aksjomatycznej, teorii

Paradoks Ricarda - nazwanie nienazywalnej liczby rzeczywistej. Precyzyjniej, jest to diagonalizacja po wszystkich unikalnie zdefiniowanych w języku francuskim liczb rzeczywistych, aby uzyskać niezdefiniowaną wcześniej liczbę. Co z tego wynika w naszym nowym kontekście, gdzie nazywamy liczby obliczając je?

Powroćmy do użycia przez Turinga argumentu przekątniowego w 3.1. W Sekcji 3.1 skonstruowaliśmy nieobliczalną liczbę rzeczywistą r. Musi ona być nieobliczalna ze względu na konstrukcję. Jednakże, jak to było w przypadku paradoksu Ricarda, wyglądało by na to, że podaliśmy procedurę do obliczenia diagonalnej liczby rzeczywistej r bit po bicie. Jak ta może się nie udać? Co mogło pójść źle?

Odpowiedź jest następująca: Jedynby nieobliczalny krok, jaki musi być wykonany, to ustalenie czy k - ty komputerowy program kiedykolwiek da na wyjściu k - tą cyfrę. Gdybyśmy mogli to zrobić, to moglibyśmy precyzyjnie obliczyć nieobliczalną liczbę rzeczywistą r z 3.1.

Inaczej, podrozdział 3.1 tak naprawdę dowodzi, że nie istnieje algorytm do ustalenia czy k - ty program komputerowy, kiedykolwiek da na wyjściu k - tą cyfrę.

I to jest szczególny przypadek nazywany problemem stopu Turinga, w tej sytuacji jest pytanie czy czekać czy nie na zakończenie obliczeń k - tej liczby. W przypadku ogólnym jest kwestia czy program komputerowy kiedykolwiek się zatrzyma.

Algorytmiczna nierozwiązywalność problemu stopu jest wyjątkowo zasadniczym meta - twierdzeniem. Dużo silniejszym niż słynne twierdzenie Godla o niezupełności z 1931 roku. Dlaczego? Ponieważ w swojej pracy z 1936 roku, pokazał jak natychmiast uzyskać niezupełność z rozwiązania problemu stopu.

Formalna aksjomatyczna matematyczna teoria (FAMT) składa się ze skończonego zbioru aksjomatów, i skończonego zbioru reguł wynikania, do wydedukowania konsekwencji tych aksjomatów. Patrząc w dużym uproszczeniu, to co się liczy to istnienie algorytmu generującego wszystkie możliwe twierdzenia, wszystkie możliwe konsekwencje aksjomatów, jedno po drugim, systematycznie stosując reguły wynikania w każdy możliwy sposób. To jest to, co w rzeczywistości nazywamy przeszukiwaniem wszerz(raczej niż przeszukiwanie w głąb) drzewa, drzewo to drzewo wszystkich możliwych dowodów.

Tak więc, jak argumentuje Turing w 1936, jeśli byłaby FAMT, która zawsze pozwalała by nam sprawdzic czy dany program komputerowy się zatrzyma, to znaczyłoby to, że tak naprawdę mamy do tego algorytm. Wystarczyło by przeszukać wszystkie możliwe dowody, aż do znalezienia dowodu, że dany program się zatrzyma albo dowodu, że obliczenia nigdy się nie zakończą.

Nieobliczalnośc jest bardziej fundamentalna niż niezupełnośc. Niezupełnośc jest natychmiastową konsekwencją nieobliczalności. Ale nie na odwrót. Pojęcie niekompletności nie zawiera pojęcia nieobliczalności.

Teraz przejdźmy do jeszcze bardziej irytującego, ograniczającego meta - twierdzenia. Rozważymy prawdopodobieństwo stopu Ω [Chaitin, 2005], które można, w aktualnym kontekście, porównać do “wiedzącej wszystko” liczby rzeczywistej Borela(Podrozdział 2.4).

3.4. Nieredukowalna złożoność, idealna losowość, maksymalna niepoznawalność: Prawdopodobieństwo stopu Ω

Z czego wywodzi się prawdopodobieństwo stopu? Cóż naszą motywacją jest kontrast między 3.1, a 3.2. Sekcja 3.1 ma się do 3.2 tak, jak problem stopu do prawdopodobieństwa stopu! Inaczej mówiąc, fakt, że znaleźliśmy łatwiejszy dowód na pokazanie istnienia nieobliczalnych liczb rzeczywistych używając argumentu prawdopodobieństwa, sugeruje, aby przyjrzeć się bliżej prawdopodobieństwu, że wybrany losowo program się zatrzyma, zamiast rozważać programy indywidualnie, jak to uczynił Turing w pracy z 1936.

Formalnie, prawdopodobieństwo stopu Ω jest zdefiniowane następująco:

0 < Ω_n ≣ Σ2^{-(rozmiar p w bitach)} < 1

gdzie sumowanie odbywa się po wszystkich zatrzymujących się programach p

Aby uniknąć rozbieżności tej sumy, ważne jest, aby programy p były samoograniczone (tzn. żadne rozszeżenie poprawnego programu nie jest poprawnym programem; patrz [Chaitin, 2005]).

Ciekawym faktem o Ω jest to, że zachowuje się ona jak skompresowana wersja “wszystko - wiedzącej” liczby rzeczywistej Borela. Poznanie pierwszych n bitów liczby Borela, pozwala nam odpowiedzieć na pierwszych n tak/nie pytań z języka francuskiego. Znając pierwsze n bitów Ω możemy rozwiązać problem stopu dla programów wszystkich p, aż do rozmiaru w bitach n. To jest, n bitów Ω mówi nam czy każdy z programów p, aż do rozmiaru n się zatrzyma. (Widzicie jak?) To jest ogromna ilość informacji!

W rzeczywistości w Ω zakodowana tak duża ilość informacji, że potrzeba FAMT o dokładnie n - bitach, do wypisania n bitów Ω! Innymi słowy, Ω jest jest nieredukowalną informacją matematyczną, jest to miejsce gdzie wnioskowanie matematyczne jest kompletnie bezsilne. Bity Ω są faktami matematycznymi, które mogą być udowodnione, ale tylko w sposób dodawania ich kolejno, jako nowe aksjomaty! Mówię, jak trudno jest udowodnić takie twierdzenia, jak:

“piątym bitem Ω jest 0”

i

“dziewiątym bitem Ω jest 1”

lub inne.
Aby udowodnić, że Ω jest obliczeniowo, a więc i logicznie nieredukowalna, potrzeba teorii o złożoności programów, którą ja nazywam Algorytmiczną Teorią Informacji (AIT) [Chaitin, 2005]. Kluczową ideą AIT jest mierzenie złożoności czegoś, jako ilości bitów jaką ma najmniejszy program komputerowy do obliczenia tego. To jest ulepszona wersja pomysłu Borela [Borel, 1960] definiowania złożoności liczby rzeczywistej, jako ilości słów potrzebnej do jej nazwania.

Najistotniejszym faktem, udowodnionym o Ω w AIT jest:

H(Ωn ) ≥ n - c.

To jest.,

(napis Ωn składający się z pierwszych n bitów Ω)

ma złożoność (Złożoność Kołmogorowa, przyp. tłum.) lub “entropię algorytmiczną H” większą lub równą
n - c. Gdzie c jest stałą, a mówimy o rozmiarze w bitach samoograniczających się programów.

Inaczej, każdy samoograniczony program obliczający pierwsze n bitów Ω będzie miał długość co najmniej n - c bitów.

Nieredukowalna sekwencja bitów Ω to miejsce gdzie prawda matematyczna nie absolutnie żadnego wzoru, ani struktury umożliwiającej jej wykrycie. To miejsce gdzie prawda ma maksymalną możliwą entropię - miejsce gdzie, w pewnym sencie, Bóg gra w kości.

Dlaczego mamy wierzyć w istnienie liczb rzeczywistych, jeśli większość z nich jest nieobliczalna? Dlaczego mamy wierzyć w istnienie liczb, z których większość, jak się okazuje, jest maksymalnie niepoznawalna[Chaitin, 2005], jak Ω?[...]

Bibliografia:

Borel, E. [1950] Lecons sur la Theorie des Fonctions (Gabbay, Paris) str. 161, 275.

Borel, E. [1952] Les Nombres Inaccessibles (Gauthier - Vil lars, Paris) str. 21.

Borel, E. [1960] Space and Time (Dover, Mineola str. 212-214.

Chaitin G. [2005] Meta Math! (Pantheon, New York).

Copeland B.J. [2004] The Essential Turing (Clarendon Press, Oxford).

Courant, R. & Robbins, H. [1947] What is Mathematics? (Oxford University Press, New

York)

Fredkin, E. [2004] http://digitalphilosophy.org.

James, I. [2002] Remarkable Mathematics (Cambridge University Press, New York)

Smolin, L. [2000] Three Roads To Quantum Gravity (Weidenfeld & Nicholson, London)

Tasic, V. [2001] Mathematics and the Roots of Postmodern Thought (Oxford University

Press)

Wolfram, S. [2002] A New Kinds of Science (Wolfram Media, Champaign).