Monday 27 February 2012

Szkic Dowodu Twierdzenia Gödla

WSTĘP

[Praca ta jest prawie dokładnie odtworzonym pierwszym rozdziałem Gödel’s Incompletness Theorems Raymonda Smullyana, podane są tu ogólne założenia dla rozważanych twierdzeń i dowody niezupełności bez wyspecyfikowania dane go języka. W szczególności, nie pokazałem, jak wyrazić (P~)* w językach które rozważamy (a zrobił to Gödel w swojej słynnej pracy z 1931 roku. Jednakże, ostatnie twierdzenie tekstu jest udowodnione, więc można powiedzieć, że po przeczytaniu rozumiemy argument Gödla. W dalszych częściach przedstawię szczegółowy dowód dla danego języka (Arytmetyki Peano z Potęgowaniem), będący jednocześnie najprostszym znanym dowodem niezupełności.
Autor: lion137
]

1. Ogólne formy Twierdzeń Gödla i Tarskiego

Języki do których ma zastosowanie Twierdzenie Gödla muszą zawierać co najmniej:
1. Przeliczalny zbiór ℰ, którego elementy nazywamy wyrażeniami.
2. Podzbiór 𝓢 zbioru ℰ którego elementy nazywamy zdaniami języka 𝓛.
3. Podzbiór 𝓟 zbioru 𝓢, którego elementy to zdania dowodliwe w 𝓛.
4. Podzbiór 𝓡 zdań , którego elementy nazywa się zdaniami niedowodliwymi.
5. Zbiór 𝓗 wyrażeń, którego elementy nazywamy predykatami [Gödel we wstępie do swej pracy nazywa je nazwami klas (class names), można pomyśleć o każdym predykacie 𝓗, jako o nazwie pewnego zbioru liczb naturalnych].
6. Funkcja 𝜱, która przyporządkowuje każdemu wyrażeniu E, i każdej liczbie naturalnej n wyrażenie E(n). Funkcja ta jest potrzebna, aby spełnić warunek, że dla każdego predykatu H i dla każdej liczby naturalnej n, wyrażenie H(n) jest zdaniem. [Nieformalnie, zdanie H(n) stwierdza, że liczba n należy do zbioru nazywanego przez H.]
W pierwszym dowodzie niezupełności, jaki podamy dla danego systemu 𝓛, użyjemy podstawowego pojęcia, które precyzyjnym uczynił Alfred Tarski [1936], tj., pojęcia zdania prawdziwego (zdefiniowanego nieco inaczej niż dowodliwość w systemie).
7. Zbiór 𝓣, zdań, którego elementy nazywa się zdaniami prawdziwymi języka𝓛.

Wyrażalność dla 𝓛. Przy definiowaniu wyrażalności w języku bierzemy pod uwagę zbiór zdań prawdziwych, ale nie rozważamy zbiorów 𝓟, ani 𝓡.
Słowo liczba będzie znaczyć, w dalszej części tekstu liczba naturalna. Powiemy, że predykat H jest prawdziwy dla liczby n lub, że n spełnia H, jeśli H(n) jest zdaniem prawdziwym (tj., elementem 𝓣). Przez set wyrażany przez H, rozumiemy zbiór wszystkich n spełniających H. Stąd, dla każdego zbioru liczbowego A, H wyraża ten zbiór, wtedy i tylko wtedy gdy, dla każdej liczby n:

H(n) ϵ 𝓣 ↔ n ϵA.

Definicja. Zbiór A nazywamy wyrażalnymi lub nazywalnym w 𝓛 jeśli A jest wyrażane przez jakiś predykat w 𝓛.
Ponieważ w 𝓛 jest przeliczalnie wiele wyrażeń, dlatego też jest tylko przeliczalnie wiele predykatów. Ale z dobrze nam znanego twierdzenia Cantora, mamy nieprzeliczalnie wiele zbiorów liczb naturalnych. Dlatego nie każdy zbiór liczb jest wyrażalny w 𝓛.

Definicja. System 𝓛 nazywamy poprawnym, jeśli każde dowodliwe zdanie jest prawdziwe, a każde niedowodliwe jest fałszywe (nie prawdziwe). To znaczy, że 𝓟 jest podzbiorem 𝓣 i 𝓡 jest rozdzielne z 𝓣. Chcemy teraz znaleźć wystarczające warunki na to, żeby 𝓛, przy założeniu, że jest poprawny, zawierał zdanie prawdziwe, ale niedowodliwe w 𝓛.

Numery Gödla i Diagonalizacja. Niech funkcja g będzie funkcją jedno - jednoznaczną, która każdemu wyrażeniu E przypisuje liczbę naturalną g(E) zwaną liczbą Gödla E. Funkcja ta będzie stała przez resztę rozdziału. Zakładając, że każda liczba naturalna jest numerem Gödla jakiegoś wyrażenia, niech En będzie wyrażeniem, którego numerem Gödla jest n. Stąd, g(En)= n.

Diagonalizacja. Przez Diagonalizację wyrażenia En rozumiemy wyrażnie En(n). Jeśli En jest predykatem to jego diagonalizacją jest oczywiście jakieś zdanie; zdanie to jest prawdziwe wtw(wtedy i tylko wtedy), jeśli predykat En jest spełniony przez swoją własną liczbę Gödla n.
Dla każdego n, d(n) będzie numerem Gödla En(n); nazywamy tę funkcję funkcja diagonalną
funkcją systemu.
Używamy terminu zbiór liczbowy (number-set) w znaczeniu zbioru liczb naturalnych. Dlakażdego zbioru liczbowego A, przez A* będziemy rozumieć zbiór wszystkich takich liczb n, że d(n) ϵ A. Stąd dla każdego n równoważność
n ϵA* ↔ d(n) ϵ A
zachodzi z definicji A*.

Ogólna Forma Twierdzenia Gödla. Niech 𝓟 będzie zbiorem liczb Gödla wszystkich dowodliwych zdań. Dla każdego zbioru liczbowego A, przez jego dopełnienie A~ nazywamy dopełnienie A względem zbioru N liczb naturalnych - t.j.,A~ jest zbiorem liczb naturalnych, które nie są w A.

Twierdzenie (GT) - Gödla, z punktu widzenia Tarskiego. Jeśli zbiór (P~)* jest wyrażalny w 𝓛 i 𝓛 jest poprawny, to istnieje w 𝓛 zdanie prawdziwe, ale nie będące tezą 𝓛.
Dowód. Złóżmy, że 𝓛 jest poprawny i (P~)* jest wyrażalny w 𝓛. Niech H będzie predykatem wyrażającym (P~)* w 𝓛, i niech h będzie numerem Gödla H. Niech G będzie diagonalizacją H (tj., zdaniem H(h)). Pokażemy, żeG jest prawdziwe,ale nie dowodliwe w 𝓛.
Ponieważ H wyraża (P~)* w 𝓛, to dla każdej liczby n, H(n) jest prawdziwe ↔ n ϵ (P~)*. Ponieważ równoważność ta zachodzi dla każdego n, zachodzi też dla szczególnego n mianowicie dla n = h (i to jest część rozumowania zwana diagonalizacją), więc mamy równowazność:
H(h) jest prawdziwe ↔ h ϵ (P~)*.
Teraz,
h ϵ (P~)* ↔ d(h) ϵ P~ ↔ d(h) ∉ P.
Ale d(h) jest numerem Gödla H(h) (ponieważ h jest numerem Gödla H) i wiemy też, że d(h) ϵ P jest równoważne temu, iżH(h) jest dowodliwe w 𝓛 i d(h) ∉ P ↔ H(h) nie jest dowodliwe w 𝓛. I teraz mamy:
1. H(h) jest prawdziwe ↔ H(h) nie jest tezą 𝓛. To znaczy, że H(h) jest albo prawdziwe i niedowodliwe w 𝓛, albo fałszywe i dowodliwe w 𝓛. Druga możliwość przeczy założeniu, że 𝓛 jest poprawny. Stąd, musi być, że H(h) jest prawdziwe, ale nie dowodliwe w 𝓛.

Przy analizie konkretnych języków formalnych, należy pokazać, jak wyrazić (P~)* w 𝓛. Można to zrobić pokazując, że zachodzą następujące warunki:
G1 : Dla każdego zbioru A wyrażalnego w 𝓛, zbiór A* jest wyrażalny w 𝓛.
G2 : Dla każdego zbioru A wyrażalnego w 𝓛, zbiór A~ jest wyrażalny w 𝓛.
G3 : Zbiór 𝓟 jest wyrażalny w 𝓛.

Zdania Gödla. Nazwijmy zdanie En zdaniem Gödla dla zbioru liczbowego A, jeśli En jest prawdziwe, a jego numer Gödla leży w A; albo En jest fałszywe i jego numer Gödla leży poza A. Stąd, En jest zdaniem Gödla dla A wtedy i tylko wtedy gdy zachodzi:
En ϵ 𝓣 ↔ n ϵ A.

Lemat (D) - Diagonalny. (a) dla każdego zbioru A, jeśli A* jest wyrażalne w 𝓛, to istnieje zdanie Gödla dla A.
(b) Jeśli 𝓛 spełnia warunek G1, to dla każdego zbioru A wyrażalnego w 𝓛, jest zdanie Gödla dla A.
Dowód.
(a) Załóżmy, że H jest predykatem, który wyraża A* w 𝓛; niech h będzie jego numerem Gödla. Wtedy d(h) jest numerem Gödla H(h). Dla każdego n, H(n) jest prawdziwe ↔ n ϵ A*, z tego wynika, że H(h) jest prawdziwe ↔ h ϵ A*. Mamy też h ϵ A* ↔ d(h) ϵ A. Stąd wynika, że H(h) jest prawdziwe ↔
d(h) ϵ A, a ponieważ d(h) jest numerem Gödla H(h), to H(h) jest zdaniem Gödla dla A.
(b) Natychmiast wynika z (a).
Ogólna Forma Twierdzenia Tarskiego. Lemat D ma ważną konsekwencję: Niech T będzie zbiorem numerów Gödla zdań prawdziwych 𝓛. Wtedy zachodzą następujące twierdzenia.
Twierdzenie (T) ( Tarskiego).
1. Zbiór (T~)* nie jest nazywalny w 𝓛.
2. Jeżeli zachodzi G1, to zbiór T~ nie jest nazywalny w 𝓛.
3. Jeżeli jednocześnie zachodzą G1 i G2 , zbiór 𝓣 jest nienazywalny w 𝓛.

Uwagi.
1. Konkluzja (1) powyżej jest czasami cytowana jako: Dla dostatecznie silnych systemów, prawda nie jest definiowalna wewnątrz systemu. Fraza “ dostatecznie silna” była interpretowana na wiele sposobów. My chcieliyśmy podkreślić, że warunki G1 i G2 są “wystarczająco silne”.
2. Gödel (1931) powiązał swój dowód ze słynnym paradoksem Kreteńczyka, który mówi, że wszyscy Kreteńczycy to kłamcy. Analogia bliższa Twierdzeniu Gödla jest następująca: Wyobraźmy sobie kraj, którego każdy mieszkaniec albo zawsze mówi prawdę albo zasze kłamie. Niektórzy z mieszkańców to Ateńczycy, niektórzy to Kreteńczycy. Ateńczycy w tym kraju zawsze mówią prawdę a Kreteńczycy zawsze kłamią. Jakie zdanie musi wypowiedzieć mieszkaniec tego kraju aby przekonać nas, że mówi on prawdę, a nie jest Ateńczykiem?
Móglby on powiedzieć: “ Nie jestem Ateńczykiem” Kłamca nie może tego stwierdzić (ponieważ kłamca nie może być Ateńczykiem; tylko prawdomówni są Ateńczykami). Stąd też musi mówić prawdę. Skoro jego stwierdzenie jest prawdziwe, to znaczy, że nie może on być Ateńczykiem. Tak więc mówi an prawdę nie będąc Ateńczykiem.
Jeśli założymy, że Ateńczycy są zdaniami 𝓛, które są nie tylko prawdziwe, ale i dowodliwe w 𝓛, to każdy autochton, który twierdzi, że jest Ateńczykiem gra rolę zdania Gödla G, które obwieszcza swą własną niedowodliwość w 𝓛.

2. Zdania Nierozstrzygalne w 𝓛

Jak dotąd nie braliśmy pod uwagę zbioru 𝓡 zdań niedowodliwych. Teraz będą grały kluczową rolę.
𝓛 nazywamy niesprzecznym, jeśli żadne zdanie nie jest jednocześnie dowodliwe i niedowodliwe w 𝓛(tj., zbiory 𝓟 i 𝓡 są rozłączne) i sprzecznym w przeciwnym przypadku. Definicja niesprzeczności odnosi się tylko do zbiorów 𝓟 i 𝓡, nie do zbioru 𝓣. Jednakże, jeśli 𝓛 jest poprawny, to jest automatycznie niesprzeczny (ponieważ, jeśli 𝓟 jest podzbiorem 𝓣, a 𝓣 jest rozdzielne z 𝓡, to 𝓟 musi być rozdzielne 𝓡). Wynikanie w drugą stronę niekoniecznie zachodzi (później będziemy rozważać systemy, które są niesprzeczne, ale nie poprawne).
Zdanie X nazywamy rozstrzygalnymi w 𝓛, jeśli jest albo dowodliwe albo niedowodliwe w 𝓛, a nierozstrzygalne w 𝓛 przeciwnym przypadku. System 𝓛 nazywamy zupełnym w 𝓛, jeśli każde zdanie jest w nim rozstrzygalne i niezupełnym jeśli istnieje w nim jakieś nierozstrzygalne zdanie.
Załóżmy, że język 𝓛 spełnia założenia Twierdzenia GT. Wtedy pewne zdanie G jest prawdziwe ale nie dowodliwe w 𝓛. Ponieważ G jest prawdziwe, więc również nie może być niedowodliwe (z założenia o poprawności systemu). Stąd G jest nieorozstrzygalne w 𝓛. I mamy

Twierdzenie 1. Jeśli 𝓛 jest poprawny i zbiór (P~)* jest wyrażalny w 𝓛, to 𝓛 jest niezupełny.

Saturday 18 February 2012

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ą ε/2i Całkowita długość przedziałów pokrywających wszystkie liczby rzeczywiste, wynosi:

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

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 ε/2k. 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).