Maszyna Turinga

Artystyczna wizja maszyny Turinga

Grafika przedstawiająca maszynę Turinga w stanie q₁ nad zerem na taśmie

Maszyna Turinga - zbudowany przez Alana Turinga abstrakcyjny model komputera służącego do wykonywania algorytmów, składającego się z nieskończenie długiej taśmy podzielonej na pola. Taśma bywa nieskończona jednostronnie albo obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna stale jest ustawiona nad jednym z pól oraz istnieje w jednym z M stanów. Zależnie od kombinacji stanu maszyny oraz pola maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo albo w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną liczbę takich rozkazów. Liczby N oraz M bywają dowolne, byle skończone. Czasem dopuszcza się też stan M+1, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga bywa traktowana jako jej program.

Każdy algorytm wyrażalny na maszynie Turinga da się wyrazić w rachunku lambda oraz odwrotnie. Gdyż 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 wielokrotnie do udowadniania nierozstrzygalności wielorakich 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ą maszyna 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, albowiem ilość danych, które potrafią przechowywać oraz przetwarzać jest skończona, tak więc dla każdego komputera istnieje tylko skończona ilość programów, które może wykonać. Mimo że ilość ta jest niewyobrażalnie wielka oraz w praktyce wielokrotnie wystarczająca, to bez względu na rozmiar pamięci, stale będzie istnieć program, którego maszyna nie będzie w stanie wykonać, albowiem jego kod (opis) po prostu nie mieści się w tej pamięci.

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

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

W informatyce dowodzi się równoważności wielu wielorakich wariantów maszyny Turinga. Np. nader ł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 dylematu teorii złożoności obliczeniowej – "P versus NP".

Mimo że maszyna Turinga jest abstrakcją o dużej mocy obliczeniowej (większej dla przykładu 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 potrafią 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:

Q – skończony zbiór stanów

q₀ – stan początkowy, q₀ ∈ 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 Γ, do którego nie trzeba 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 albo bez przesunięcia).

Przykłady maszyny Turinga

Podwajanie znaków

Zaprezentowano tutaj tabelę stanów reprezentującą przykładową Maszynę Turinga. Ta Maszyna ma za zadanie podwajanie znaków w podanym ciągu,

np. ciąg wejściowy ΦabcΦ (gdzie Φ to symbol pusty oznaczający koniec danych) zamieni na ΦaabbccΦ

Q = { q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₈, q₉, q₁₀, q₁₁, q₁₂ }

q₀ = q₀

F = { q₁₂ }

Γ = { Φ, a, b, c }

B = Φ

Σ = { a, b, c }

Kolumny tabeli są to elementy zbioru Q – dopuszczalne stany Maszyny Turinga, wiersze oznaczają kolejno wszystkie dopuszczalne symbole wejściowe (podczas wejścia w dany stan głowica czytająca Maszyny Turinga odczytuje aktualny symbol z taśmy oraz to jest właśnie jeden z tych symboli). Każda komórka tabeli zawiera w sobie instrukcje dla Maszyny Turinga, a mianowicie dla przykładu:

q₂ – oznacza kolejny stan, w którym znajdzie się maszyna po przejściu z aktualnego stanu

a – symbol, który zostanie umieszczony na tym polu taśmy

P – przesunięcie głowicy maszyny (L – w lewo o jedno pole, P – w prawo o jedno pole, – – niedobór przesunięcia głowicy)

Sprawdzanie palindromów

Weźmy wydatnie prostszą maszynę Turinga niż w przykładzie powyżej – będzie sprawdzać, czy dane słowo jest palindromem.

Q = { q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇ }

q₀ = q₀

F = { q₆, q₇ }

Γ = { Φ, a, b }

B = Φ

Σ = { a, b }

Ten artykuł trzeba dopracować zgodnie z zaleceniami edycyjnymi: sformatować tekst (pomoc: podział na sekcje, tabele). Dokładniejsze informacje o tym, co trzeba poprawić, być może leżą na stronie dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu.

Działanie dla ΦabaΦ

¡q0
ΦabaΦ

¡q1
ΦΦbaΦ

¡q1
ΦΦbaΦ

¡q1
ΦΦbaΦ

¡q1
ΦΦbaΦ

¡q3
ΦΦbaΦ

¡q5
ΦΦbΦΦ

¡q5
ΦΦbΦΦ

¡q0
ΦΦbΦΦ

¡q2
ΦΦΦΦΦ

¡q4
ΦΦΦΦΦ

¡q6 TAK
ΦΦΦΦΦ

Działanie dla ΦabbΦ

¡q0
ΦabbΦ

¡q1
ΦΦbbΦ

¡q1
ΦΦbbΦ

¡q1
ΦΦbbΦ

¡q3
ΦΦbbΦ

¡q7 NIE
ΦΦbbΦ

Negowanie w kodzie U2

Poniższy schemat przedstawia algorytm negowania liczby w kodzie U2. Zapis 0→1L trzeba interpretować: zamień 0 na 1 oraz przesuń głowicę w lewo

Inne ujęcie

Model przedstawiony przez Rogera Penrose'a w Nowym umyśle cesarza (ISBN 83-01-11819-9, str. 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 oraz jedynkę. Przy tym stany wewnętrzne są oznaczone liczbami dwójkowymi oraz maszyna zaczyna od stanu 0. Maszyna po każdej operacji zmienia stan wewnętrzny, znak na taśmie oraz przesuwa się w lewo albo w prawo. Może też się zatrzymać. Reguły oznacza się przez odpowiedni zestaw przejść, np. (ostatnia cyfra oznacza znak na taśmie oraz 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 wcale nie występuje, albowiem odpowiedź ma znaleźć się po lewej stronie maszyny. Dlatego R.STOP skraca się do STOP. W wyniku tego zapisujemy 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 dla przykładu ciąg

...000111111011111111000...

w ciąg

...00011000...

(Największy wspólny dzielnik liczb 6 oraz 8 to 2.)

Większą liczbę znaków da się zastąpić rozszerzoną notacją dwójkową. Dla przykładu 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,

zapisujemy stosując ekspansję jako

...000100101101010010110011010110101101000110000...

W rozszerzonej notacji dwójkowej da się zakodować też symbol oznaczający koniec wyniku, ale dla uproszczenia da się np. przyjąć, że maszyna oznacza jakoś pola, które przez nią przeszły oraz 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+1zwię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 da się zakodować oznaczając 0, 1, R, L, STOP, strzałkę oraz przecinek przez liczby od 0 do 6, czyli 0, 10, 110, 1110, 11110, 111110, 1111110. Jednak przecinek jest zbędny (wystarczy samo R, L albo STOP), tak jak stany wejściowe (o ile dane są podane po kolei, np. w XN+1 trzeba dodać np. 101 → 00R). Wtedy otrzymamy 0 oraz 0 → 0, 1 oraz 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) oraz końcowe (każdy opis kończy się symbolem R, L albo 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

Przeważajaca ilość jest niekompletna (bywa np., że zawierają więcej, niż cztery jedynki pod rząd, czyli są niepoprawnie określone) albo wcale się nie zatrzymuje, zdarzają się też powtórzenia. Żaden system kodowania nie dopuszcza wyeliminować wszystkich takich dat.

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

Sprawdź też

• maszyna RAM
• funkcja rekurencyjna
• Język rekurencyjny
• Język rekurencyjnie przeliczalny

Linki zewnętrzne

• Maszyna Turinga (ang.) w encyklopedii MathWorld
• Maszyna Turinga w serwisie edukacyjnym I LO w Tarnowie
• Prezentacja modelu maszyny Turinga zrealizowanej za pomocą klocków lego.