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 = {s

i

} - zbiór symboli, które b d przetwarzane przez maszyn

Turinga, nazwany alfabetem S

Stan maszyny - okre la jednoznacznie stan głowicy q

j

i odczytany przez ni

symbol alfabetu s

i

:

S

ij

= (s

i

,q

j

)

Ruch maszyny - opisuje akcj , jak ma wykona MT. Ruch maszyny jest reakcj

maszyny na stan maszyny S

ij

. Opisywany jest jako trójka:

R

ij

= (s

k

, q

l

, p

m

),

Gdzie:
s

k

– symbol zapisany przez głowic ,

q

l

– nowy stan wewn trzny głowicy,

p

m

–przesuni cie głowicy {P, N, L},

q

1

q

2

...

q

j

...

q

m

s

1

s

2

...

...

s

n

•

Ka dy ruch R

ij

jest zwi zany jednoznacznie ze stanem maszyny S

ij

.

Zatem: R

ij

= T (S

ij

), gdzie T – to tablica charakterystyczna maszyny Turinga

R

ij

= (s

k

, q

l

, p

m

)

Je li b d c w stanie q

j

głowica

odczytała symbol s

i

, to nale y

zapisa na ta mie symbol s

k

,

zmieni stan wewn trzny głowicy

na q

l

i dokona przesuni cia

głowicy p

m

,

Twierdzenie:

Ka dy algorytm mo e by realizowany
przez odpowiednio zaprogramowan (za

pomoc tablicy charakterystycznej)
Maszyn Turinga

Zadanie 1

Maszyna Turinga odejmuj ca 1 od liczby binarnej

Liczba parzysta

Liczba nieparzysta

10

100

1010

1

-

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.

q

0

q

1

q

2

q

3

φ

φq

0

L

φq

3

L

φq

3

L

φq

3

N

0

1q

1

L

1q

1

L

0q

2

L

0q

3

N

1

0q

2

L

0q

2

L

1q

2

L

1q

3

N

Stany wewn trzne głowicy
q

0

– stan pocz tkowy, szukanie liczby,

q

1

– stan inwersji,

q

2

– stan przepisywania,

Q

3

– stan ko cowy.

Pocz tkowy napis i poło enie głowicy

↓

φ

1

0

0

0

1

0

0

φ

φ

Stan głowicy

Napis na ta mie

q

0

φ

φφφφφ

q

0

φ

φφφφφ

q

0

φ

0φφ

q

1

φ

01φφ

q

1

φ

111φφ

q

2

φ

0011φφ

q

2

φ 00011φφ

q

2

φ 000011φφ

q

2

φ 000011φφ

q

2

φφφφ

φφ

q

3

φφφφ

φφ

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: <ci g cyfr>.<ci g cyfr>

↓

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

φ

φ

φ

φ

φ

q

0

q

1

q

2

q

3

q

4

φ

φq

0

P

φq

2

L

φq

4

N

φq

3

N

φq

4

N

0

φq

0

P

0q

1

P

φq

2

L

0q

3

N

1

1q

1

P

1q

1

P

1q

3

N

1q

3

N

2

2q

1

P

2q

1

P

2q

3

N

2q

3

N

.

.q

1

P

.q

1

P

.q

3

N

.q

3

N

Stany wewn trzne głowicy
q

0

– przesuwanie w prawo i pomijanie

zer pocz tkowych,

q

1

– przej cie na prawy koniec liczby,

q

2

– eliminowanie zer ko cowych,

q

3

– poprawny stan ko cowy,

q

4

– bł dny stan ko cowy.

Ogólny opis zło enia dwóch maszyn Turinga

Dane maszyny: T1, T2
Alfabet wspólny:

S = {s

0

, s

1

, .. , s

l

}

Zbiory stanów wewn trznych:

Q

1

= {q

01

, q

11

, q

21

, .. , q

n1

}

Q

2

= {q

02

, q

12

, q

22

, .. , q

m2

}

Zło enie (iloczyn) maszyn Turinga jest maszyn Turinga o tym samym

alfabecie oraz zbiorze stanów wewn trznych Q:

Q = {q

0

, q

1

, q

2

, .. , q

m+n

},

w którym kolejne stany odpowiadaj stanom maszyn T1, T2 w nast puj cy

sposób:

q

0

≡ q

01

q

1

≡ q

11

q

2

≡ q

21

...

q

n-1

≡ q

n-1,1

q

n

≡ q

n1

≡ q

02

q

n+1

≡ q

12

q

n+2

≡ q

22

...

q

n+m

≡ q

m,2

Zakłada si , e q

n1

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

Stany wewn trzne głowicy
q

0

– stan pocz tkowy,

q

1

– bit znaku ‘0’,

q

2

– bit znaku ‘1’,

q

3

– liczba ujemna,

q

4

– liczba dodatnia.

Tablica charakterystyczna

q

0

q

1

q

2

q

3

q

4

φφφφ

φq

0

P

φq

4

N

φq

3

N

q

3

N

q

4

N

0

0q

1

P

0q

1

P

0q

2

P

q

3

N

q

4

N

1

1q

2

P

1q

1

P

1q

2

P

q

3

N

q

4

N

q

s

Maszyna T2 - dodaj ca 1

(głowica z prawej)

1010

0

00

011

10101

00100

+ 1

+ 1

Stany wewn trzne głowicy

q

0

– stan pocz tkowy, głowica z prawej,

q

1

– inwersja,

q

2

– przepisywanie,

q

3

– stan ko cowy.

S

Q

q

0

q

1

q

2

q

3

φφφφ

φq

0

L

φq

3

N

φq

3

N

q

3

N

0

1q

2

L

1q

2

L

0q

2

L

q

3

N

1

0q

1

L

0q

1

L

1q

2

L

q

3

N

Tablica charakterystyczna

T3 – maszyna odejmuj ca 1 (głowica z prawej)

10

100

0001

1

10011

00010

– 1

– 1

Stany wewn trzne głowicy
q

0

– stan pocz tkowy, głowica z prawej,

q

1

– inwersja,

q

2

– przepisywanie,

q

3

– stan ko cowy.

q

0

q

1

q

2

q

3

φφφφ

φq

0

L

φq

3

N

φq

3

N

q

3

N

0

1q

1

L

1q

1

L

0q

2

L

q

3

N

1

0q

2

L

0q

2

L

1q

2

L

q

3

N

s

q

Tablica charakterystyczna

T1

q

0

q

1

q

2

q

3

q

4

T2

q

0

q

1

q

2

q

3

T3

q

0

q

1

q

2

q

3

T

q

0

q

1

q

2

q

3

q

4

q

5

q

6

q

7

q

8

q

9

φφφφ

φq

0

P

φq

6

N

φq

3

N

φq

3

L

φq

9

N

φq

9

N

φq

6

L

φq

9

N

φq

9

N

φq

9

N

0

0q

1

P

0q

1

P

0q

2

P

1q

5

L

1q

5

L

0q

5

L

1q

7

L

1q

7

L

0q

8

L

φq

9

N

1

1q

2

P

1q

1

P

1q

2

P

0q

4

L

0q

4

L

1q

5

L

0q

8

L

0q

8

L

1q

8

L

φq

9

N