Maszyna Turinga

Maszyna Turinga – stworzony przez Alana Turinga, w 1936 roku, abstrakcyjny model urządzenia służącego do wykonywania algorytmów^[1]. Powstała w celu udowodnienia hipotezy nazwanej później hipotezą Churcha-Turinga^[2][3]. Jest równoznaczy drugiemu modelowi, rachunkowi lambda, stworzonego przez Alonzo Churcha.

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.

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.

Formalnie maszynę Turinga opisuje się poprzez krotkę:

${\displaystyle MT=\;<Q,\Sigma ,\delta ,\Gamma ,q_{0},B,F>}$

gdzie:

${\displaystyle Q}$ – skończony zbiór stanów

${\displaystyle q_{0}\in Q}$ – stan początkowy,

${\displaystyle F}$ – zbiór stanów końcowych

${\displaystyle \Gamma }$ – skończony zbiór dopuszczalnych symboli

${\displaystyle B\in \Gamma }$ – symbol pusty,

${\displaystyle \Sigma }$ – zbiór symboli wejściowych – podzbiór zbioru ${\displaystyle \Gamma ,}$ do którego nie należy ${\displaystyle B}$

${\displaystyle \delta }$ – funkcja opisana następująco:

${\displaystyle \delta :\Gamma \times Q\to Q\times \Gamma \times \{L,P,-\}}$

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)^[4].

Model przedstawiony przez Rogera Penrose’a w Nowym umyśle cesarza (s. 46–93, ISBN 83-01-11819-9) 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.

• automat Büchiego
• funkcja rekurencyjna
• maszyna RAM
• mrówka Langtona
• niedeterministyczna maszyna Turinga

• Agnijo Banerjee, David Darling: Dziwna matematyka. Helion S.A., 2020. ISBN 83-283-5687-2.
• John E. Hopcroft, Rajeew Motwani, Jeffrey D. Ullman: Wprowadzenie do teorii automatów, języków i obliczeń. Wyd. Wyd. 2. Warszawa: Wydawnictwo Naukowe PWN, 2005. ISBN 978-83-01-14502-6.

Polskojęzyczne

• Maszyna Turinga w serwisie edukacyjnym I LO w Tarnowie

Anglojęzyczne

• Prezentacja modelu maszyny Turinga zrealizowanej za pomocą klocków lego.
• Eric W.E.W. Weisstein Eric W.E.W., Turing Machine, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Turing machines (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].

Artykuły na Stanford Encyclopedia of Philosophy (ang.) [dostęp 2018-09-25]:

• DavidD. Barker-Plummer DavidD., Turing Machines [online], 26 czerwca 2012 .
• LiesbethL. De Mol LiesbethL., Turing Machines, 24 września 2018 .