[ Pobierz całość w formacie PDF ]
.Cóż zatem jesteśmy w stanie wywnioskować o naturze programu, który, jak chcieliby nas przekonać Fredkin, Tipler i im podobni, jest podłożem naszej rzeczywistości?NiepoznawalneZajmijmy się przez chwilę konkretnym przypadkiem programu używanego w maszynie cyfrowej, służącego na przykład do mnożenia ciągu liczb.Założeniem całej koncepcji jest, że napisanie programu powinno być w jakimś sensie prostsze niż wykonanie operacji, do których jest on przeznaczony.Gdyby tak nie było, nikt nie zawracałby sobie głowy komputerem, lecz po prostu przeprowadził rachunki bezpośrednio.Można to wyrazić w ten sposób, że użyteczny program komputerowy jest w stanie generować więcej informacji (w tym przypadku, przeprowadzić bardzo wiele mnożeń), niż sam zawiera.Jest to nic innego, jak nieco udziwniony sposób powiedzenia, że w matematyce poszukujemy prostych reguł, które mogą być stosowane wielokrotnie, nawet przy bardzo skomplikowanych obliczeniach.Jednakże nie wszystkie operacje w matematyce da się wykonać za pośrednictwem programu znacznie mniej złożonego niż sama ta operacja.W istocie, z faktu istnienia liczb nieobliczalnych wynika, że dla pewnych operacji nie istnieje żaden program.Zatem niektóre procesy matematyczne cechuje taka złożoność wewnętrzna, że nie mogą być one ujęte w ramy zwięzłego programu.W przyrodzie również mamy do czynienia z procesami o ogromnej złożoności, a zatem rodzi się pytanie, czy można je zawrzeć w ramach zwięzłego opisu.Ujmując rzecz inaczej, czy „program Wszechświata” jest znacząco prostszy niż sam Wszechświat? Stanowi to bardzo głębokie pytanie dotyczące natury rzeczywistości fizycznej.Jeśli program komputerowy lub algorytm jest prostszy niż układ, którego dotyczy, mówimy, że układ ten jest „algorytmicznie upraszczalny”.Zatem mamy znaleźć odpowiedź na pytanie, czy Wszechświat jest algorytmicznie upraszczalny.Zanim zajmiemy się tym pytaniem, nie od rzeczy będzie rozważenie pojęcia algorytmicznej upraszczalności nieco bardziej szczegółowo.Dziedzina, zwana algorytmiczną teorią informacji, została stworzona w latach sześćdziesiątych w Związku Radzieckim przez Andrieja Kołmogorowa oraz w Stanach Zjednoczonych przez Gregory Chaitina z IBM.U jej podstaw leżało bardzo proste pytanie: jaki najkrótszy komunikat pozwala wyrazić układ o pewnym stopniu złożoności? Jest oczywiste, że prosty układ da się wyrazić krótko, lecz złożony układ już nie (spróbujcie opisać strukturę rafy koralowej za pomocą tej samej liczby słów, co w przypadku opisu kostki lodu).Chaitin i Kołmogorow zaproponowali definicję złożoności układu jako długości najkrótszego możliwego jego opisu.Przyjrzyjmy się, jak to działa w przypadku liczb.Istnieją liczby proste, takie jak 2 lub n, i liczby złożone, jak ciąg jedynek i zer otrzymany poprzez rzuty monetą (orzeł = 0, reszka = 1).Czy możemy podać typ opisu pozwalający na jednoznaczne wyrażanie tych liczb? Jedną z możliwości jest wypisywanie ich w postaci dziesiętnej lub dwójkowej (n można tak wyrazić tylko jako konkretne przybliżenie, gdyż jej rozwinięcie dziesiętne ma długość nieskończoną).Jednakże jest oczywiste, że nie jest to najkrótszy sposób ich opisu.Na przykład liczbę rt możemy wyrazić krócej, podając wzór pozwalający na obliczenie jej z zadaną dokładnością.Jeżeli przyjmiemy, że rozważane liczby otrzymujemy na wyjściu komputera, to najkrótszym opisem danej liczby będzie najkrótszy program pozwalający komputerowi obliczyć tę liczbę.W ten sposób za proste liczby będziemy uważać te, które są generowane przez krótkie programy, a za złożone te, które wymagają długiego programu.Następnym etapem jest porównanie długości danej liczby z długością programu, który ją oblicza.Czy jest on krótszy? Czy faktycznie udało nam się w ten sposób osiągnąć uproszczenie? Aby wyrazić to w sposób bardziej ścisły, przypuśćmy, że na wyjściu komputera otrzymujemy ciąg jedynek i zer, taki jak ten:101101011100010100110101001.(gdzie kropki „.” oznaczają „i tak dalej, nawet w nieskończoność”).Ciąg ten będzie zawierał pewną ilość informacji, mierzoną w „bitach”.Następnie chcemy porównać tę zawartość informacyjną z ilością informacji, jaką zawiera sam program.By podać tu prosty przykład, załóżmy, że na wyjściu komputera otrzymaliśmy:101010101010101010101010101010Ten ciąg moży być wygenerowany za pomocą prostego algorytmu „Wydrukuj piętnaście razy 10”.O wiele dłuższy ciąg otrzymamy za pomocą programu „Wydrukuj milion razy 10”.Ten drugi program nie jest wcale bardziej skomplikowany niż pierwszy, a wynikiem jego działania jest o wiele dłuższy ciąg informacyjny.Wynika stąd, że gdy ciąg wynikowy zawiera jakiekolwiek struktury, to mogą być one wyrażone za pomocą prostego algorytmu, który może być o wiele krótszy (przyjmując za jednostki bity informacji) niż pierwotnie otrzymany ciąg.Mówimy wtedy, że ciąg jest algorytmicznie upraszczamy.Natomiast jeżeli, na odwrót, dla danego ciągu nie da się podać algorytmu istotnie krótszego niż on sam, jest on algorytmicznie nieupraszczalny.W tym przypadku ciąg nie będzie zawierał żadnych regularności ani struktur; będzie to po prostu chaotyczny ciąg jedynek i zer.W ten sposób stopień możliwego do osiągnięcia uproszczenia algorytmicznego może być uznany za praktyczną miarę złożoności ciągu wynikowego, przy czym niska upraszczalność oznaczałaby większą złożoność.Ciągi regularne da się znacznie uprościć, podczas gdy nie można tego uczynić dla ciągów, w których nie występują żadne struktury.Pojęcie algorytmicznej upraszczalności pozwala na ścisłe zdefiniowanie przypadkowości: ciągiem przypadkowym będzie ciąg, który nie może być algorytmicznie uproszczony.Może nie być łatwo stwierdzić na drodze czysto wizualnej, czy dany ciąg jest upraszczalny, gdyż występujące w nim struktury mogą być bardzo wyrafinowane i głęboko ukryte.Każdy, kto kiedykolwiek zajmował się łamaniem szyfrów, wie, że to, co na pierwszy rzut oka wydaje się bezładnym zbiorowiskiem liter, może w rzeczywistości zawierać strukturę komunikatu; trzeba jedynie znać klucz do szyfru.Nieskończone rozwinięcie dziesiętne (i jego dwójkowy odpowiednik) liczby n nie wykazuje żadnych regularności, nawet w skali tysięcy cyfr, i cyfry te według wszystkich standardowych testów statystycznych ułożone są czysto losowo.Na podstawie znajomości pierwszego tysiąca cyfr tego rozwinięcia nie mamy żadnej możliwości przewidzieć tysiąc pierwszej cyfry.A mimo to ti jest algorytmicznie upraszczalna, bowiem dysponujemy prostym algorytmem pozwalającym na wyliczanie kolejnych miejsc po przecinku tej liczby.Chaitin wykazuje, że takie pojęcie matematycznej złożoności może być sensownie zastosowane także do układów fizycznych: złożonością układu fizycznego jest minimalna długość algorytmu pozwalającego go opisać lub symulować jego działanie.Na pierwszy rzut oka definicja ta wydaje się dość arbitralna, ponieważ nie zostało określone, jakiego będziemy używać komputera.Okazuje się jednak, że nie ma to większego znaczenia w sytuacji, gdy wszytkie komputery uniwersalne są w stanie się nawzajem symulować.Podobnie nieistotne jest, jakim językiem programowania - LISP, BASIC, FORTRAN - się posłużymy, gdyż napisanie ciągu instrukcji tłumaczącego jeden język na drugi jest sprawą prostą
[ Pobierz całość w formacie PDF ]