Maszyna Turinga – czym jest?
Maszyna Turinga to prosty model automatu logicznego, składający się z taśmy, ruchomej głowicy i układu sterującego. Został opracowany w 1936 roku przez angielskiego matematyka i kryptologa Alana Turinga. Naukowiec nie mógł korzystać z komputerów, gdyż jeszcze nie istniały. Dlatego postanowił stworzyć maszynę, która pomoże w jego badaniach. Obecnie wynalazek Turinga nadal posiada ogromne znaczenie, ponieważ można prowadzić nim wszystkie komputery.
Maszyna Turinga – jak działa?
Model Maszyny Turinga działa na zasadzie odczytywania i zapisywania symboli na taśmie. W każdej komórce taśmy może znajdować się tylko jeden symbol. Maszyna zawsze jest umieszczona nad jednym z pól i znajduje się w jednym z Q stanów. Stany przyjmują wartości od q0 do qn, gdzie q0 określa stan początkowy.
Pojedyncza instrukcja dla maszyny Turinga zawiera pięć symboli:
- So (symbol odczytywany z aktualnej komórki),
- qi (aktualny stan układu sterującego),
- Sz (znak, który ma zostać zapisany w aktualnej komórce),
- qj (stan, w który ma przejść układ sterowania po wykonaniu instrukcji),
- L/R (zmiana położenia głowicy w lewo (L) lub w prawo(R)).
W zależności od kombinacji stanu maszyny i symbolu, który napotyka na taśmie, maszyna zapisuje nową wartość w danym polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Działanie to określa się rozkazem. Maszyna Turinga jest sterowana listą, która zawiera dowolną liczbę takich rozkazów. Czasami dopuszczany jest także stan M+1, sygnalizujący zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.
Budowa Maszyny Turinga
Maszyna Turinga charakteryzuje się niezwykłą prostotą. Zbudowana jest z trzech podstawowych elementów: nieskończenie długiej taśmy zawierającej komórki z przetwarzanymi symbolami, ruchomej głowicy odczytująco-zapisującej i układu sterowania głowicą.
Taśma
Taśma to najistotniejszy element w Maszynie Turinga, który jest głównym nośnikiem danych. Składa się z komórek taśmy, zawierających symbole. Głowica, będąca częścią układu sterującego, odczytuje i zapisuje symbole na taśmie, przesuwając się w lewo lub w prawo w zależności od działania maszyny. Taśma odpowiada aktualnie pamięci komputera.
Głowica
Kolejnym ważnym elementem maszyny jest głowica, czyli mechaniczna wypustka, która odpowiada za analizę symboli zawartych w komórkach. Odczytuje je i zapisuje na taśmę. Tym sposobem odbywa się przetwarzanie danych, w wyniku czego z jednych symboli otrzymuje się inne. Głowica porusza się w prawo lub lewo, zgodnie z kolejnością, jaką ma dla niej system. Przed rozpoczęciem pracy powinna zawsze być ustawiona nad komórką taśmy zawierającą pierwszy symbol do przetworzenia. Głowica stanowi odpowiedź na urządzenia wejścia i wyjścia współczesnym sprzętom.
Układ sterowania
Układ sterujący Maszyny Turinga odpowiada za programowanie kolejnych kroków obliczeń. Poprzez zdefiniowane instrukcje zawarte na taśmie, maszyna przetwarza dane i realizuje algorytmy matematyczne, wykorzystując moc obliczeniową głowicy odczytującej i zapisującej. Współczesnym odpowiednikiem układu sterowania jest procesor komputera.
Kim był Alan Turing?
Alan Mathison Turing urodził się 23 czerwca 1912 roku w Londynie. Był matematykiem i kryptologiem. Miał ogromny wkład w rozwój kryptologii, informatyki oraz biologii matematycznej. Jest twórcą koncepcji maszyny Turinga. To także jeden z ojców sztucznej inteligencji, który zaproponował test Turinga. W czasie II wojny światowej pracował nad złamaniem szyfrów III Rzeszy. Opracował wówczas nową maszynę („Bomba”), która była w stanie rozszyfrować wiadomości Enigmy. Zmarł 7 czerwca 1954 w Wilmslow, popełniając samobójstwo.
Test Turinga
Test Turinga został zaproponowany po raz pierwszy przez Alana Turinga w 1950 roku. Miał on celu określenie, czy maszyna potrafi zachować się na tyle inteligentnie, aby mogła zostać uznana za człowieka. W teście sędzia przeprowadza rozmowę tekstową z niewidocznym dla niego partnerem, którym może być człowiek lub maszyna. Jeżeli po zakończeniu rozmowy, sędzia ten nie jest w stanie określić, czy rozmawiał z maszyną, czy z człowiekiem, oznacza to, że maszyna zdała test Turinga i osiągnęła inteligencję porównywalną z ludzką lub nie do odróżnienia od niej.
Kompletność Turinga
Kompletność Turinga (Turing Completes) to cecha systemu przetwarzającego dane lub języka programowania. Oznacza, że taki system jest w stanie rozwiązać podobną klasę problemów obliczeniowych, które również rozwiąże Maszyna Turinga. Kompletność Turinga posiada szerokie zastosowanie w informatyce i innych dziedzinach nauki. Używa się jej m.in. do tworzenia algorytmów i programów komputerowych oraz do rozwiązywania skomplikowanych problemów matematycznych. Stosuje się ją także w badaniach nad sztuczną inteligencją.