Maszyna Turinga

Maszyna Turinga – stworzony przez Alana Turinga abstrakcyjny model urządzenia służącego do wykonywania algorytmów. Maszyna składa się z bloku sterowania, głowicy odczytującej i zapisującej oraz nieskończenie długiej taśmy. W każdej komórce taśmy może mieścić się jeden symbol. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z Q stanów. Zależnie od kombinacji stanu maszyny i symbolu napotkanego na taśmie 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ą liczbę takich rozkazów. Czasem dopuszcza się też stan M+1, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.

Wstęp 
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 A posiadająca zdolność symulacji działania dowolnej innej maszyny Turinga B (opisanej jako dane wejściowe dla maszyny A) na dowolnych danych wejściowych dla maszyny B, nazywana jest uniwersalną maszyną Turinga. Praktycznym przybliżeniem realizacji uniwersalnej maszyny Turinga jest komputer, będący w stanie wykonać dowolny program na dowolnych danych. Jednak komputery nie są uniwersalnymi maszynami Turinga w sensie pierwotnej definicji, ponieważ ilość danych, które mogą przechowywać i przetwarzać jest skończona, tak więc dla każdego komputera istnieje tylko skończona liczba programów, które może wykonać. Mimo że liczba ta jest niewyobrażalnie wielka i w praktyce często wystarczająca, to bez względu na rozmiar pamięci, zawsze będzie istnieć program, którego maszyna nie będzie w stanie wykonać, ponieważ jego kod (opis) po prostu nie mieści się w tej pamięci.

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.

Można rozważać 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).

W informatyce dowodzi się równoważności wielu różnych wariantów maszyny Turinga. Np. dość łatwo jest pokazać, że maszyna Turinga z wieloma taśmami nie różni się istotnie od klasycznej maszyny jednotaśmowej. Również niedeterministyczne maszyny Turinga są równoważne deterministycznym. Rozważania na temat mocy obliczeniowej niedeterministycznych maszyn Turinga są podstawą centralnego problemu teorii złożoności obliczeniowej – „P versus NP”.

Mimo że maszyna Turinga jest abstrakcją o dużej mocy obliczeniowej (większej na przykład niż dowolny komputer), istnieje wiele problemów (np. problem stopu), których nie da się na niej rozwiązać. Matematycy rozważają więc (od czasów samego Turinga) silniejsze modele obliczeń, które mogą takim zadaniom podołać. Hipotetyczne maszyny potrafiące wykonywać takie obliczenia, nazywa się hiperkomputerami. Należy zauważyć, że przy obecnym stanie wiedzy nie jest jasne, czy prawa fizyki rządzące naszym światem pozwalają na skonstruowanie maszyn obliczeniowych silniejszych niż maszyna Turinga. Jest to pole aktywnych prac badawczych.

Zapis formalny 

Formalnie maszynę Turinga opisuje się poprzez krotkę:

 

gdzie:
  – skończony zbiór stanów
  – stan początkowy,
  – zbiór stanów końcowych
  – skończony zbiór dopuszczalnych symboli
  – symbol pusty,
  – zbiór symboli wejściowych – podzbiór zbioru  do którego nie należy 
  – 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).

Inne ujęcie 
Model przedstawiony przez Rogera Penrose’a w Nowym umyśle cesarza (s. 46–93, ) jest nieco inny, bardziej oszczędny, chociaż równoważny matematycznie.

Przyjmuje się, że maszyna obsługuje tylko dwa znaki na taśmie – zero i jedynkę. Przy tym stany wewnętrzne są oznaczone liczbami dwójkowymi i maszyna zaczyna od stanu 0. Maszyna po każdej operacji zmienia stan wewnętrzny, znak na taśmie i przesuwa się w lewo lub w prawo. Może też się zatrzymać. Reguły oznacza się przez odpowiedni zestaw przejść, np. (ostatnia cyfra oznacza znak na taśmie i jest wytłuszczona dla czytelności)

 00 → 00R,
 01 → 11R,
 10 → 01R.STOP,
 11 → 11R.

Jest to maszyna UN+1 zwiększająca liczbę zapisaną w systemie jedynkowym o jeden, czyli dopisująca na końcu pierwszego ciągu jedynek na taśmie jeszcze jedną jedynkę.

Można przyjąć, że instrukcja L.STOP nigdy nie występuje, gdyż odpowiedź ma znaleźć się po lewej stronie maszyny. Dlatego R.STOP skraca się do STOP. W ten sposób zapisuje się maszynę UN×2 jako

 00 → 00R,
 01 → 10R,
 10 → 101L,
 11 → 11R,
 100 → 110R,
 101 → 1000R,
 110 → 01STOP,
 111 → 111R,
 1000 → 1011L,
 1001 → 1001R,
 1010 → 101L,
 1011 → 1011L.

