Alan Mathison Turing.doc

Maszyna Turinga

Paweł Grądzki Kl. I Ti
Alan Mathison Turing

1912 - 1954

Alan Mathison Turing (ur. 23 czerwca 1912 w Londynie - zm. 7 czerwca 1954 w Wilmslow) - angielski matematyk, twórca maszyny Turinga i jeden z twórców informatyki.

Jego ojciec, Julius Turing był pracownikiem indyjskiej służby cywilnej i razem z żoną Ethel Turing mieszkał w Chatrapur niedaleko Madrasu w południowych Indiach. Tam też Alan Turing został poczęty jesienią 1911. Rodzice przyszłego matematyka chcieli aby dziecko urodziło się w Anglii. Tak też się stało. 23 czerwca 1912 w Londynie urodził się Alan Mathison Turing. Jego ojciec niedługo po jego narodzinach wrócił do Indii natomiast matka wyjechała piętnaście miesięcy później, w połowie września 1913, pozostawiając Alana pod opieką nianiek.

W 1926 roku Alan Turing rozpoczął naukę w Scherbone School w Dorset. Od samego początku nauki wykazywał duże zdolności w dziedzinie nauk ścisłych, jednak źle czuł się w szkole, która kształciła przyszłą kadrę przywódczą Imperium Brytyjskiego.

Uczęszczając do Sherbone School, Alan odkrył swoją prawdziwą orientację seksualną, wówczas też zakochał się w Christoperze Moracomie. Ten jednak zmarł niedługo później - 13 lutego 1930 na gruźlicę. Po śmierci ukochanego, Turing zaczął jeszcze ciężej pracować aż w 1931 uzyskał stypendium naukowe na King's College w Cambridge.

Przebywając w Cambridge Turing napisał swoją prawdopodobnie najważniejszą pracę matematyczną On Computable Numbers czyli O liczbach obliczalnych. To właśnie w niej wprowadził abstrakcyjną maszynę, która była w stanie wykonywać zaprogramowaną matematyczną operacją czyli tak zwany algorytm. Maszyna mogła wykonać jednak tylko jeden, określony algorytm, na przykład mogła podnieść liczbę do kwadratu, podzielić, dodać, odjąć. Według Turinga liczby miały być podawane maszynie za pomocą papierowej taśmy podobnej do taśmy z melodią zapisaną dla pianoli. W swojej pracy Turing opisał wiele takich maszyn, które uzyskały wspólne miano maszyn Turinga. Następnie Turing opracował tak zwaną uniwersalną maszynę Turinga, która w zależności od instrukcji zapisanej na taśmie, miała wykonywać dowolną operację. W ten sam sposób udowodnił, że nie istnieje algorytm pozwalający odpowiedzieć na pytanie dotyczące nierozstrzygalności każdego innego twierdzenia, a zatem nawet uniwersalna maszyna Turinga nie była w stanie zidentyfikować wszystkich nierozstrzygalnych stwierdzeń. Było to ostateczne rozwiązania zagadnienia nierozstrzygalności wprowadzonego do logiki matematycznej przez Kurta Gödla. W tej samej pracy Turing przedstawił schemat pierwszego komputera przygotowany w oparciu o prace Charlesa Babbage'a i jego projekt Maszyny Różniczkowej nr 2. Był to projekt, którego realizacja wykraczała poza możliwości ówczesnej techniki, jednakże z inżynierskiego punktu widzenia był on zupełnie prawidłowy. Dzięki pracy O liczbach obliczalnych, w wieku 26 lat, Turing został uznany za jednego z najlepszych matematyków świata. Bardzo szybko robił karierę naukową, został nawet członkiem King's College.

W 1939 roku Rządowa Szkoła Kodów i Szyfrów zaproponowała Alanowi podjęcie pracy kryptoanalityka w Bletchley. Tam też matematyk (na przełomie 1939 i 1940 roku) zaprojektował tzw. bombę Turinga (częściowo w oparciu o prace polskich kryptoanalityków, np. Mariana Rejewskiego – zob.. bomba kryptologiczna), urządzenie służące do łamania kodu Enigmy. Było to urządzenie, dzięki któremu rozszyfrowywanie wiadomości zapisanych przy użyciu niemieckiej maszyny szyfrującej Enigma było dużo prostsze, tańsze, a co najważniejsze - skuteczniejsze. Bletchey posiadało piętnaście takich bomb, każdą przeznaczoną do jednej wiadomości.

W 1941 roku nastąpiła zmiana na stanowisku dyrektora Bletchley. Nowy szef, komandor Edward Travis zablokował kryptoanalitykom dostęp do funduszy na badania i budowę bomb. Wówczas Alan Turing i jego współpracownicy zwrócili się bezpośrednio do Winstona Churchilla po dotacje na prace związane z kryptoanalizą. Dotacje te otrzymali i w rok później Bletchley posiadało już czterdzieści dziewięć bomb. Powstała także stacja bomb w Gayhurst Manor. Wówczas (pośrednio) publicznie ogłoszono rekrutację do Bletchley, publikując w Daily Telegraph krzyżówkę. Sześciu czytelników, którzy poprawnie ją rozwiązali i przeszli specjalny test zorganizowany przez MI-6, zostało zatrudnionych razem z Turingiem w Bletchley.

