muuishuukai muuishuukai
81
BLOG

Łańcuchy binarne 8: szaleństwo przejść granicznych

muuishuukai muuishuukai Nauka Obserwuj temat Obserwuj notkę 0

Pora na coś szalonego. Generator "siłowy" działający w schemacie drzewa binarnego daje w n-tym kroku tablicę wszystkich łańcuchów n-długich ustawionych w określonym porządku, który możemy nazwać porządkiem generowania. Oczywiście istnieją dwa generatory siłowe, jeden zaczynający się od 

0

1

i drugi mający na początku

1

0.

W przypadku pierwszego tablice zaczynają się od 00.. ..0 a kończą na 11... ...1 i są prostokątnymi macierzami n na 2^n. Zadajmy pytanie: czy możliwe jest przejście graniczne to znaczy wygenerowanie wszystkich łańcuchów nieskończonych? Sprawa nie jest bynajmniej jasna, a istnienie tego rodzaju prześć należy zawsze wykazać. Rzecz jasna znajdujemy się na terenie matematyki dopuszczającej rozważanie obiektów pozaskończonych a nie na obszarze np. informatyki praktycznej czy w dominium intuicjonistów. W celu rozruszania przybliżenia problemu wyobraźmy sobie abstrakcyjną maszynę o następujących właściwościach:  w n-tym kroku maszyna generuje siłowo n-tą tablicę, każdy krok wykonywany jest dwa razy szybciej niż poprzedni, maszyna wykonuje drugie obliczenie po upływie pół minuty. Pytanie: co maszyna robi w drugiej minucie? Odpowiedź: nic nie robi ponieważ wygenerowała już wszystkie, dowolnie długie łańcuchy skończone jest ich oczywiście policzalnie nieskończenie wiele). Zatem tą metodą nie uzyskujemy przejścia, tablica wszystkich łańcuchów nieskończonych nie została wygenerowana. Zauważmy jednak: gdyby maszyna w n-tym kroku dawała wszystkie łańcuchy długości SUMA(od1 do n) to przejście zostało by dokonane. Ale nie może tego zrobić ponieważ, jak widzieliśmy wcześniej, "liczby nieobliczalne" muszą być generowane krok po kroku. Moglibyśmy zacząć próby udoskonalania naszej maszyny siłowej ale prowadziłoby to do komplikacji spróbujemy więc drugiego generatora niewłaściwego czyli losowego. Niech będzie dana maszyna generująca losowo w n-tym kroku wszystkie Suma(1 do n)-długie łancuchy binarne przy czym na długość kroku nakładamy te same warunki co w przypadku poprzednim (każdy jest dwa razy krótszy od poprzedniego). Rozważmy zbiór wszystkich takich maszyn (omega). Jest on naprawdę liczny, to moc 2^(2^(alef zero)). Ale istnieją w nim dwie dające na nieskończone tablice uporządkowane zgodnie z porządkiem generowania siłowego. Jak mogą takie tablice wyglądać? Zgodnie z Cantorowską intuicją mają wymiary alefzero na 2^alef zero i zaczynają się od samych zer (lub jedynek) a kończą na samych jedynkach (lub zerach). Łańcuchów jest tyle co liczb rzeczywistych i są uporządkowane w sposób nie gęsty i nieciągły w sensie Dedekinda. To nie musi nas martwić poniewaz gęstość i ciągłaść są własnościami uporządkowań a nie zbiorów i tego rodzaju uporządkowania liczb są znane. Zastanawiające jest jednak coś innego. W przypadku generowania siłowego w każdej tablicy otrzymujemy łańcuch postaci 1000... ...01 (zera między dwoma jedynkami). W tablicy nieskończonej także musi on wystąpić czyli usi wystąpić łańcuch, w którym druga jedynka nie ma następnika, jednym słowem element ostatni. Ale ponieważ zbiór elementów łańcucha jest policzalny i ma jak widać kres górny (pierwsza jedynka) i kres dolny (druga jedynka) to sam łańcuch także musi być skończony. Sytuacja jest zastanawiająca. Wykazaliśmy istnienie przejścia ale okazało się, że intuicje Cantorowskie zawodzą. W tym momencie mamy trzy możliwości. Pierwsza polega na głoszeniu, że Cantor nie miał racji i żadna nieskończoność nie istnieje. Byłby to jednak krok pochopny ponieważ teoria mnogości jest piękną konstrukcją o fundamentalnym charakterze i wielu matematycznych zastosowaniach. Druga możliwość to przyjęcie, że przejście było po prostu nieefektywne i ogłoszenie, że nie jest ono możliwe. Istnieje jeszcze trzecia i ona jest naprawdę interesująca, należy mianowicie zbadać co właściwie otrzymaliśmy. Powróćmy do łańcucha 1000... ...001. Pytanie brzmi: ile właściwie jest zer pomiędzy tymi jedynkami? Odpowiedź jest prosta: skończene, dowolnie i nieokreślenie wiele. W tym momencie pojawia się możliwość wprowadzenia nowego rodzaju zbiorów, mianowicie zbiorów potencjalnie skończonych. Filozofowie/matematycy zajmowali się głównie dwoma rodzajami nieskończoności: nieskończonością potencjalną (możemy do skończonego dodawać w nieskończoność) i aktualną (zbiór już ma moc nieskończoną). Pozostałe zbiory uważano zazwyczaj za "po prostu" skończone. Zbiory potencalnie skończone to zbiory skończone, które jednak można powiększać. Ich podstawowymi własnościami są moc otwarcia (ile elementów można dodawać) oraz prawdopodobieństwo zamknięcia. To tak jak z życiem, zbiór jego chwil jest skończony i rośnie minuta po minucie ale zamknięcie nieznane, możemy tylko szacować prawdopodobieństwa. Rozglądając się po świecie łatwo zauważyć, że zbiory potencjalnie skończone występują bardzo często, tak więc ewentualna teoria mnogości potencjalnie skończonych mogłaby być interesująca tak dla matematyka jak i dla przyrodnika. Dodatkowo: zauważyłem, że zbiory o różnych mocach otwarcia mają "w praktyce" (da się to ściślej zdefiniować) własności analogiczne do zbiorów Cantorowskich o różnych mocach. Jeżeli np. mamy zbiór otweraty powiększany liniowo (za każdym razem dokładamy n elementów) to jest on praktycznie nierównoliczny ze zbiorem otwartym wykładniczo (np, z mocą otwarcia 2^n).

muuishuukai
O mnie muuishuukai

Nowości od blogera

Komentarze

Inne tematy w dziale Technologie