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

*

…….