Po wojnie Alan Turing zaprojektował jeden z pierwszych elektronicznych, programowanych komputerów. Był również pomysłodawcą tak zwanego testu Turinga – eksperymentu będącego próbą formalnego zdefiniowania sztucznej inteligencji.

W 1952 roku włamano się do domu Alana Turinga. Gdy zgłosił to na policję, wyjawił nieopatrznie, że jest homoseksualny. Wówczas został oskarżony o naruszenie moralności publicznej, wytoczono przeciwko niemu głośny jak na owe czasy proces. Jako karę orzeczono odebranie klauzuli dostępu do poufnych informacji oraz zakazano udziału w badaniach związanych z konstrukcją komputera. Zmuszono go do konsultacji z psychiatrą i kuracji hormonalnej. Jego zdrowie pogorszyło się, zachorował na depresję, utył i stał się impotentem. 7 czerwca 1954 Alan Turing, zamknął się w swojej sypialni i popełnił samobójstwo spożywając jabłko zanurzone wcześniej w cyjanku.

W roku 1937 angielski matematyk Alan Turing pracując nad koncepcją obliczalności funkcji matematycznych opisuje bardzo prostą maszynę logiczną, która dziś nosi nazwę Maszyny Turinga. Pomimo swej prostoty posiada ona obecnie olbrzymie znaczenie teoretyczne, ponieważ wszystkie współczesne komputery dają się do niej sprowadzić. Problem jest rozwiązalny na komputerze, jeśli da się zdefiniować rozwiązującą go maszynę Turinga.

Budowa Maszyny Turinga

Pod koniec lat trzydziestych ubiegłego wieku Alan

Turing nie posiadał do swojej dyspozycji komputerów, ponieważ w owym czasie ich jeszcze nie było. Dlatego na potrzeby swoich badań nad problemami obliczalności opracował model maszyny, który można zrealizować nawet na kartce papieru. Maszyna Turinga zbudowana jest z trzech głównych elementów:

·         Nieskończonej taśmy zawierającej komórki z przetwarzanymi symbolami

·         Ruchomej głowicy zapisująco-odczytującej.

·         Układu sterowania głowicą.

Taśma
 

Nieskończona taśma jest odpowiednikiem współczesnej pamięci komputera. Taśma dzieli się na komórki, w których umieszczone zostały symbole, czyli po prostu znaki przetwarzane przez maszynę Turinga. Symbole te stanowią odpowiednik danych wejściowych. Maszyna Turinga odczytuje te dane z kolejnych komórek i przetwarza na inne symbole, czyli dane wyjściowe. Wyniki obliczeń również są zapisywane w komórkach taśmy.
 

Można definiować różne symbole dla maszyny Turinga. Najczęściej rozważa się jedynie symbole 0, 1 oraz tzw. znak pusty - czyli zawartość komórki, która nie zawiera żadnej danej do przetworzenia.  Wbrew pozorom taki prymitywny zbiór trzech symboli jest równoważny logicznie dowolnemu innemu zbiorowi. Przecież współczesne komputery wewnętrznie operują jedynie na bitach, a mimo to są w stanie przetwarzać prawie dowolną informację z obrazami, dźwiękiem i filmami włącznie.

Głowica zapisująco-odczytująca

Aby przetwarzać dane, maszyna Turinga musi je odczytywać i zapisywać na taśmę. Do tego celu przeznaczona jest właśnie głowica zapisująco-odczytująca, która odpowiada funkcjonalnie urządzeniom wejścia/wyjścia współczesnych komputerów lub układom odczytu i zapisu pamięci.

Głowica zawsze znajduje się nad jedną z komórek taśmy. Może ona odczytywać zawartość tej komórki oraz zapisywać do niej inny symbol - na tej zasadzie odbywa się przetwarzanie danych - z jednych symboli otrzymujemy inne. Oprócz odczytywania i zapisywania symboli w komórkach głowica wykonuje ruchy w prawo i w lewo do sąsiednich komórek na taśmie. W ten sposób może się ona przemieścić do dowolnie wybranej komórki taśmy.

Przed rozpoczęciem pracy maszyny Turinga głowica jest zawsze ustawiana nad komórką taśmy zawierającą pierwszy symbol do przetworzenia.

Układ sterowania

Przetwarzaniem informacji zarządza układ sterowania głowicą. Jego współczesnym odpowiednikiem jest procesor komputera. Układ ten odczytuje za pomocą głowicy symbole z komórek taśmy oraz przesyła do głowicy symbole do zapisu w komórkach. Dodatkowo nakazuje on głowicy przemieścić się do sąsiedniej komórki w lewo lub w prawo.

Podstawą działania maszyny Turinga są stany układu sterowania. Jest to pojęcie trudne do zrozumienia dla początkujących, jednakże gdy raz to się stanie, maszyna Turinga okaże się bardzo prostym automatem, który będziemy mogli dowolnie programować. Stan układu sterowania określa jednoznacznie jaką operację wykona, jak zareaguje maszyna Turinga, gdy odczyta z taśmy określony symbol.

