Maszyna Turinga - od ''komputera'' do komputera

Przywykliśmy do komputerów już tak dalece, że ich początki nie budzą szczególnego zainteresowania. Skupiamy się obecnie na ich rozlicznych zastosowaniach. Częściej jednak patrzymy w przyszłość, słuchając zapowiedzi teoretyków sztucznej inteligencji, którzy zapowiadają zastąpienie naszego rozumu wszechmocą cyfrowych maszyn.

Przywykliśmy do komputerów już tak dalece, że ich początki nie budzą szczególnego zainteresowania. Skupiamy się obecnie na ich rozlicznych zastosowaniach. Częściej jednak patrzymy w przyszłość, słuchając zapowiedzi teoretyków sztucznej inteligencji, którzy zapowiadają zastąpienie naszego rozumu wszechmocą cyfrowych maszyn.

Czasami tylko uświadamiamy sobie, że komputer to etap długiego rozwoju mechanicznych maszyn liczących. Rzadziej jednak wiemy, że jego projekt łączy się ze szczególną sytuacją teoretyczną współczesnej nauki. Rodowód komputera sięga początków dyskusji nad podstawami matematyki i logiki, sporów psychologicznych i filozoficznych toczonych od lat 30. i 40. naszego stulecia.

Komputer służy do liczenia - jest to oczywiste dla każdego, kto używa arkusza kalkulacyjnego czy najzwyklejszego kalkulatora. Skuteczność komputerów cyfrowych w ich liczeniu opiera się na matematycznej idei, mówiącej, że każdy poprawnie sformułowany problem ma swoje rozwiązanie (rozstrzygnięcie) poprzez jego obliczenie. Obliczeniem jest zaś mechaniczna procedura wykonania zadania w skończonej liczbie kroków, inaczej mówiąc, obliczenie jest wykonalne, jeśli istnieje dla niego algorytm. Rzecz cała wydaje się trywialnie prosta i oczywista, ale faktycznie taka nie jest. Otóż w dyskusjach nad podstawami matematyki i logiki podnosi się istotne zastrzeżenia co do obliczalności na podstawie mechanicznych (algorytmicznych) procedur.

Wszystko zaczęło się w 1936 r. Wówczas to dwudziestotrzyletni absolwent matematyki z Cambridge Alan M. Turing opublikował artykuł o tzw. liczbach obliczalnych, w którym sformułował pomysł abstrakcyjnej maszyny do przeprowadzania obliczeń. Jego rozwiązanie kwestii rozstrzygalności (tak nazywano zagadnienie, czy istnieją liczby obliczalne) może pozostałoby ważnym osiągnięciem matematycznym znanym tylko wąskiemu gronu matematyków, gdyby nie to, że użył on bardzo pomysłowej i obrazowej argumentacji. Był pod tym względem nowatorski, choć nie jedyny ani nawet nie pierwszy. Gdy oddawał swój artykuł do druku, znane już było podobne (inaczej tylko sformułowane) rozstrzygnięcie podane przez znanego amerykańskiego matematyka A. Churcha (z którym potem A. Turing współpracował) i Emila Posta - matematyka polskiego pochodzenia, który kilka lat wcześniej również rozważał możliwość mechanizacji obliczeń.

A. Turing miał jednak przewagę nad nimi, gdy użył nazwy "maszyna", mając jednak na myśli nie tyle konkretne urządzenie (tak myślał bardziej Post), co abstrakcyjny projekt, swoistą grę intelektualną. Zaczęto ją później nazywać (zaproponował to A. Church) "maszyną Turinga" i termin ten stał się jednym z najczęściej używanych (także nadużywanych) w logice, naukach o komputerach, informatyce, biologii teoretycznej, wreszcie w teoriach sztucznej inteligencji.

Uniwersalna maszyna Turinga

Alan Turing rozważył obliczanie od strony czynności, które wykonuje rachmistrz, a nawet każde dziecko, gdy na kartce papieru etap po etapie przeprowadza obliczenia. Taką abstrakcyjną osobę A. Turing nazwał "komputerem" (w latach 30. słowo to było ekstrawagancją językową, dlatego jeden z jego uczniów proponuje używanie raczej terminu "komputor") i założył, że jego czynności mogą być w zasadzie wykonane przez pewne mechaniczne urządzenie, choć wtedy nie zaprzątał sobie jeszcze głowy, jak ma być ono skonstruowane.

Założył, że taki komputer oblicza według bardzo elementarnych czynności i określonego algorytmu. Jego postępowanie sprowadza się do następujących etapów: zapisu (zmiany) na nieskończonej (lecz ograniczonej) taśmie z kratkami określonego znaku ze skończonego zbioru (A. Turing rozważył układ binarny, 0 i 1) i przejścia od jednej kratki do drugiej (w dowolnym kierunku) według określonych "stanów umysłu" abstrakcyjnego rachmistrza. Słowem, rachmistrz robi to, co wyznacza za każdym razem znak z konkretnej kratki taśmy i jego własny stan.

Na działanie komputera/rachmistrza składają się zatem skończone instrukcje przechodzenia między poszczególnymi kratkami, wykonywania wobec nich pewnych działań (odczytania, zapisu lub wymazania znaku); instrukcje te są programem działania maszyny. Wobec każdej konkretnej maszyny istnieje ponadto maszyna uniwersalna, która może imitować jej obliczenia. Taką maszyną uniwersalną jest każdy komputer.

Maszyneria "komputera"

"Otóż moglibyśmy skonstruować maszynę, która wykonałaby pracę tego komputera" - napisał A. Turing i zdanie to określa dobitnie jego stanowisko w sprawie rzeczywistych możliwości maszyn cyfrowych - komputerów pisanych już bez cudzysłowu. I choć jemu samemu nie było dane doświadczyć sukcesów w konstrukcji pierwszych maszyn cyfrowych, to jednak stworzył kilka ważnych projektów, z których większość zrealizowano zaledwie w postaci prototypowych elektromechanicznych urządzeń. Już podczas stypendium w Princeton oraz po powrocie do Cambridge A. Turing zbudował prostą maszynę z elektromagnetycznych przełączników do obliczania funkcji zeta Riemanna, na której realizację otrzymał w swej uczelni 40 funtów. Cel był ważny - mechaniczne wyszukiwanie miejsc zerowych tej funkcji.

Wyniki te doceniono i szybko spożytkowano, bowiem praca ta miała znaczenie dla kryptografii. Na początku wojny władze wojskowe zmobilizowały Alana Turinga do prac nad łamaniem niemieckich szyfrów, głównie słynnej Enigmy. Pracował w tajnym ośrodku w Blatchley Park nad teoretycznymi założeniami i konstrukcją maszyn deszyfrujących. Wykorzystał w nich istniejące już urządzenia zbudowane przez polskich inżynierów, zwane "bombami", które przekazano stronie brytyjskiej na początku działań wojennych. Współpracował także z badaczami i konstruktorami amerykańskimi, lecz ścisła brytyjska tajemnica wojskowa długo nie pozwoliła ocenić rangi i zakresu wkładu A. Turinga w te badania.