Najważniejsza maszyna na świecie

W czasach, gdy chodziłem do szkoły podstawowej, nie wiem, czy obecnie też tak jest, kazano nam się uczyć na pamięć tabliczki mnożenia. Dotyczyło to mnożenia w obrębie liczb od jeden do dziesięć. Na przykład, że dwa razy trzy równa się sześć (symbolicznie 2 x 3 = 6). Ten wynik wyskakiwał trochę jak królik z kapelusza. Nieco później uczono nas metody dochodzenia do tego wyniku. Dla małych liczb można było wspomagać się palcami u rąk: „dwa razy trzy” znaczyło np. „weź dwa razy po trzy palce i policz ile to jest”. Problem zaczynał się z większymi liczbami. Brakowało palców, ale można się było wspomagać zapałkami lub czymś, czego było dużo – np. ziarenkami grochu. Dla w miarę dużych liczb, np. 123456 x 789 = 97406784, nauczono nas technik mnożenia na kartce papieru. Dzisiaj mamy kalkulatory, które dokonują obliczeń, ale jeśli liczby będą zbyt duże, to wyświetlacz pokaże „error”.

Sama metoda obliczeń jest identyczna jak w przypadku liczb dwa oraz trzy: „weź sto dwadzieścia trzy tysiące czterysta pięćdziesiąt sześć razy liczbę siedemset osiemdziesiąt dziewięć, i policz ile to jest”. Intuicyjnie (to słowo jest istotne) czujemy, że ta metoda obliczeń zawsze zadziała, ale pod jednym warunkiem. Żeby wykonać mnożenie trzeba mieć dokładnie dwie liczby, dlatego mówimy, że mnożenie jest dwuargumentowe. Co to zatem znaczy, że mnożenie wykonane na dwóch liczbach zawsze zadziała? Znaczy to, że po wykonaniu skończonej liczby pewnych operacji (które można opisać jako przepis postępowania), uzyskamy zadowalający wynik i ten sam wynik uzyska każdy, kto starannie wykona te same operacje (zgodnie z przepisem).

Mnożenie jest przykładem tego, co matematycy nazywają funkcją. Pojęcie to jest również znane ze szkoły podstawowej. Ze względu na wspomniane powyżej własności tej funkcji przyjęto mówić, że jest to funkcja efektywnie obliczalna w sensie intuicyjnym. Czy jest to jedyna taka funkcja? Otóż nie – takich funkcji znamy ze szkoły więcej, przykładem są choćby dodawanie i potęgowanie. Co więcej, mamy w głowach jakieś pojęcie takich funkcji.

Głowa, ołówek, gumka i papier w kratkę

Można postawić w związku z tym co najmniej dwa ważne pytania. Po pierwsze: czy takich funkcji jest dużo? Po drugie: czy da się je wszystkie opisać w ogólny sposób? Na oba te pytania odpowiedział w połowie lat trzydziestych dwudziestego wieku Alan Turing (1912-1954). Rozpoczął od prostego spostrzeżenia, że funkcje efektywnie obliczalne (nie wiedział ile ich jest, ani które to są dokładnie) oblicza człowiek. Postawił takie pytanie: co właściwie robi człowiek, kiedy oblicza takie funkcje? Lub konkretniej, co właściwie robi człowiek, kiedy mnoży „dwa razy trzy”? Turing przeformułował to pytanie na następujące: czego właściwie człowiek potrzebuje, żeby dokonywać obliczeń? Rezultat jego analiz był zaskakująco prosty: człowiek potrzebuje niewiele, musi mieć głowę (umysł), dużo (właściwie dowolnie dużo) papieru kratkowanego (koniecznie kratkowanego, nie może być w linie) oraz coś do pisania – np. ołówek – i mazania – np. gumkę.

Turing wpadł na pomysł, że każdą liczbę da się zapisać w postaci pionowych kresek w kolejnych kratkach na kartce (w jednej linijce idąc od lewej do prawej), z zastrzeżeniem, że w jednej kratce może być tylko jedna kreska oraz kreski muszą być zapisane w kolejnych kratkach bez wolnych kratek. I tak np. liczbę dwa zapisywał jako dwie kreski pionowe w dwóch następujących po sobie kratkach. Zapiszę to bez kratek: (II). Liczbę trzy jako (III), liczbę cztery jako (IIII), i tak dalej. Z zerem jest kłopot, ale da się rozwiązać, nie będę jednak komplikował rozważań. Jak zapiszemy dwie liczby, na przykład dwa oraz trzy? W postaci dwóch grup kresek, oddzielonych od siebie jedną pustą kratką; najpierw liczbę dwa, zostawiamy jedną kratkę pustą i liczbę trzy, czyli otrzymujemy: (II III).

