Geneza
W 1936 roku, dokładniej dwunastego dnia jedenastego miesiąca tegoż roku, na światło dzienne wyszła jedna z ważniejszych prac naukowych, która dotyczyła i do dnia dzisiejszego dotyczy, algorytmiki. Mało tego, można by rzec, że jest to praca, która dała początek ich formalizacji. "On computable numbers, with an application to the entscheidungsproblem" Alana Mathisona Turinga, znanego po dziś dzień angielskiego matematyka, kryptologa, i można by rzec subiektywnie, pierwszego informatyka świata. Praca ta jest o tyle interesująca, że wprowadza pojęcie pewnego abstrakcyjnego urządzenia, zdolnego wykonywać operacje na liczbach. Urządzenie to zostało ochrzczone maszyną Turinga, choć w samej pracy nie zostało tak nazwane (nazwane zostało maszyną "obliczającą", "liczącą", tj. Computing machine).
Co to za urządzenie i do czego służy? Zapraszam do dalszej lektury.
Liczby obliczalne
Turing w swej pracy użył pojęcia liczb obliczalnych, "computable numbers". Warto wspomnieć cóż to takiego jest.
W odniesieniu do maszyn liczących, czy też obliczających, należy uściślić pojęcie liczby, którą da się policzyć. Pojęcie mogłoby wydawać się proste, bo przecież, pamietając matematykę licealną, można powiedzieć, że każdą! Nieskończony zbiór liczb zespolonych, obejmuje wszytkie znane nam zbiory liczby i ma ściśle zdefiniowaną arytmetykę, toteż pierwszą rzeczą jaka nasuwa się na myśl jest, że każda.
Otóż nie do końca.
Matematyka jest o tyle dziedziną przyjemną, że nie istnieje w niej pojęcie ograniczeń w sensie fizycznym. Czy możemy rozważyć liczbę, której liczba cyfr będzie \(100^{134^{216^{376}}} \) a każda z owych cyfr będzie różna od poprzedniej i dwóch wstecz, następnie zdefiniować takich 12 i każdą z nich osobno ze sobą wymnożyć? Oczywiście że tak, któż nam broni?
Problem komputerów zaczyna się tam, gdzie zaczyna się fizyka, materiały i związane z nimi ograniczenia.
Otóż. Komputery mają pamięć. Przeróżną. W procesorach, w kościach RAM, na dyskach twardych, taśmach magnetycznych i wielu innych, zdolnych zatrzymać jakiś stan, urządzeniach. Mają one ograniczenia pojemności. W większości przechowują różnie zrealizowaną pamięć na bity (np. w RAM'ie napięcie powyżej jakiejś wartości, np. 0.5V na tranzystorze). Żeby uzmysłowić fakt absurdalnej wręcz wielkości liczby, którą przytoczyliśmy, musimy powiedzieć że szacowana liczba atomów we wszechświecie wynosi \(10^{80}\). To dużo dużo mniej niż liczba cyfr naszej liczby. Nawet jeżeli zlogartymowalibyśmy tę liczbę podstawą 2, uzyskując liczbę bitów potrzebnych do jej zakodowania otrzymamy:
\(log_2(100^{134^{216^{376}}} ) \approx log_2(10^{10^{876}}) \approx 3 \cdot 10^{876}\)
Co nadal jest liczbą bitów większą, niż liczba atomów we wszechświecie.
Wniosek jest prosty, nie jesteśmy w stanie zrealizować fizycznie obliczeń na wszystkich liczbach. Możemy jednak operować na takich, które będą wystarczająco duże, by spełnić zdecydowaną większość oczekiwań jakie przed nimi stawiamy, np. odległość, liczba pieniędzy, temperatury, etc. Podzbiór takich liczb Turing nazwał "obliczalnymi", czyli rzeczywistymi, które są zapisywalne przez maszynę.
Jednak jeżeli zerkniemy sobie na konstrucję maszyny, zauważymy że nie musi się ona ograniczać do samych tylko liczb. Jako że model jest abstrakcyjny, można mu zadać dowolny ciąg czegokolwiek, tzw. ciąg symboli. Czym one są? O tym zaraz.
Maszyna Turinga
Turing w swojej pracy, bez zbędnych wstępów, opis swojej maszyny rozpoczął już od drugiej strony. Maszyna ta w swej istocie jest niezwykle prostej konstrukcji.
Rzecz pierwsza. Taśma.
Skoro maszyna ma coś liczyć i wykonywać jakieś operacje, musi mieć wejście, do którego dostarczać będziemy dane. Funkcję nośnika wejścia w maszynie Turinga pełni taśma. Można ją z łatwością przyrównać do papierowej taśmy, albo metra krawieckiego. Tasiemka ta podzielona jest na sekcje, nazwane przez Turinga "kwadratami" (squares). Każdy kwadrat zdolny jest nieść jeden symbol, a maszyna musi się spodziewać, że owy nadejdzie. Krótko mówiąc, musi wiedzieć jak na niego zareagować. Na początku przetwarzania na owej taśmie znajduje się ciąg symboli wejściowych, a symbol pusty wypełnia wszystkie inne pola, zarówno po lewej stronie taśmy, jak i jej prawej stronie. Dodatkowo, należy nadmienić, że taśma jest nieskończenie długa w obie strony od ciągu wejściowego.
Można ową taśmę przedstawić np. w taki sposób:
Rzecz druga. Symbol.
Mówiąc o symbolach musimy wprowadzić pojęcie alfabetu.
Alfabet jest to skończony zbiór symboli/znaków (formalnie mówi się symboli, ale znak jest według mnie bardziej obrazowy), dowolnych, które jednoznacznie się definiują (tj. nie ma w nich dwóch znaków oznaczających to samo), posiadających znak pusty, czy też zabrzmieć bardziej znajomo może znak spacji, czyli znak oddzielający od siebie ciągi znaków.
Mając alfabet możemy definiować słowo. Słowo to ciąg znaków z alfabetu, który jeżeli nie jest pojedynczym znakiem pustym, nie zawiera znaku pustego, tj. mając alfabet cyfr słowem będzie np.: 123, ale "123 42" już słowem nie będzie, będzie parą słów. Pojedynczy znak pusty również będzie słowem.
Mając zdefiniowane słowo, widzimy że może być ich wiele, a ich wielość może złożyć się we zbiory. Zbiory tych słów nazywamy językami. Mając więc pojęcie czym jest słowo, symbol/znak, możemy rzec, że dalej rozumiany przez naz symbol, będzie słowem z dowolnego języka rozumianego przez maszynę.
Maszyna Turinga będzie związana z symbolami na dwa sposoby. Będzie odczytywać symbole z wejścia zadanego poprzez zbiór symboli dopuszczalnych w wejściu (czy też alfabetu wejścia) \(\sum\), oraz odczytywać i zapisywać symbole ze zbioru symboli dopuszczalnych na taśmie ogółem (czy też alfabetu taśmy) \(\Gamma\).
Rzecz trzecia. Skaner (głowica odczytująco-zapisująca).
Alan Turing pisząc swą rozprawę pisał o "skanowaniu" poszczególnych pól i ruchach maszyny w lewo lub prawo. Czym odbywało się to skanowanie nie miało większego znaczenia, ze względu na abstrakcyjny charakter maszyny, jednak dla lepszego pojęcia i fajniejszego zrozumienia, jak działa ten mechanizm, wprowadźmy sobie takie pojęcie. Nazwijmy ten skaner głowicą, jako że wyobrażamy go sobie jako urządzenie skanujące kwadracik pod nim. Odczytująco zapisującą, jako że maszyna zdolna jest zarówno odczytać jak i zapisać symbol na taśmie, i robi to podczas skanowania, tj. odczytując symbol, po zareagowaniu na niego, wymazuje go (czyli de facto zapisuje symbol pusty) bądź zapisuje dowolny ze zbioru \(\Gamma\) (inny bądź ten sam). Wspomniałem o ruchach w prawo i lewo, toteż głowica porusza się w lewo, o dowolną liczbę pól, w prawo, również o dowolną ilość pól (spotkać można definicje, według których poruszać się można o tylko jedno pole na raz, nie mniej efekt poruszenia o dowolną liczbę pól można osiągnąć w takim modelu komplikując funkcję przejść, więc przyjęcia założenia o tym że poruszać się może o dowolną, ustaloną wcześniej liczbę pól jest jak najbardziej zasadne), lub może nie ruszać się wcale (dla upartego można tę właściwość wyłączyć, sprowadzając zatrzymanie do pojedynczego ruchu w lewo a później w prawo, bądź odwrotnie).
Rzecz czwarta. Zbiór stanów i funkcja przejść.
Gdy mamy zdefiniowane wejście do owego urządzenia, musimy zdefiniować jak ma na nie reagować. Funkcję taką w maszynie Turinga, pełni zbiór stanów (lub jak kto woli przestrzeń stanów) oraz funkcja przejść/przesunięć.
Stan jest to pojęcie dosyć pierwotne, więc ciężko o jego definicję, toteż przyjmijmy że stan maszyny to aktualne wartości wszystkich właściwości w jakiejś tam chwili czasu. Pojedynczy stan jest zdeterminowany przez wejście jakie otrzymaliśmy oraz w jakim stanie byliśmy poprzednio, wedle funkcji przejść. Zaczynając jednak pracę, w jakim stanie jesteśmy? Jak rozpoznać, kiedy praca maszyny się zakończyła? No właśnie. Wśród wszystkich stanów ogólnych jakie posiada maszyna, musimy wyszczególnić trzy specyficzne: stan początkowy, stan akceptacji i stan odrzucenia (warto wspomnieć, że stanów odrzucenia jak i akceptacji może być wiele, tutaj jednak dla uproszczenia wyróżnimy pojedyncze. Zbiór łączący stany akceptacji i odrzucenia nazywamy zbiorem stanów końcowych maszyny.). Stan początkowy, wiadomo, stan z którego startujemy, ale czym są stany akceptacji i odrzucenia, czy też stan "tak" i stan "nie"? Są to odpowiedzi na zadane maszynie pytanie, czyli np. jeżeli definiowalibyśmy maszynę sprawdzającą czy podana przez nas liczba jest parzysta, stan końcowy musiałby nam mówić czy jest parzysta, czy nie jest parzysta. Rozwiązujemy tu więc problem decyzyjny. Problemy to jednak temat na osobny artykuł, dlatego na ten czas uznajmy, że problem decyzyjny to taki na który odpowiadamy tak lub nie. Skoro jednak odpowiadamy na pytanie, kończymy naszą pracę, toteż stan akceptacji i odrzucenia są stanami końcowymi.
No dobra. Ale mając zbiór stanów, w jaki sposób stwierdzić, na jakie stany z jakich stanów możemy przechodzić odczytując jakieś wejście? Jaką reakcję podjąć co zapisać? Przepis na rozwiązanie owej zagadki daje nam funkcja przejść czy też funkcja przesunięć.
Mówiąc o tym jak na wejście reaguję maszyna, mówiliśmy o trzech rzeczach: zmiana stanu, zapis/odczyt/wymazanie symbolu, przesunięcie głowicy. Wszystko to w reakcji na odczytany symbol. A więc, skoro musimy zdefiniować zachowanie/reakcję na owy symbol, taką funkcję właśnie pełnić będzie funkcja przejść.
Wspomnieliśmy wcześniej że stan maszyny zależy od wejścia i poprzedniego stanu, a więc na wejściu owej funkcji będą znajdować się właśnie te parametry.
Skoro musimy zaregować na te parametry, efektem/wyjściem tej funkcji będzie trójka, tj. stan do którego przejdziemy, jak przesunąć głowicę oraz co zapisać na taśmie w miejscu w którym jesteśmy aktualnie. Można by to zapisać wzorem:
\(\delta(stan_{poprzedni}, \textrm{wejście}) = (stan_{następny}, \textrm{przesunięcie}, \textrm{zapis/odczyt/wymazanie})\)
Ale coś długi ten wzór i paskudny, dlatego uprośćmy go trochę wprowadzając bardziej eleganckie oznacznia:
\(\delta(q_p, i) = (q_n, s, a)\)
O. Teraz zdecydowanie ładniej, ale należy uściślić, że:
- \(q_p\) oznacza stan poprzedni, \(q\) ponieważ zwyczajowo w literaturze stany oznaczane są przez \(q\) właśnie, \(p\) od angielskiego "\(p\)revious",
- \(i \) to wejście maszyny, ("\(i\)nput")
- \(q_n \)to stan następny, ("\(n\)ext")
- \(s\) to przesunięcie głowicy, ("\(s\)hift")
- \(a\) to akcja podejmowana przez głowicę ("\(a\)ction")
Żeby być tutaj już całkowicie dokładnym należy dodać że:
- \(\{q_p, q_n\} \in Q\), czyli stan poprzedni i następny muszą pochodzić ze stanów, które zdefiniowaliśmy w naszym zbiorze stanów
- \(i \in \sum\), czyli wejście musi pochodzić z alfabetu wejścia
- \(s \in \{L, R, S\}\), czyli przesunięcie może nastąpić w lewo ("\(L\)eft"), w prawo ("\(R\)ight") lub w ogóle się nie poruszyć ("\(S\)top")
- \(a \in \{W, E\}\), czyli podjęta akcja musi być zapisem na taśmie ("\(W\)rite"), lub wymazaniem z taśmy ("\(E\)rase")
Czyli mówiąc krótko i zwięźle, funkcja ta mówi jak będąc w jakimś stanie dostając jakieś wejście, przesunąć głowicę, na jaki stan ma przeskoczyć maszyna, oraz co ma zapisać na taśmie (lub z niej wymazać). Funkcja ta może być absolutnie dowolna. Ograniczeniem dla niej jest sama maszyna i wyobraźnia projektanta. Poniższy obrazek przedstawia, jak można by zwizualizować zbiór stanów, wraz z funkcją przejść, dla lepszego zrozumienia:
Rzecz piąta. Opis formalny.
"Farmazony" - zakrzyknąłby formalista - "Nic w tym ścisłego, brak więc nauki". Uściślijmy więc opis, okraśmy go we wzory i symbole. Jest to o tyle ważne, że przy pełnym zrozumieniu zagadnienia, znacznie upraszcza to opis instancji maszyny oraz powoduje jej ścisłą definicję, bez żadnych niedomówień.
A więc zacznijmy. Naszą maszynę definiować będzie 7 zmiennych. Samą maszynę oznaczmy literą \(M\).
Tych siedem kolejnych zmiennych wymieniliśmy już w poprzednich akapitach, a są to dokładnie:
- zbiór stanów, który oznaczymy sobie jako \(Q\),
- stan początkowy \(q_0\),
- stan akceptacji \(q_a\), ("\(a\)cceptance")
- stan odrzucenia \(q_r \) ("\(r\)eject"), należy dodatkowo pamiętać że \(q_a \neq q_r\)
- alfabet wejściowy bez symbolu pustego, czy też zbiór symboli dopuszczalnych wejścia \(\sum\)
- alfabet taśmy \(\Gamma\), czyli alfabet zawierający cały alfabet wejściowy i symbol pusty (i niekoniecznie do nich ograniczony)
- funkcja przejść/przesunięć \(\delta: Q \times\Gamma \rightarrow Q \times \Gamma \times\{L, R, S\}\)
A więc mamy krotkę:
\(M = \langle Q, q_0, q_a, q_r, \sum, \Gamma, \delta \rangle\)
Która jednoznacznie definuje nam maszynę Turinga. Sporządźmy więc opis formalny maszyny, którą zdefiniowaliśmy na przestrzeni artykułu.
\(Q = \{q_0, q_1, q_2\}\)
\(q_0 = q_0\)
\(q_a = q_3\)
\(q_r = q_4\)
\(\sum = \{ 1, 0, A\}\)
\(\Gamma = \{ 1, 0, A, \text{␣} \}\)
\(\delta(q, i)= \begin{cases} (q_0, R, W(i)) & \text{gdy } q=q_0 \space \text{i } i \in \{0, 1, \text{␣}\} \\ (q_1, L, W(A)) & \text{gdy } q=q_0 \space \text{i } i = A \\ (q_2, S, W(1)) & \text{gdy } q=q_1 \space \text{i } i = 0 \\ (q_3, S, W(0)) & \text{gdy } q=q_1 \space \text{i } i = 1 \\ \end{cases}\)
Rzecz szósta. Wizualizacja.
Tak więc mamy wszystko co potrzebowaliśmy do zdefiniowania naszej maszyny. Mając ją zdefiniowaną, spróbujmy dla ułatwienia zrozumienia, zwizualizować, jak mogłaby ona wyglądać w stanie, w którym aktualnie się znajduje na rysunku skanera. Jesteśmy w stanie \(q_0\) skanujemy właśnie \(0\), więc reakcją, zgodnie z funkcją przejść będzie zapisanie aktualnego wejścia na taśmę, przesunięcie głowicy w prawo oraz pozostanie w tym samym stanie co poprzednio.
Rzecz siódma. Determinizm maszyny Turinga.
Maszyna którą udało nam się zbudować, jest pełnoprawną maszyną Turinga. Warto wspomnieć, że nasza ma tylko jedną taśmę, do której zaczepiona jest jedna głowica. Istnieją, przez skomplikowanie funkcji przejść i zbioru stanów, wersje maszyn, które tych tasiem mają więcej, np. 2, 5, 10, w zależności do wyobraźni twórcy. Dodatkową właśnością owej naszej maszyny jest to, że jest deterministyczna. Co to oznacza? Oznacza to to, że na jedną interpretację symbolu, może wykonać jedną akcję i dokładnie wiemy jaką. Zupełnie inaczej zachowuje się niedeterministyczna maszyna Turinga.
Rzecz ósma. Niedeterministyczna maszyna Turinga.
Czemu niederministyczna? Ano dlatego, że na jedną intepretację symbolu, może dla niego mieć wiele ścieżek, czyli tych strzałek ze stanów, do wielu różnych stanów. Np. w ten sposób:
Mamy tu mały dysonans. Bo przecież odczytujemy jedynkę i mamy dwie ścieżki reakcji na nią? Coś tu jest nie tak, ale tylko intuicyjnie.
Otóż.
Niedeteminizm maszyny turinga polega na tym, że jeżeli stajemy przed wyborem, właśnie np. jak na obrazku, oczytując jedynkę, maszyna jakoby kopiuje się na dwa warianty, jakie może w tej sytuacji podjąć i każdy z tych skopiowanych wariantów kontunuuje według właśnej ścieżki. W tym przypadku jedna skopiowana maszyna pójdzie do \(q_1\), a druga do \(q_2\). Wszystko to oczywiście odbywa się równolegle ze sobą. Więc można powiedzieć, że niedeterministyczna maszyna turinga wykonuje wszystkie możliwe ścieżki wykonania swojej definicji na raz. I na tym polega jej niedeterminizm.
Jest to troszkę nieintuicyjne, bo w praktyce nie ma fizycznej implementacji tego ustrojstwa. Można próbować pisać programy, które będą się zrównoleglać w nieskończoność, ale zabraknie nam w końcu zasobów sprzętowych, żeby spełnić warunki definicyjne.
Ciekawą rzeczą jest fakt, że deterministyczna maszyna Turinga, jest szczególnym przypadkiem niedeterministycznej maszyny Turinga. Po prostu mając możliwość wykonywania wszystkich ścieżek wykonania jednocześnie, my zdefiniujemy sobie taką maszynę, która będzie miała tylko jedną ścieżkę. Ot cała zagadka.
Trzeba jeszcze, jako że przejścia ze stanów trochę nam zewoluowały, zaktualizować funkcję przejść, a zmodyfikujemy ją tylko, wprowadzając \(\mathcal{P}\), czyli oznacznie faktu, że reakcje wykonują się wszystkie na raz.
\(\delta: Q \times\Gamma \rightarrow\mathcal{P}( Q \times \Gamma \times\{L, R, S\})\)
Rzecz dziewiąta. Uniwersalna maszyna Turinga.
Ciekawą i wartą wspomnienia rzeczą jest również uniwersalna maszyna Turinga. Turing przedstawił ją również w swojej pracy, jako koncept, która na dowolne wejście, zamiast prostą zmianą stanu i poruszeniem głowicy i pisaniem czegokolwiek, może zareagować przekazaniem tego wejścia do dowolnie innej maszyny Turinga. Czyni to sytuację, że na dowolnym wejściu, możemy wykonać dowolną instrukcję. Brzmi znajomo? I tak miało zabrzmieć, gdyż jest prawie że model tego jak działają dzisiejsze programy i komputery (z dokładnością do poziomu abstrakcji).
Podsumowanie.
Jeżeli mielibyśmy wyliczać, modeli maszyn Turinga jest jeszcze kilka, ale są one na tyle dziwne, skomplikowane i nic nam nie wnoszące w dalszych rozważaniach, że pozwolę je sobie ominąć (Może kiedyś jeszcze o nich wspomnimy w ramach ciekawostki). Poruszone natomiast warto znać, ze względu na ich fundamentalność, jako podstawy wszystkich innych maszyn oraz dlatego, że będziemy się jeszcze do nich odwoływać w przyszłych rozważaniach i analizach na temat algorytmów oraz ich złożoności.
"Turing wielkim człowiekiem był" - można by delikatnie zmieniając słowa wieszcza, oddać hołd człowiekowi którego podwaliny informatyki dziś studiowaliśmy. Natomiast dla ciekawych szczegółów, które z oczywistych względów pominąłem, zapraszam do przestudiowania oryginału pracy naukowej, na którym, chociażby Turing udowadnia, że Entscheidungsproblem Hilberta nie ma rozwiązania, właśnie swoją maszyną. Link do pracy.
Dziękuję za uwagę i do zobaczenia w następnych artykułach!
Komentarze