Opis maszyny EUC, znajdującej największy wspólny dzielnik dwóch liczb naturalnych zawiera 22 instrukcje dotyczące 11 stanów wewnętrznych (tylko 3 z tych instrukcji powodują zmianą zapisu na taśmie). Przekształca ona na przykład ciąg
 ...000111111011111111000...
w ciąg
 ...00011000...
(Największy wspólny dzielnik liczb 6 i 8 to 2.)

Większą liczbę znaków można zastąpić rozszerzoną notacją dwójkową. Na przykład 0 może oznaczać 0, 10 – 1, a 110 – 2 itp. Jeżeli 2 oznacza przecinek, ciąg liczb dwójkowych
 101, 1101, 0, 1, 1, 100,
zapisuje się, stosując ekspansję jako
 ...000100101101010010110011010110101101000110000...

W rozszerzonej notacji dwójkowej można zakodować też symbol oznaczający koniec wyniku, ale dla uproszczenia można np. przyjąć, że maszyna oznacza jakoś pola, które przez nią przeszły i nie trzeba sprawdzać całej taśmy, aby przekonać się, że w dalszej części zawiera same zera.

Maszyny wykorzystujące taki kod są zwykle bardziej skomplikowane, ale szybsze. Np. maszyna XN+1 zwiększająca liczbę zapisaną w systemie dwójkowym za pomocą rozszerzonej notacji dwójkowej o 1:

 00 → 00R,
 01 → 11R,
 10 → 00R,
 11 → 101R,
 100 → 110L,
 101 → 101R,
 110 → 01STOP,
 111 → 1000L,
 1000 → 1011L,
 1001 → 1001R,
 1010 → 1100R,
 1011 → 101R,
 1101 → 1111R,
 1110 → 111R,
 1111 → 1110R.

Maszyna XN×2 mnożąca przez dwa jest jednak prostsza od UN×2:

 00 → 00R,
 01 → 11R,
 10 → 00R,
 11 → 100R,
 100 → 111R,
 110 → 00STOP.

Opis maszyny Turinga można zakodować, oznaczając 0, 1, R, L, STOP, strzałkę i przecinek przez liczby od 0 do 6, czyli 0, 10, 110, 1110, 11110, 111110, 1111110. Jednak przecinek jest zbędny (wystarczy samo R, L lub STOP), tak jak stany wejściowe (o ile dane są podane po kolei, np. w XN+1 należy dodać np. 101 → 00R). Wtedy otrzymamy 0 i 0 → 0, 1 i 1 → 10, R → 110, L → 1110 oraz STOP → 11110. Maszyna XN+1 jest teraz opisana przez
 00R 11R 00R 101R 110L 101R 01STOP 1000L 1011L 1001L 1100R 101R 00R 1111R 111R 1110R
Pomijając początkowe (00R to początek każdej maszyny Turinga) i końcowe (każdy opis kończy się symbolem R, L lub STOP), 110 zapisuje się
 10101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100
czyli dziesiętnie
 450 813 704 461 563 958 982 113 775 643 437 908

Z kolei numer dwójkowy UN+1 to
 101011010111101010
czyli dziesiętnie 177 642.

XN×2 ma numer 1 456 581 339, a UN×2 – 1 492 923 420 919 872 026 917 547 669.

Pierwsze trzynaście maszyn:
 T0: 00 → 00R, 01 → 00R,
 T1: 00 → 00R, 01 → 00L,
 T2: 00 → 00R, 01 → 01R,
 T3: 00 → 00R, 01 → 00STOP,
 T4: 00 → 00R, 01 → 10R,
 T5: 00 → 00R, 01 → 01L,
 T6: 00 → 00R, 01 → 00R, 10 → 00R,
 T7: 00 → 00R, 01 →???,
 T8: 00 → 00R, 01 → 100R,
 T9: 00 → 00R, 01 → 10L,
 T10: 00 → 00R, 01 → 11R,
 T11: 00 → 00R, 01 → 01STOP,
 T12: 00 → 00R, 01 → 00R, 10 → 00R

Większość jest niekompletna (bywa na przykład, że zawierają więcej, niż cztery jedynki z rzędu, czyli są niepoprawnie określone) lub nigdy się nie zatrzymuje, zdarzają się też powtórzenia. Żaden system kodowania nie pozwala wyeliminować wszystkich takich dat.

Pewna skomplikowana maszyna Turinga zastosowana do numeru dowolnej maszyny Turinga i jej argumentu da wynik działania tej maszyny.

Zobacz też 
 automat Büchiego
 funkcja rekurencyjna
 maszyna RAM
 mrówka Langtona
 niedeterministyczna maszyna Turinga

Przypisy

Linki zewnętrzne 
 Polskojęzyczne
 Maszyna Turinga w serwisie edukacyjnym I LO w Tarnowie

 Anglojęzyczne
 Prezentacja modelu maszyny Turinga zrealizowanej za pomocą klocków lego.
 
  Turing machines , Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].

 
 

Teoria obliczeń
Teoria automatów