Czy człowiek podczas obliczeń na takich ciągach kresek musi wiedzieć, ile jest tych kresek w każdej grupie, żeby wykonać mnożenie? Zaskakujące jest to, że nie musi. Musi za to umieć obserwować, w danym momencie, pojedynczą kratkę i rozpoznać, czy jest ona pusta, czy też jest w niej kreska. Po drugie, musi umieć wymazać kreskę gumką oraz wpisać do pustej kratki kreskę (są to dwie różne operację podstawowe). Musi również umieć przesuwać swoją uwagę z danej kratki na kratkę sąsiadującą z prawej lub lewej strony (są to kolejne dwie operacje podstawowe). Ale nie musi wcale umieć obserwować więcej niż jednej kratki w danym momencie. Obliczający człowiek musi mieć w głowie przepis (bardziej fachowo program, niektórzy mówią algorytm), który mu wskaże sposób postępowania w każdej sytuacji w jakiej się znajdzie, czyli którą z podstawowych operacji ma wykonać (zapis kreski, wymazanie kreski, przesunięcie uwagi na kratkę w lewo lub w prawo).

Od komputora do komputera

Proszę zwrócić uwagę na to, jak skromne środki wystarczają do obliczania. Spróbujmy się zastanowić, co musi zrobić taki obliczający człowiek (Turing nazywał go komputorem), żeby pomnożyć dwa razy trzy, i żeby wynik tego mnożenia (czyli sześć — sześć kresek w kolejnych sześciu kratkach) znalazł się na kartce. Może zrobić tak: komputor zaczyna, stojąc nad pierwszą kreską z lewej strony (pierwszą kreską liczby dwa). Dwie pierwsze kreski (pierwsza grupa kresek – licznik) informują, ile razy trzeba powtórzyć liczbę kresek z drugiej grupy. W naszym przypadku powtarzamy dwa razy liczbę trzy, lub inaczej – dwukrotnie grupę trzech kresek. Trzeba wymazać pierwszą kreskę (kratka zostanie pusta) czyli sytuacja będzie taka w kolejnych kratkach: (I III). Teraz piszemy trzy kreski w kratkach z prawej strony grupy trzech kresek (oczywiście zostawiamy jedną kratkę pustą) i mamy na kartce: (I III III). Wymazujemy drugą kreskę i mamy sytuację w kratkach: (III III). Teraz przechodzimy do pierwszej kratki pustej, następującej po drugiej grupie trzech kresek i bez zostawiania pustej kratki wpisujemy znowu trzy kreski do kratek: (III IIIIII). Kończymy pracę obliczeniową. Wynik mnożenia, w naszym przypadku sześć, tworzy drugą grupę kresek.

Mając w kratkach dwa oraz trzy możemy je też dodać do siebie, ale wtedy program musi być inny, np.: wymażmy pierwszą kreskę z lewej strony, przejdźmy do pustej kratki między liczbami i wpiszmy tam kreskę. Koniec obliczeń. Mamy wynik w postaci (IIIII), czyli pięć kresek w kolejnych kratkach. Obliczający komputor nie musi wiedzieć, ile kresek jest w każdej grupie.