Zatem operacje wykonywane przez układ sterowania zależą od dwóch czynników:

1. Symbolu odczytanego z komórki na taśmie.
2. Bieżącego stanu układu sterującego.

Stany będziemy określać kolejnymi nazwami: q0, q1, q2, ... ,qn, gdzie q0 jest stanem początkowym, w którym znajduje się maszyna Turinga przed rozpoczęciem przetwarzania symboli na taśmie.

Instrukcją dla maszyny Turinga jest następująca piątka symboli:
 

S0 i qi są tzw. częścią identyfikacyjną instrukcji. Maszyna Turinga wykonuje tyle różnych instrukcji, ile zdefiniujemy części identyfikacyjnych - w programie nie może być dwóch różnych instrukcji o identycznej części identyfikacyjnej. Powód jest oczywisty - którą instrukcję należałoby w takim wypadku wykonać?

Sz, qj i L/P są tzw. częścią operacyjną, która określa jakie działanie podejmuje dana instrukcja. Części operacyjne różnych instrukcji mogą być takie same - oznacza to jedynie, iż instrukcje te wykonują dokładnie to samo działanie.

Szybko, zanim ta wiedza ulotni się nam w niedostępne obszary mózgu, podajmy odpowiedni przykład. Oto on:

(A, q0, B, q0, R)

Co robi ta instrukcja? Otóż jeżeli odczytanym przez głowicę symbolem z taśmy będzie literka A, a układ sterowania znajduje się w stanie q0, to głowica zamieni ten symbol na B, stan wewnętrzny nie zmieni się (pozostanie dalej q0), a głowica przesunie się do sąsiedniej komórki po prawej stronie. Zawile? Chyba nie.

Pierwsze dwa elementy określają jednoznacznie instrukcję. Pozostałe trzy określają, co w ramach tej instrukcji należy zrobić, czyli jaki symbol umieścić w bieżącej komórce taśmy, w jaki nowy stan przejść i w którą stronę przesunąć głowicę.

Programem dla maszyny Turinga jest tablica, w której określamy wszystkie wykonywalne przez nią instrukcje. Kolejność tych instrukcji w żaden sposób nie jest istotna. Maszyna Turinga rozpoznaje instrukcje po symbolu z taśmy i swoim stanie wewnętrznym. Jeśli w tablicy zabraknie dla tej kombinacji odpowiedniej instrukcji, to program zatrzymuje się.

To stworzony przez Alana Turinga abstrakcyjny model komputera służący do wykonywania algorytmów. Każdy algorytm wyrażalny na maszynie Turinga można wyrazić w rachunku lambda i odwrotnie. Ponieważ jednak maszyny Turinga rozszerza się bardzo trudno, zaś rachunek lambda bardzo łatwo, w praktyce są one o wiele mniej popularne jako rzeczywiste modele obliczeń. Są za to używane często do udowadniania nierozstrzygalności różnych problemów.

Maszyna Turinga składa się z nieskończenie długiej taśmy podzielonej na pola. Taśma może być nieskończona jednostronnie lub obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z M stanów. Zależnie od kombinacji stanu maszyny i pola maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną ilość takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan (M+1)-szy, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.

Maszyna posiadająca zdolność wykonywania dowolnego programu jest nazywana uniwersalną maszyna Turinga. Praktyczną realizacją uniwersalnej Maszyny Turinga jest komputer.

Można rozważać bardzo wiele różnych wariantów maszyny Turinga. Na przykład nie ma potrzeby pozwalać na pozostanie maszyny na tym samym polu, ponieważ maszyna musi albo zakończyć obliczenia przez zapętlenie, albo po nie więcej niż N*M krokach dane pole opuścić i wystarczy wtedy przyjąć dla danej kombinacji początkowej stany podczas opuszczania pola.

Istnieją też maszyny Turinga wielotaśmowe lub niedeterministyczne (gdzie jednej parze (symbol, stan) może odpowiadać kilka instrukcji) oraz wielowymiarowe (prostą dwuwymiarową maszyną Turinga jest mrówka Langtona).

Zapis formalny

Formalnie Maszynę Turinga opisuje się poprzez siódemkę:

MT = < Q, Σ, δ, Γ, q0, B, F >

gdzie:

Q - skończony zbiór stanów

q0 - stan początkowy, q0 ∈ Q

F - zbiór stanów końcowych

Γ - skończony zbiór dopuszczalnych symboli

B - symbol pusty, B ∈ Γ

Σ - zbiór symboli wejściowych - podzbiór zbioru Γ nie zawierający B

δ - funkcja opisana następująco:

→

co oznacza że jest to funkcja pobierająca aktualny stan maszyny oraz symbol wejściowy a dającą w wyniku symbol jaki ma się pojawić na taśmie, kolejny stan maszyny oraz przesunięcie głowicy maszyny (lewo, prawo lub bez przesunięcia).