Maszyna Turinga
W roku 1937 angielski matematyk, Alan Turing,pracując nad koncepcją
obliczalności funkcji matematycznych opisuje bardzo prostą maszynę
logiczną, która dziś nosi nazwę Maszyny Turinga.
.
Pomimo swej prostoty Maszyna Turinga
posiada obecnie olbrzymie
znaczenie teoretyczne, ponieważ
wszystkie współczesne komputery dają
się do niej sprowadzić, zatem dany
problem jest rozwiązalny na komputerze,
jeśli da się zdefiniować rozwiązującą
go maszynę Turinga
Taśma
Nieskończona taśma jest odpowiednikiem
współczesnej pamięci komputera. Taśma dzieli się
na komórki, w których umieszczone zostały symbole,
czyli po prostu znaki przetwarzane przez maszynę
Turinga. Symbole te stanowią odpowiednik danych
wejściowych. Maszyna Turinga odczytuje te dane z
kolejnych komórek i przetwarza na inne symbole,
czyli dane wyjściowe. Wyniki obliczeń również są
zapisywane w komórkach taśmy.
Głowica zapisująco-odczytująca
Aby przetwarzać dane, maszyna Turinga musi potrafić je
odczytywać z taśmy i zapisywać na taśmę. Do tego celu
przeznaczona jest właśnie głowica zapisująco-odczytująca, która
odpowiada funkcjonalnie urządzeniom wejścia/wyjścia
współczesnych komputerów lub układom odczytu i zapisu pamięci.
Głowica zawsze znajduje się nad jedną z komórek taśmy. Może
ona odczytywać zawartość tej komórki oraz zapisywać do niej inny
symbol - na tej zasadzie odbywa się przetwarzanie danych - z
jednych symboli otrzymujemy inne. Oprócz odczytywania i
zapisywania symboli w komórkach głowica wykonuje ruchy w
prawo i w lewo do sąsiednich komórek na taśmie. W ten sposób
może się ona przemieścić do dowolnie wybranej komórki taśmy.
Układ sterowania
Przetwarzaniem informacji zarządza układ sterowania
głowicą. Jego współczesnym odpowiednikiem jest procesor
komputera. Układ ten odczytuje za pomocą głowicy
symbole z komórek taśmy oraz przesyła do głowicy
symbole do zapisu w komórkach. Dodatkowo nakazuje on
głowicy przemieścić się do sąsiedniej komórki w lewo lub w
prawo.
Zbiór symboli S = {si} - zbiór symboli, które będą przetwarzane przez maszynę
Turinga, nazwany alfabetem S
Stan maszyny - określa jednoznacznie stan głowicy qj i odczytany przez nią
symbol alfabetu si: Sij = (si,qj)
Ruch maszyny - opisuje akcję, jaką ma wykonać MT. Ruch maszyny jest reakcją
maszyny na stan maszyny Sij. Opisywany jest jako trójka: Rij = (sk, ql, pm),
Gdzie:
sk  symbol zapisany przez głowicę,
ql  nowy stan wewnętrzny głowicy,
pm  przesunięcie głowicy {P, N, L},
" Każdy ruch Rij jest związany jednoznacznie ze stanem maszyny Sij.
Zatem: Rij = T (Sij), gdzie T  to tablica charakterystyczna maszyny Turinga
q1 q2 ... qj ... qm
Rij = (sk, ql, pm)
Jeśli będąc w stanie qj głowica
s1
odczytała symbol si, to należy
zapisać na taśmie symbol sk,
s2
zmienić stan wewnętrzny głowicy
... na ql i dokonać przesunięcia
głowicy pm,
...
Twierdzenie:
Każdy algorytm może być realizowany
sn
przez odpowiednio zaprogramowaną (za
pomocą tablicy charakterystycznej)
Maszynę Turinga
Zadanie 1
Maszyna Turinga odejmująca 1 od liczby binarnej
Liczba parzysta Liczba nieparzysta
10100 10101
-1 -1
10011 10100
Negacja wszystkich cyfr od prawej aż do pierwszej jedynki włącznie
Uwagi:
" Alfabet składa się ze znaków: {Ć, 0, 1}.
" Głowica na początku umieszczona jest z prawej strony taśmy.
Po wykonaniu przetwarzania głowica pozostaje po lewej stronie liczby
binarnej.
Stany wewnętrzne głowicy
q0  stan początkowy, szukanie liczby,
�!
Początkowy napis i położenie głowicy
q1  stan inwersji,
q2  stan przepisywania,
Ć 1 0 0 0 1 0 0 Ć Ć
Q3  stan końcowy.
Stan głowicy Napis na taśmie
Ć
q0 Ć ĆĆ
Ć
Ć
Ć
q0 Ć ĆĆ
Ć
Ć
q0 q1 q2 q3
q0 Ć 0ĆĆ
Ć Ćq0L Ćq3L Ćq3L Ćq3N q1 Ć 01ĆĆ
q1 Ć 111ĆĆ
0 1q1L 1q1L 0q2L 0q3N
q2 Ć 0011ĆĆ
q2 Ć 00011ĆĆ
1 0q2L 0q2L 1q2L 1q3N
q2 Ć 000011ĆĆ
q2 Ć 000011ĆĆ
Ć
q2 Ć ĆĆ
Ć
Ć
Ć
q3 Ć ĆĆ
Ć
Ć
Zaprojektować maszynę Turinga eliminującą nieznaczące zera liczb ułamkowych
w zapisz trójkowym (zarówno na początku jak i na końcu liczby).
Możliwe symbole: ", 0, 1, 2, .
"
"
"
Stan początkowy głowicy: z lewej strony liczby
Założenia:
Liczby są tylko w poprawnej postaci: .
Początkowy napis i położenie głowicy
�!
Ć Ć 0 0 1 . 0 1 0 0 0 Ć Ć
Końcowy napis i położenie głowicy
�!
Ć Ć Ć Ć 1 . 0 1 Ć Ć Ć Ć Ć
q0 q1 q2 q3 q4
Ćq0P Ćq2L Ćq4N Ćq3N Ćq4N
Ć
Ćq0P 0q1P Ćq2L 0q3N
0
Stany wewnętrzne głowicy
1q1P 1q1P 1q3N 1q3N
1 q0  przesuwanie w prawo i pomijanie
zer początkowych,
2q1P 2q1P 2q3N 2q3N
2
q1  przejście na prawy koniec liczby,
.q1P .q1P .q3N .q3N
.
q2  eliminowanie zer końcowych,
q3  poprawny stan końcowy,
q4  błędny stan końcowy.
Ogólny opis złożenia dwóch maszyn Turinga
Dane maszyny: T1, T2
Alfabet wspólny: S = {s0, s1, .. , sl}
Zbiory stanów wewnętrznych: Q1 = {q01, q11, q21, .. , qn1}
Q2 = {q02, q12, q22, .. , qm2}
Złożenie (iloczyn) maszyn Turinga jest maszyną Turinga o tym samym
alfabecie oraz zbiorze stanów wewnętrznych Q:
Q = {q0, q1, q2, .. , qm+n},
w którym kolejne stany odpowiadają stanom maszyn T1, T2 w następujący
sposób:
q0 a" q01
q1 a" q11
q2 a" q21
...
qn-1 a" qn-1,1
qn a" qn1 a" q02
qn+1 a" q12
qn+2 a" q22
...
qn+m a" qm,2
Zakłada się, że qn1 jest stanem poprawnego zakończenia pracy maszyny T1 i początkowym
stanem dla maszyny T2.
Zadanie
Zaprojektować maszynę Turinga dodającą 1 do liczby binarnej, jeśli jest ona ujemna albo
odejmująca 1, jeśli liczba jest dodatnia.
Uwagi:
� Symbole alfabetu: {Ć, 0, 1}.
� Pierwszy znak z lewej strony napisu jest bitem znaku.
� Głowica na początku znajduje się z lewej strony liczby binarnej,
Po wykonaniu przetwarzania głowica z prawej stronie liczby.
T1  maszyna testująca znak liczby i szukająca jej prawego końca (stan początkowy
głowica z lewej)
T2  maszyna dodająca 1 (stan początkowy głowica z prawej)
T3  maszyna odejmująca 1 (stan początkowy głowica z prawej)
Maszyna T1 maszyna testująca znak liczby i szukająca jej prawego końca
Tablica charakterystyczna
Stany wewnętrzne głowicy
q
q0 q1 q2 q3 q4
s
q0  stan początkowy,
q1  bit znaku  0 ,
Ćq0P Ćq4N Ćq3N q3N q4N
Ć
Ć
Ć
Ć
q2  bit znaku  1 ,
0q1P 0q1P 0q2P q3N q4N
q3  liczba ujemna, 0
q4  liczba dodatnia.
1q2P 1q1P 1q2P q3N q4N
1
Maszyna T2 - dodająca 1 (głowica z prawej)
10100 00011
+ 1
+ 1
Tablica charakterystyczna
10101 00100
q0 q1 q2 q3
S
Q
Stany wewnętrzne głowicy
Ćq0L Ćq3N Ćq3N q3N
Ć
Ć
Ć
Ć
q0  stan początkowy, głowica z prawej,
q1  inwersja,
1q2L 1q2L 0q2L q3N
0
q2  przepisywanie,
0q1L 0q1L 1q2L q3N
1
q3  stan końcowy.
T3  maszyna odejmująca 1 (głowica z prawej)
10100 00011
Tablica charakterystyczna
 1
 1
q
10011
00010
q0 q1 q2 q3
s
Stany wewnętrzne głowicy
Ćq0L Ćq3N Ćq3N q3N
Ć
Ć
Ć
Ć
q0  stan początkowy, głowica z prawej,
1q1L 1q1L 0q2L q3N
0
q1  inwersja,
q2  przepisywanie,
0q2L 0q2L 1q2L q3N
1
q3  stan końcowy.
T1 q0 q1 q2 q3 q4
T2 q0 q1 q2 q3
T3 q0 q1 q2 q3
T q0 q1 q2 q3 q4 q5 q6 q7 q8 q9
Ćq0P Ćq6N Ćq3N Ćq3L Ćq9N Ćq9N Ćq6L Ćq9N Ćq9N Ćq9N
Ć
Ć
Ć
Ć
0q1P 0q1P 0q2P 1q5L 1q5L 0q5L 1q7L 1q7L 0q8L
0 Ćq9N
1q2P 1q1P 1q2P 0q4L 0q4L 1q5L 0q8L 0q8L 1q8L
1 Ćq9N