W trakcie wykonywania operacji (tych najprostszych) komputor znajdzie się nad jakąś kratką i będzie musiał wykonać kolejną operację (z tych podstawowych, które musi znać). Przypomnijmy, że są one cztery: wymazanie kreski (jeśli jest kreska w kratce), wpisanie kreski (jeśli kratka jest pusta), przejście o jedną kratkę w prawo lub przejść o jedną kratkę w lewo. Jeśli na przykład czyta kreskę w jakiejś kratce, to może wykonać trzy operacje (nie może wpisać kreski, ponieważ kreska już jest). Komputor nie wie, którą z operacji podstawowych ma wykonać. Trzeba mu to jakoś zaznaczyć w przepisie. Otóż wykonanie różnych operacji należy oznaczyć różnymi etykietami lub numerami (od czasów Turinga te etykiety nazywają się stanami wewnętrznymi). Dzięki tym etykietom zapewniamy komputorowi dwie ważne rzeczy: po pierwsze różne etykiety odróżniają od siebie różne operacje, które ma wykonać komputor, po drugie pozwalają komputorowi zapamiętać wykonywanie operacji. Dodatkowym bonusem jest to, że etykiety pozwalają ustalić, kiedy komputor zaczyna obliczanie i kiedy ma je skończyć, co jest bardzo ważne. Przepis w „głowie” obliczającego składa się ze skończonej liczby prostych poleceń, które mają następującą postać czwórek: E (numer czyli etykieta operacji), symbol czytany w kratce, rodzaj operacji, E’ (numer czyli etykieta operacji, którą komputor ma wykonać jako następną). Ten owoc analizy Turinga nazywa się często modelem obliczalności Turinga lub maszyną Turinga. Ta cała sprawa z komputorem, pozornie banalna, wywarła ogromny wpływ na dalsze losy świata. Komputer, którego Czytelnik używa do wyświetlenia tego tekstu, został skonstruowany według idei Turinga i jest, w pewnym sensie, maszyną Turinga.

Teza Churcha-Turinga

Powróćmy teraz do funkcji efektywnie obliczalnych w sensie intuicyjnym. Okazało się, że wszystkie znane takie funkcje można obliczać dzięki pewnej maszynie Turinga. Po drugie, wszystkie funkcje obliczalne na jakiejś maszynie Turinga są obliczalne w sensie intuicyjnym. Po trzecie, maszyn Turinga jest nieskończenie wiele, dokładnie tyle, ile jest liczb naturalnych. Turing postawił sobie w tej sytuacji pytanie: czy wszystkie funkcje obliczalne w sensie intuicyjnym są obliczalne przez jakiś komputor? Odpowiedzią na to pytanie jest hipoteza nazwana tezą Turinga, która brzmi następująco: każda funkcja efektywnie obliczalna w sensie intuicyjnym jest obliczalna przez jakąś maszynę Turinga.

Mniej więcej w tym samym czasie wielu ludzi stawiało sobie podobne pytania jak Turing, odnośnie do funkcji obliczalnych w sensie intuicyjnym. Jednym z nich był Amerykanin Alozno Church, który stworzył inne modele obliczalności. Modele te są jednak trudniejsze do popularnonaukowego przedstawienia i nazywają się lambda rachunkiem i funkcjami rekurencyjnymi. Church postawił również analogiczną hipotezę jak Turing. Nazywamy ją tezą Churcha. Wykazano, że jest ona logicznie równoważna tezie Turinga (dokonał tego nasz ulubieniec Turing). Tezy te powstały przed ponad siedemdziesięciu laty, ale do dzisiaj nie wiadomo czy są prawdziwe. Wielu ludzi chciało wykazać ich fałszywość, ale nikomu się nie udało, choć starali się o to ludzie z najwyższej półki intelektualnej.

Czy umysł jest maszyną Turinga?

W tzw. pierwszej generacji nauk kognitywnych panowało przekonanie, że cały umysł można opisać jako maszynę Turinga realizującą odpowiednie programy, a wszystkie funkcje myślenia, włączając w to język, w zasadzie jako manipulacje pozbawionymi znaczenia symbolami (kreski to po prostu kreski). Umysł stracił swój „duchowy” charakter – stał się maszyną. Efektem takiego podejścia stały się modele sztucznej inteligencji, które osiągają zdumiewające wyniki – na przykład ogrywają arcymistrzów w szachy albo prowadzą rozmowę tak, że trudno rozpoznać, czy odpowiedzi wprowadza człowiek, czy generuje je program. Szukając pod hasłem „test Turinga” w Internecie natrafić można na wiele programów, które potrafią zaskoczyć inteligentnymi odpowiedziami.

Druga generacja nauk kognitywnych odeszła od tego pomysłu, akcentując rolę cielesnych interakcji w powstawaniu zjawisk umysłowych, ale rola fizycznych realizacji maszyn Turinga we współczesnym świecie nie zmalała. Ciągle spotykamy je na każdym kroku, wykonują za nas wiele zadań (obliczeń) i trudno nam wyobrazić sobie życie bez nich.

Adam Olszewski