MT – przykłady

Rozważmy następującą MT (Maszyna Turinga 3):
Maszyna ta dodaje wartośd „1” do liczby dziesiętnej zapisanej na taśmie. Maszyna startuje od ”*”
występującej po lewej stronie liczby.
Zbiór stanów: {S, D, Po, K, KN}

S – start

D – dodawanie

Po – powrót
K – koniec sukces
KN – koniec - nadmiar

Alfabet: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, *}

Rozkazy:

←– przesuo głowicę w lewo

→ – przesuo głowicę w prawo

_ – nic nie rób

Stan początkowy maszyny to S, startowe pole na taśmie, to * rozpoczynająca liczbę dziesiętną.

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

2

−

K

2

2

→ D

3

−

K

3

3

→ D

4

−

K

4

4

→ D

5

−

K

5

5

→ D

6

−

K

6

6

→ D

7

−

K

7

7

→ D

8

−

K

8

8

→ D

9

−

K

9

9

→ D

0

← Po

…….

*

2

3

6

9

1

0

*

…….

start

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śd na taśmie /zastępuje bieżącą



R – rozkaz / związany z ruchem głowicy



NS – nowy stan

Głowica tej maszyny przemieszcza się od początku liczby w prawą stronę do symbolu ”*”, kooczącego
liczbę, po czym przesuwa się o jedną pozycję w lewo. Występująca tam cyfra z wyjątkiem ”9”
zastępowana jest kolejną cyfrą (odpowiadającą liczbie o ”1” większej) i maszyna się zatrzymuje.
W przypadku napotkania cyfry ”9”, zastąpiona jest ona cyfrą ”0”, głowica przesuwa się w lewo
i czynnośd się powtarza do napotkania cyfry różnej od ”9” lub ”*”. Jeśli po dodaniu ”1” liczba nie
mieści się w wyznaczonym znakami ”*” maszyna przyjmuje stan ”KN” (nadmiar) i symbol ”*”
rozpoczynający liczbę zastąpiony jest ”1”.

Kolejny przykład (Maszyna Turinga 4) to maszyna, która odejmuje ”1” od liczby binarnej. Pozycją
startową jest ”*” rozpoczynająca liczbę. Maszyna działa tylko w zakresie liczb dodatnich.

Zbiór stanów: {S, O, Po, J, K, KN}

S – start

O – odejmowanie

Po – powrót

J – jest od czego odjąd
K – koniec sukces
KN – koniec - porażka

Alfabet: {0, 1, *}

Rozkazy:

←– przesuo głowicę w lewo

→ – przesuo głowicę w prawo

_ – nic nie rób

Stan początkowy maszyny to S, startowe pole na taśmie, to * rozpoczynająca liczbę binarną.

Tabela z listą rozkazów naszej maszyny:

stan

symbol

S

O

J

Po

NT

R

NS

NT

R

NS

NT

R

NS

NT

R

NS

*

*

→

O

*

−

KN

*

←

Po

0

0

→

O

0

→

J

1

←

Po

1

1

→

J

1

→

J

0

−

K

…….

*

1

0

0

1

1

0

*

…….

start

Głowica tej maszyny przemieszcza się od początku liczby w prawą stronę do symbolu ”*”, kooczącego
liczbę. Jeśli na taśmie napotka symbol ”1” przyjmuje stan ”J” oznaczający, że da się odjąd ”1” od
liczby. Gdy głowica dotrze do symbolu ”*” kooczącego liczbę, a stan maszyny nie został zmieniony na
”J”, to znaczy, że liczba na taśmie miała wartośd 0 i nie da się odjąd ”1” - maszyna zatrzymuje się,
przyjmując stan ”KN”. Jeśli natomiast stan maszyny to ”J”, następuje powrót, podczas, którego każdy
napotkany symbol ”0” jest zmieniany na ”1”, a symbol ”1” jest zamieniony na ”0” z równoczesnym
zatrzymaniem maszyny.

W podobny sposób można zaprojektowad maszynę odejmującą ”1” od liczby ósemkowej:

Maszyna Turinga 5:

Zbiór stanów: {S, O, Po, J, K, KN}

S – start

O – odejmowanie

Po – powrót

J – jest od czego odjąd
K – koniec sukces
KN – koniec - porażka

Alfabet: {0, 1, 2, 3, 4, 5, 6, 7, *}

Rozkazy:

←– przesuo głowicę w lewo

→ – przesuo głowicę w prawo

_ – nic nie rób

Stan początkowy maszyny to S, startowe pole na taśmie, to * rozpoczynająca liczbę ósemkową.
Tabela z listą rozkazów naszej maszyny:

stan

symbol

S

O

J

Po

NT

R

NS

NT

R

NS

NT

R

NS NT

R

NS

*

*

→

O

*

−

KN

*

←

Po

0

0

→

O

0

→

J

1

←

Po

1

1

→

J

1

→

J

0

−

K

2

2

→

J

2

→

J

1

−

K

3

3

→

J

3

→

J

2

−

K

4

4

→

J

4

→

J

3

−

K

5

5

→

J

5

→

J

4

−

K

6

6

→

J

6

→

J

5

−

K

7

7

→

J

7

→

J

6

−

K

start