Maszyna Turinga
Maszyna Turinga (MT) jest to abstrakcyjne, pojęciowe urządzenie, a komputer można uznać za jego
implementację. Każdy problem algorytmizowany da się rozwiązać przy pomocy MT. Została ona
opracowana przez Alana Turinga w 1936 roku.
Maszyna składa się z:
nieskończonej taśmy podzielonej na pola,
głowicy odczytująco/zapisującej,
zbioru stanów
alfabetu
algorytmu
Na taśmie jest zapisana informacja przy pomocy skończonego alfabetu. W każdej chwili jedno z pól
jest polem bieżącym, a maszyna przyjmuje jeden określony stan. W zależności od kombinacji
aktualnego stanu maszyny i wartości bieżącego pola taśmy, maszyna zmienia stan, zmienia wartość
bieżącego pola na taśmie, a głowica przemieszcza się o jedno pole w prawą lub lewą stronę, lub
pozostaje bez zmian. Maszyna sterowana jest listą takich rozkazów (zawarte w tabeli). Wśród stanów
wyróżniony jest stan początkowy (start) i końcowy (koniec), a alfabet zawiera symbol początku i
końca danych (*).
Przykład – Maszyna Turinga 1:
Rozważmy następującą MT:
Maszyna ta dodaje wartość „1” do liczby binarnej zapisanej na taśmie.
Zbiór stanów: {S, D, P, N, K}
S – start
D – dodawanie
P – przeniesienie
N – nadmiar
K – koniec - sukces
KN – koniec - nadmiar
Alfabet: {0, 1, *}
Rozkazy:
←– przesuń głowicę w lewo
→ – przesuń głowicę w prawo
_ – nic nie rób
Stan początkowy maszyny to S, startowe pole na taśmie, to * kończąca liczbę dwójkową.
…….
*
1
0
1
0
1
1
*
…….
start
Tabela z listą rozkazów naszej maszyny:
stan
symbol
S
D
P
N
NT R
NS NT R
NS NT R
NS NT R NS
*
*
← D
1
← N
*
− KN
0
1
− K
1
−
K
*
− KN
1
0
← P
0
← P
*
− KN
W tabeli jest zapisane działanie maszyny dla każdego stanu i dla każdego symbolu bieżącego na
taśmie. Jest ono wyrażone trzema wartościami:
NT – nowa wartość na taśmie /zastępuje bieżącą
R – rozkaz / związany z ruchem głowicy
NS – nowy stan
Przeanalizujmy działanie maszyny dla liczby binarnej 101 zapisanej na taśmie:
Taśma
Stan Nowy stan
Bieżące pole
Nowe pole
S
D
*
*
D
P
1
0
P
K
0
1
K
-
1
-
STOP maszyny: Wynik na taśmie: 110; stan K - koniec
--------------------------------------------------------------------------------------------------------------------------------------
…….
*
1
0
1
*
…….
…….
*
1
0
1
*
…….
…….
*
1
0
0
*
…….
…….
*
1
1
0
*
…….
A co się stanie, jeśli na taśmie zapiszemy liczbę 111:
Taśma
Stan Nowy stan
Bieżące pole
Nowe pole
S
D
*
*
D
P
1
0
P
P
1
0
P P
1
0
P N
*
1
N KN
1
-
Wynik: 1000; stan: KN.
Stan ”KN” oznacza, że wystąpił nadmiar. W przypadku tej maszyny wynik jest poprawny, ale na
taśmie zastąpiony został symbol występujący przed ”*” rozpoczynającą ciąg bitowy reprezentujący
liczbę, symbolem ”*”.
Głowica przesuwa się od końca liczby w lewą stronę, aż do napotkania wartości ”0”. Napotkane po
drodze ”1” zamienia na ”0”,a zatrzymuje się po zamianie wartości ”0” na ”1”. Jeśli wcześniej napotka
”*” oznaczającą początek liczby, dodaje z przodu ”1”, a przed nią ”*” i przechodzi w stan „nadmiar”.
…….
*
1
1
1
*
…….
…….
*
1
1
1
*
…….
…….
*
1
1
0
*
…….
…….
*
1
0
0
*
…….
…….
*
0
0
0
*
…….
… *
1
0
0
0
*
…….
Przykład – Maszyna Turinga 2:
Rozważmy następującą MT:
Maszyna ta dodaje wartość „1” do liczby binarnej zapisanej na taśmie, ale w przeciwieństwie do
poprzedniego przykładu maszyna startuje od ”*” występującej po lewej stronie liczby.
Zbiór stanów: {S, D, Po, N, K, KN}
S – start
D – dodawanie
Po – powrót
N – nadmiar
K – koniec sukces
KN – koniec - nadmiar
Alfabet: {0, 1, *}
Rozkazy:
←– przesuń głowicę w lewo
→ – przesuń głowicę w prawo
_ – nic nie rób
Stan początkowy maszyny to S, startowe pole na taśmie, to * rozpoczynająca liczbę dwójkową.
Tabela z listą rozkazów naszej maszyny:
stan
symbol
S
D
Po
NT R
NS NT R
NS NT R
NS
*
*
→ D
*
← Po 1
−
KN
0
0
→ D
1
−
K
1
1
→ D
0
← Po
W tabeli jest zapisane działanie maszyny dla każdego stanu i dla każdego symbolu bieżącego na
taśmie. Jest ono wyrażone trzema wartościami:
NT – nowa wartość na taśmie /zastępuje bieżącą
R – rozkaz / związany z ruchem głowicy
NS – nowy stan
Przeanalizujmy działanie maszyny dla liczby binarnej 101 zapisanej na taśmie:
…….
*
1
0
1
0
1
1
*
…….
start
Taśma
Stan Nowy stan
Bieżące pole
Nowe pole
S
D
*
*
D
D
1
1
D
D
0
0
D
D
1
1
D
Po
*
*
Po
Po
1
0
Po K
0
1
K
-
1
-
STOP maszyny: Wynik na taśmie: 110; stan K - koniec
Najpierw głowica przesuwa się w prawo, do końca liczby, a potem cofa się zamieniając kolejne
napotkane ”1” na „0”, aż do napotkania ”0”, które zamienia na ”1”.
--------------------------------------------------------------------------------------------------------------------------------------
…….
*
1
0
1
*
…….
…….
*
1
0
1
*
…….
…….
*
1
0
1
*
…….
…….
*
1
0
1
*
…….
…….
*
1
0
1
*
…….
…….
*
1
0
1
*
…….
…….
*
1
0
0
*
…….
…….
*
1
1
0
*
…….
A co się stanie, jeśli na taśmie zapiszemy liczbę 111:
Taśma
Stan Nowy stan
Bieżące pole
Nowe pole
S
D
*
*
D
D
1
1
D
D
1
1
D D
1
1
D P
*
*
P P
1
0
P P
1
0
P P
1
0
P KN
*
1
KN -
1
-
Wynik: 1000; stan KN.
Stan ”KN” oznacza, że wystąpił nadmiar. W przypadku tej maszyny wynik jest poprawny, ale na
taśmie zastąpiony został symbol ”*” rozpoczynający liczbę, symbolem ”1”.
…….
*
1
1
1
*
…….
…….
*
1
1
1
*
…….
…….
*
1
1
1
*
…….
…….
*
1
1
1
*
…….
…….
*
1
1
1
*
…….
…….
*
1
1
1
*
…….
…….
*
1
1
0
*
…….
…….
*
1
0
0
*
…….
…….
*
0
0
0
*
…….
…….
1
0
0
0
*
…….