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