Co to są liczby nieobliczalne? Jak algorytm kulinarny zamienić w łańcuch cyfr? W jaki sposób oddać zmysły w programie komputerowym?

Pomysłodawca komputera, czyli maszyny cyfrowej, matematyk z Oxfordu Alan M. Turing był największym w dziejach kryptografem, specjalistą od kodowania i łamania szyfrów. Aby wyjaśnić tę zbieżność, bynajmniej nieprzypadkową, przypomnijmy historyczny sukces Turinga w kryptografii.

Nadchodziła druga wojna światowa. A. Turing spotyka się z matematykami z Poznania pracującymi dla polskiego wywiadu nad złamaniem szyfrów armii niemieckiej. Rozpracowali oni służącą do tego celu niemiecką maszynę o nazwie Enigma i spotykają się, by przekazać wyniki wywiadowi sojusznika. Na tych wynikach Turing, powołany przez rząd brytyjski na szefa głównego zespołu od łamania kodów, oparł dalszą działalność. Okazała się ona kolosalnym wkładem wywiadowczym w ostateczne zwycięstwo, gdyż szyfrowane rozkazy dowódców niemieckich szybko trafiały do dowództwa brytyjskiego. Do Turinga i jego zespołu również trzeba odnieść to, co powiedział Churchill o lotnikach z bitwy o Anglię: jeszcze nigdy tak wielu nie zawdzięczało tak wiele tak niewielu.

Dlaczego to historyczne zadanie powierzono człowiekowi w wieku lat dwudziestu kilku, którego nazwisko było znane tylko w wąskim kręgu logików matematycznych? Mianowicie w tym kręgu podziwiano wynik Turinga w pewnej kluczowej kwestii atakowanej przez logikę od kilku dziesiątków lat, który to wynik wymagał wyrafinowanej metody kodowania opisów procedur mechanicznych. To wystarczyło rządowi Jego Królewskiej Mości, szukającemu kogoś, kto by przechytrzył kryptografów niemieckich.

Wynik Turinga z 1936 r. okazał się podstawowy zarówno dla idei komputera, jak i projektu sztucznej inteligencji wysuniętego przez Turinga w 1948 r. (W 1998 r. - okrągły jubileusz!) Istotą tego wyniku jest zdefiniowanie nowej (nie znanej w dawniejszej matematyce) klasy liczb rzeczywistych nazwanych NIEOBLICZALNYMI i wyprowadzenie stąd zaskakujących konsekwencji co do możliwości rozwiązywania problemów matematycznych. Mianowicie, nie są dla maszyny rozwiązywalne te problemy, których rozwiązanie wyrażałoby się jakąś liczbą nieobliczalną.

Kluczem do tego wyniku jest definicja pojęcia obliczania. Jeśli (1) się ją posiądzie i jeśli (2) WSZYSTKIE inne problemy dadzą się zakodować liczbowo, czyli w cyfrach, to odpowiedź na pytanie postawione w tytule będzie twierdząca. Definicja obliczania to niepodważalne osiągnięcie Turinga (i innych autorów, lecz z uwagi na to, iż u Turinga mamy punkt wyjścia dla SI, mowa tu tylko o nim). W punkcie 2 nie ma tak definitywnej odpowiedzi, ścierają się hipotezy na ,,tak" i ,,nie". W każdym razie, nawet jeśli kodowanie nie jest ,,dobre na wszystko", to jego możliwości obejmują kolosalną sferę problemów. Tak wielką, że odkąd ludzie opanowali technikę kodowania cyfrowego - w formie programowania komputerów - nie będzie przesadą powiedzieć, że odmieniło się oblicze ziemi.

Jak algorytm kulinarny zamienić w łańcuch cyfr

Co to jest algorytm, wie uczeń szkoły podstawowej odrabiający lekcje z matematyki metodą ,,słupków". Wie w tym sensie, że umie go stosować (nie musi znać samego słowa, jak nie musi wiedzieć, że pochodzi ono od nazwiska pewnego średniowiecznego Araba, któremu tę metodę zawdzięczamy). ALGORYTM nazywamy też PROCEDURĄ MECHANICZNĄ, co oznacza, że jest to postępowanie, które nie wymaga twórczości, będąc tylko wykonywaniem instrukcji odnoszących się wyłącznie do kształtu symboli i ich usytuowania przestrzennego. Prawdę mówiąc postępowanie mechaniczne to tyle, co bezmyślne.

Mamy do dyspozycji jeszcze jeden termin - PROGRAM. W szerszym znaczeniu jest on synonimem obu wymienionych. W węższym zaś - tym szeroko znanym - to algorytm wyrażony w języku dającym się przełożyć na kod maszynowy, czyli język wewnętrzny maszyny cyfrowej (system impulsów sterujących wykonywaniem przez nią zadań).

W popularnych wprowadzeniach w informatykę, by czytelników nie straszyć przykładami z matematyki, jako przykłady algorytmów podaje się przepisy z książki kucharskiej. Aby ten chwyt dydaktyczny zdał egzamin, trzeba by pokazać, jak przepis kulinarny zastąpić łańcuchem cyfr opisującym pewną liczbę. Do istoty bowiem algorytmu - procedury mechanicznej, czyli programu (w szerszym znaczeniu) - należy możliwość zakodowania go cyfrowo. Jest to wielka idea Turinga, którą tak ujął jego biograf, fizyk z Oxfordu, Andrew Hodges:

"Zdolność komputera do wykonania dowolnego programu wywodzi się z głębokiej idei, że programy i liczby nie różnią się od siebie".

Uniwersalność bowiem komputera na tym polega, że dysponuje on układem programów (systemy operacyjne i translatory), który potrafi realizować każdy inny program, o ile ten inny jest dostarczony w postaci ciągu liczbowego. Jak to zrobić? Częścią programu są operacje arytmetyczne, np. 2+3=5. W tym napisie są już symbole liczbowe (cyfry), odnoszące się do argumentów operacji. Symbolom operacji (jak +) i relacji (jak =) również przydziela się umownie pewne cyfry, aby zaś nie mylić ich z argumentami, oddzielamy je stworzonymi w tym celu znakami interpunkcyjnymi, też kodowanymi w formie cyfr (w realizacji jest to raczej skomplikowane, lecz idea jest prosta). Inne instrukcje programu, podobnie jak symbole operacji, też oznacza się liczbami umownymi.