łańcuchy binarne 1: ogólnosć

Łańcuchem binarnym nazywamy uporządkowany (na przykład od lewej do prawej) szereg obiektów dwu i tylko dwu rodzajów. Na przykład: +-+---++, albo ###/#//. Obiektami tworzącymi łańcuch mogą być symbole ale także kamyki, cząsteczki związków chemicznych itp.

Przez język symboliczny rozumiemy język, którego wyrażenia powstają przez złożenie pewnej liczby znaków (obiektów) np. liter, symboli graficznych, fonemów, gestów. Zbiór wszystkich znaków danego języka nazywamy alfabetem. W informatyce stosujemy pojęcie języka nad alfabetem czyli zbioru wszystkich łańcuchów dających się utworzyć ze znaków alfabetu. Stosujemy oznaczenie {a1, a2, a3,...}*. Język nad alfabetem polskim (plus znaki interpunkcyjne i spacja) zawiera więc wszystkie możliwe wypowiedzi w języku polskim oraz mnóstwo (nieprzeliczalne) łańcuchów nonsensownych.

Ogólność łańcuchów binarnych:

1. Cokolwiek daje się wyrazić w jakimkolwiek języku symbolicznym daje się też przedstawić w postaci łańcucha binarnego.

Twierdzenia tego nie trzeba w dzisiejszych czasach specjalnie dowodzić, to "każdy wie". Przecież litery tego tekstu wygenerowałem właśnie korzystając z kodowania binarnego (gdzieś tam na samym dnie przetwarzania). W razie potrzeby nietrudno wykazać równoliczność odpowiednich zbiorów łańcuchów binarnych i dowolnych skończonych alfabetów. 

W szczególności zachodzi:

2. Każdy problem formułowalny w dowolnym języku symbolicznym może być przedstawiony w postaci łańcucha binarnego.

3. Sformułowanie rozwiązania dowolnego (posiadającego rozwiązanie) problemu wyrażalnego w dowolnym języku symbolicznym może być przedstawione w postaci łańcucha binarnego.

Dlatego: 

4. Znalezienie sformułowania rozwiązania dowolnego problemu rozwiązywalnego sprowadza się do przeszukania odpowiedniego zbioru łańcuchów binarnych. 

Stwierdzenia 1-4 opisują własność łańcuchów binarnych zwaną ogólnością. Łatwo zauważyć, że mają ją także inne łańcuchy i nie tylko one. Dlaczego zwracamy w takim razie szczególną uwagę właśnie na nie? Ponieważ są najprostsze: mają najmniej znaków i szczególnie łatwo liczyć z ich pomocą. Warto zaznaczyć, że można rozpatrywać łańcuchy złożone z mniejszej niż dwa (ale większej od jeden) liczby znaków. Wymaga to bardziej zaawansowanych rozumowań i komplikuje sprawę ale zasadniczo jest wykonalne. Takimi przypadkami nie będziemy się tu zajmować. Przynajmniej na razie. Trzeba też podkreślić odróżnienie "sformułowania rozwiązania problemu" od "rozwiązania problemu". Czym się różnią? Mniej więcej tym czym przepis na zupę zamieszczony w książce kucharskiej od zupy. Tylko jeden przypadek jest jadalny i sycący. Tej sprawie poświęcimy jeszcze więcej uwagi.

Zagadnienie.

Czy nasze języki, wszak symboliczne, wyrażają wszystko z czym mamy do czynienia. A może istnieje jakaś rzeczywistość pozajęzykowa? Sprawa jest otwarta. Spróbujmy tak prosto, matematycznie. Równanie okręgu może być przedstawione jako łańcuch binarny i to niedługi. A sam okrąg? Przecież to linia krzywa, ciągła, zbiór mocy continuum, a łańcuchy binarne to zbiory policzalne. Z drugiej strony jest ich (nieskończonych) "dwa do alef zero". No a jeżeli weźmiemy nie okrąg w potocznie matematycznym sensie tylko jego rysunek? Tu wkracza już fizyka i funadamentalne pytanie o naturę naszego świata: policzalna/dyskretna czy continualna, a może jeszcze jakaś inna? I jak moglibyśmy to rozstrzygnąć?