5. Maszyna Turinga

A = <Q, q

0

, F,

Γ

, T,

δ

>

∈

A

T

Q — skończony zbiór stanów
q

0

– stan początkowy

F – zbiór stanów końcowych

Γ

– skończony zbiór symboli taśmy

T

⊆

Γ

— alfabet wejściowy

b

∈

T–

Γ

— symbol pusty (blank)

δ

: Q

×Γ

! 2

Q

×Γ×

{L,R}

— funkcja przejścia (L–w lewo, R–w prawo)

Konfiguracja: (q,

α↑β

)

q – stan

αβ

– niepusta część taśmy

↑

–wskazanie położenia głowicy

Funkcja przejścia: (dla automatu deterministycznego)

δ

(q

1

,C)=(q

2

,A,R)

(q

1

,AB

↑

CABBBA)

" (q

2

,ABA

↑

ABBBA)

Konfiguracja początkowa: (q

0

,

↑α

),

α

∈

T

*

Przykład:
Q = {q

0

, q

1

, q

2

, q

3

, q

4

, q

5

}

F = {q

5

}

Γ

= {1,2,b}

T = {1}

δ

:

b

1 2

q

0

q

1

,2,L q

0

,1,R

q

1

q

2

,b,R q

1

,1,L q

1

,2,L

q

2

q

3

,b,R q

4

,b,R

q

3

q

4

,1,R q

3

,1,R q

3

,2,R

q

4

q

1

,1,L q

5

,1,R

q

5

q

5

,1,R

Start: (q

0

,

↑

11), Stop: (q

0

, 1111

↑

)

b

b

A

B

B

B

A

C

B

A

b

b

dwustronnie
nieskończona
taśma

q

1

∈

Q

urządzenie sterujące pracujące
według funkcji

δ

q

0

↑

1

1

q

0

1

↑

1

q

0

1

1

↑

b

q

1

1

↑

1

2

q

1

↑

1

1

2

q

1

↑

b 1

1

2

q

2

b

↑

1

1

2

q

3

b

↑

1

2

q

3

1

↑

2

q

3

1 2

↑

b

q

4

1 2 1

↑

b

q

1

1 2

↑

1

1

q

1

1

↑

2 1

1

q

1

↑

1 2 1

1

q

1

↑

b 1 2 1

1

q

2

b

↑

1 2 1

1

q

3

b

↑

2 1

1

q

3

2

↑

1

1

q

3

2

1

↑

1

q

3

2

1

1

↑

b

q

4

2

1

1

1

↑

b

q

1

2

1

1

↑

1

1

q

1

2

1

↑

1

1

1

q

1

2

↑

1

1

1

1

q

1

↑

2 1

1

1

1

q

1

↑

b 2 1

1

1

1

q

2

b

↑

2 1

1

1

1

q

4

b

↑

1

1

1

1

q

5

1

↑

1

1

1

. . . . . . . . . . . . . .
q

5

1

1

1

1

↑

b

Obliczalność funkcji w sensie Turinga—definicja
N

= {0,1,2,…} (zbiór liczb naturalnych z zerem)

Funkcję f
f: (x

1

,…,x

k

)

∈

N

k

! N

∋

f(x

1

,…,x

k

), k=1,2,…

nazywamy obliczalną w sensie Turinga jeżeli
(

∃

A

∈

A

T

) ((q

0

,

↑

1

x1

b1

x2

b…b1

x2

)

"* (q,1

f(x1,…,xk)

↑

))

gdzie: q

∈

F, T={1},

Γ

={1, b,…}

Funkcje rekurencyjne — definicja:

1. Funkcją rekurencyjną jest:

a) Z(x) = 0 — zero
b) S(x) = x+1 — następnik
c) I

i,n

(x

1

,…,x

i

,…x

n

) = x

i

— projekcja (identyczność)

2. Jeśli f

1

,…,f

n

są funkcjami rekurencyjnymi m argumentów, g jest funkcją rekurencyjną

n argumentów, to funkcją rekurencyjną jest
h(x

1

,…,x

m

) = g(f

1

(x

1

,…,x

m

),

…,

f

n

(x

1

,…,x

m

)) — podstawienie

3.

Jeśli f jest funkcją rekurencyjną n argumentów, g jest funkcją rekurencyjną n+2
argumentów, to h(y,x

1

,…,x

n

) (funkcja n+1 argumentów) jest funkcją rekurencyjną

określoną jako:
h(0,x

1

,…,x

n

) = f(x

1

,…,x

n

)

h(y+1,x

1

,…,x

n

) = g(y, h(y,x

1

,…,x

n

),x

1

,…,x

n

) — rekursja prosta

