Maszyna Turinga

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Definicja intuicyjna:

Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej „głowicy”, wykonującej proste operacje na zapisanych na taśmie wartościach.

Artystyczna wizja maszyny Turinga
Grafika przedstawiająca maszynę Turinga w stanie q1 nad zerem na taśmie

Maszyna Turinga – stworzony 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 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ą liczbę takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. 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[edytuj | edytuj kod]

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 ilość programów, które może wykonać. Mimo że ilość 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.

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).

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[edytuj | edytuj kod]

Formalnie Maszynę Turinga opisuje się poprzez krotkę:

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

gdzie:

Q – skończony zbiór stanów
q0stan 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 Γ, do którego nie należy B
δ – funkcja opisana następująco:
\delta : \Gamma \times Q \rightarrow 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).

Przykłady maszyny Turinga[edytuj | edytuj kod]

Podwajanie znaków[edytuj | edytuj kod]

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 = {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12}
q0 = q0
F = {q12}
Γ = {Φ, a, b, c}
B = Φ
Σ = {a, b, c}
Σ+B\Q q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 q11 q12
Φ q12
-,-
q2
Φ,P
q3
a,P
q4
a,L
q5
Φ,L
q0
Φ,P
q7
Φ,P
q8
b,P
q4
b,L
q10
Φ,P
q11
c,P
q4
c,L
s t a n
b i e r n y
a q1
Φ,P
q1
a,P
q2
a,P
q12
-,-
q4
a,L
q5
a,L
q6
a,P
q7
a,P
q12
-,-
q9
a,P
q10
a,P
q12
-,-
b q6
Φ,P
q1
b,P
q2
b,P
q12
-,-
q4
b,L
q5
b,L
q6
b,P
q7
b,P
q12
-,-
q9
b,P
q10
b,P
q12
-,-
c q9
Φ,P
q1
c,P
q2
c,P
q12
-,-
q4
c,L
q5
c,L
q6
c,P
q7
c,P
q12
-,-
q10
c,P
q9
c,P
q12
-,-

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 i 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:

q2
a,P
q2 – 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, – – brak przesunięcia głowicy)

Sprawdzanie palindromów[edytuj | edytuj kod]

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

Q = {q0, q1, q2, q3, q4, q5, q6, q7}
q0 = q0
F = {q6, q7}
Γ = {Φ, a, b}
B = Φ
Σ = {a, b}
q0 q1 q2 q3 q4 q5 q6 q7
Φ q6
-,-
q3
Φ,L
q4
Φ,L
q6
-,-
q6
-,-
q0
Φ,P
TAK NIE
a q1
Φ,P
q1
a,P
q2
a,P
q5
Φ,L
q7
-,-
q5
a,L
b q2
Φ,P
q1
b,P
q2
b,P
q7
-,-
q5
Φ,L
q5
b,L

Działanie dla ΦabaΦ[edytuj | edytuj kod]

¡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Φ[edytuj | edytuj kod]

¡q0
ΦabbΦ
¡q1
ΦΦbbΦ
¡q1
ΦΦbbΦ
¡q1
ΦΦbbΦ
¡q3
ΦΦbbΦ
¡q7 NIE
ΦΦbbΦ

Negowanie w kodzie U2[edytuj | edytuj kod]

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

Algorytm negowania liczby w kodzie U2

Przykład odwracania liczby -8 przy pomocy algorytmu opisanego powyższym diagramem:

Zapis (I,J;0→1L) oznacza

  • wykonano przejście pomiędzy stanami I i J
  • zmieniono 0 na 1 na pozycji głowicy
  • przesunięto głowicę w lewo

Spis przejść wraz ze stanem taśmy, nawiasy prostokątne wskazują położenie głowicy.

 0. [#]#1000#
 1. (A,A;#→#R) #[#]1000#
 2. (A,A;#→#R) ##[1]000#
 3. (A,B;1→0R) ##0[0]00#
 4. (B,B;0→1R) ##01[0]0#
 5. (B,B;0→1R) ##011[0]#
 6. (B,B;0→1R) ##0111[#]
 7. (B,C;#→#L) ##011[1]#
 8. (C,C;1→0L) ##01[1]0#
 9. (C,C;1→0L) ##0[1]00#
10. (C,C;1→0L) ##[0]000#
11. (C,D;0→1L) #[#]1000#
12. (D,E;#→0L) [#]01000# (uzupełnienie wiodącego zera, nie można odwrócić -8 w U2 na 4 bitach)

W 12. kroku osiągany jest stan E, co kończy program. Na taśmie znajduje się napis 01000, co odpowiada liczbie 8 w kodzie U2.

Inne ujęcie[edytuj | edytuj kod]

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 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 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, 101, a 1102 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 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+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 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 00, 1 i 110, 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 np. , ż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ż[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]