4.

Jeśli f jest funkcją rekurencyjną n+1 zmiennych to funkcja h(x

1

,…,x

n

) będąca funkcją

n zmiennych jest funkcją rekurencyjną określoną jako:
h(x

1

,…,x

n

)=

µ

y

(f(y,x

1

,…,x

n

))

gdzie

µ

y

(f(y,x

1

,…,x

n

)) oznacza najmniejszą liczbę y spełniającą równanie:

f(y,x

1

,…,x

n

)=0 dla danych x

1

,…,x

n

— minimum efektywne

5.

Nic innego nie jest funkcją rekurencyjną.

Funkcje budowane przy pomocy operacji 1,2,3 (i 5) nazywają się funkcjami pierwotnie
rekurencyjnymi

F

PR

— klasa funkcji pierwotnie rekurencyjnych

F

R

— klasa funkcji rekurencyjnych

F

PR

⊂

F

R

F

PR

≠

F

R

Przy rozpatrywaniu obliczalności funkcji pierwotnie rekurencyjnych możemy oszacować
liczbę taktów potrzebnych maszynie Turinga do obliczenia takiej funkcji, czyli określić
złożoność czasową algorytmu realizowanego przez maszynę Turinga.
Dla funkcji rekurencyjnych tworzonych przy pomocy operacji 4 (minimum efektywne) nie da
się w przypadku ogólnym przeprowadzić takiego oszacowania. Jednakże dowodzi się, że
maszyna Turinga w skończonej liczbie kroków jest w stanie funkcje te obliczyć (pod
warunkiem, że są one określone dla wszystkich argumentów swojej dziedziny).

Przykłady:

a) D(y,x)=y+x jest funkcją rekurencyjną, gdyż można ją otrzymać w drodze

podstawienia i rekursji prostej funkcji podstawowych:
D(0,x) = I

1,1

(x) = x

D(y+1,x) = S(I

2,3

(y,D(y,x),x)) = S(D(y,x)) = y+x+1

b) H(x)=2x jest funkcją rekurencyjną, gdyż można ją otrzymać w drodze podstawienia

funkcji rekurencyjnych do funkcji D(y,x), o której wiemy z punktu a), że jest
rekurencyjna:
H(x) = D(I

1,1

(x), I

1,1

(x)) = D(x,x) = x+x = 2x

c) M(y,x)=yx jest rekurencyjna, gdyż:

M(0,x)=Z(x)=0
M(y+1,x) = I

2,2

(y,D(M(y,x),x)) = D(M(y,x),x) = yx+x = (y+1)x

d) E(y,x)=x

y

jest rekurencyjna, gdyż wykorzystując c) otrzymujemy:

E(0,x) = S(Z(x)) = S(0) = 1 = x

0

E(y+1,x) = I

2,2

(y,M(x,E(y,x)) = M(x,E(y,x)) = xx

y

= x

y+1

Zbiór B

⊆

N nazywamy przeliczalnie rekurencyjnym, gdy jego funkcja charakterystyczna

f(x):

0, dla x

∉

B

f(x)=

{

1, dla x

∈

B

jest funkcją rekurencyjną.
Maszyna Turinga jest wtedy w stanie w skończonej liczbie kroków stwierdzić, czy x

∈

B, czy

też x

∉

B, czyli potrafi obliczyć funkcję charakterystyczną dla tego x.

Zbiór B

⊆

N nazywamy przeliczalnie rekurencyjnym, jeżeli B=

∅

(B jest pusty) lub istnieje

taka funkcja rekurencyjna f(x,y), taka że:
(

∀

x

∈

B) (

∃

y

∈

N) (f(x,y)=0)

Klasa zbiorów rekurencyjnych

Z

R

jest podklasą właściwą klasy zbiorów rekurencyjnie

przeliczalnych

Z

RP

Z

R

⊂

Z

RP

ale

Z

R

≠

Z

RP

Jeżeli B

⊂

N jest zbiorem rekurencyjnie przeliczalnym, to maszyna Turinga jest w stanie w

skończonej liczbie kroków określić, czy x

∈

B tylko wtedy, gdy x rzeczywiście należy do B.

Gdy natomiast x

∉

B to

¬

(

∃

y

∈

N) (f(x,y)=0), ale aby to sprawdzić trzeba przebadać wszystkie

liczby naturalne, a tych jest nieskończenie wiele, więc badania nie da się przeprowadzić w
skończonej liczbie kroków.
Pojęcia zbiorów rekurencyjnych i rekurencyjnie przeliczalnych odnosiły się do zbiorów liczb
naturalnych. Można je wszakże przenieść na grunt języków.

Numeracja Gödla: Można ponumerować słowa języka:

1. numerujemy elementy alfabetu

T={a

1

,a

2

,…,a

n

}

2. niech p

1

p

2

p

3

p

4

… będzie ciągiem rosnącym liczb pierwszych, np. 2,3,5,7,11,13,…

3. określamy funkcję num(x) dla x

∈

T

*

∏

=

=

=

k

j

i

j

i

i

i

j

k

p

a

a

a

num

num

1

)

(

0

)

(

2

1

#

ε

Można pokazać, że odwzorowanie

num: T

*

! N

jest wzajemnie jednoznaczne (funkcja num(x) jest różnowartościowa).
Przykład:

1. T={a,b}, numerujemy litery => T={a

1

,a

2

}

2. określamy rosnący ciąg liczb pierwszych: p

1,

p

2

, p

3

,… jako 2, 3, 5, 7,…

3. analizujemy słowo x = abaa

∈

T

*

, x = a

1

a

2

a

1

a

1

,

num(x) = p

1

1

p

2

2

p

3

1

p

4

1

= 2

1

*3

2

*5

1

*7

1

= 2*9*5*7 = 630

Niech L

⊆

T

*

będzie językiem.

Zbiór num(L) określony jako

num(L) = {n

∈

N | n=num(x)

∧

x

∈

L}

jest zbiorem numerów słów tego języka.
Język L nazywamy rekurencyjnym, gdy jego zbiór num(L) jest zbiorem rekurencyjnym.
Język L nazywamy rekurencyjnie przeliczalnym, gdy jego zbiór num(L) jest zbiorem
rekurencyjnie przeliczalnym.

Akceptowalność języka L przez maszynę Turinga
A = <Q, q

0

, F,

Γ

, T,

δ

>

∈

A

T

Q —zbiór stanów (q

0

–stan początkowy, F–zbiór stanów końcowych)

Γ

— alfabet taśmy

T

⊂

Γ

—alfabet wejściowy

b

∈

T–

Γ

—symbol pusty (blank)

δ

— funkcja przejścia

Maszyna Turinga A akceptuje język

L(A) = {x

∈

T

*

| (

∃

q

∈

F) (

∃

y

∈Γ

*

) ((q

0

,

↑

x)

"

*

A

(q,y

↑

))}

gdzie: (q,y

↑

) – konfiguracja stopująca

Stwierdzenia dotyczące zbiorów rekurencyjnych i rekurencyjnie przeliczalnych przenoszą się
na akceptowalność języków rekurencyjnych i rekurencyjnie przeliczalnych przez maszynę
Turinga.
L

R

— klasa języków rekurencyjnych

L

RP

— klasa języków rekurencyjnie przeliczalnych

L

TUR

— klasa języków akceptowanych przez maszynę Turinga

Jeżeli L

∈

L

R

to maszyna Turinga potrafi stwierdzić czy x

∈

L, czy też x

∉

L w skończonej liczbie

kroków.
Jeżeli L

∈

L

RP

to maszyna Turinga potrafi stwierdzić, że x

∈

L tylko wtedy, gdy x rzeczywiście

należy do L, w przeciwnym razie w przypadku ogólnym nie zatrzyma się po wykonaniu
skończonej liczby kroków.
L

R

⊂

L

TUR

ale

L

R

≠

L

TUR

L

RP

=

L

TUR

=

L

KOMB

gdzie:

L

KOMB

—klasa języków kombinatorycznych (klasa 0 (zero) w klasyfikacji

Chomsky’ego)


Tw: Klasa zbiorów rekurencyjnych

Z

R

jest zamknięta ze względu na operacje sumy,

przecięcia (iloczynu mnogościowego) oraz uzupełnienia do

N.

Jeżeli A

∈

Z

R

to (

N –A)

∈

Z

R

Tw. Klasa zbiorów rekurencyjnie przeliczalnych

Z

RP

jest zamknięta ze względu na operacje

sumy, przecięcia (iloczynu mnogościowego), nie jest natomiast zamknięta ze względu na
uzupełnienie do

N.

Jeżeli B

∈

Z

RP

to o zbiorze (

N –B) nic nie można powiedzieć, w szczególności nie można

powiedzieć, że (

N –B) jest rekurencyjnie przeliczalny.

Gdyby (

N –B)

∈

Z

RP

to korzystając z faktu, że jeżeli x

∉

B to x

∈

(

N –B) maszyna Turinga

potrafiłaby w skończonej liczbie kroków stwierdzić, że x

∈

(

N –B), a zatem mogłaby

efektywnie określać, że x

∉

B. To niestety nie ma miejsca.