5. Maszyna Turinga
A = ∈ AT
Q — skończony zbiór stanów
q0 – 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×Γ ! 2Q×Γ×{L,R} — funkcja przejścia (L–w lewo, R–w prawo)
dwustronnie
nieskończona
taśma
b
b
A
B
C
A
B
q1∈Q
B
B
A
b
urządzenie sterujące pracujące
według funkcji δ
Konfiguracja: (q,α↑β)
q – stan
αβ – niepusta część taśmy
↑–wskazanie położenia głowicy
Funkcja przejścia: (dla automatu deterministycznego)
δ(q1,C)=(q2,A,R)
(q1,AB↑CABBBA) " (q2,ABA↑ABBBA)
Konfiguracja początkowa: (q0, ↑α), α ∈T*
Przykład:
Q = {q0, q1, q2, q3, q4, q5}
F = {q5}
Γ = {1,2,b}
T = {1}
b
1
δ:
q0
q1,2,L
q0,1,R
q1
q2,b,R
q1,1,L
q2
q3,b,R
q3
q4,1,R
q3,1,R
q4
q1,1,L
q5,1,R
q5
q5,1,R
b
2
q1,2,L
q4,b,R
q3,2,R
Start: (q0, ↑11), Stop: (q0, 1111↑)
q0
q0
q0
q1
q1
q1
q2
q3
q3
q3
q4
q1
q1
q1
q1
q2
q3
q3
q3
q3
q4
q1
q1
q1
q1
q1
q2
q4
q5
.
q5
↑
↑
b
b
↑
↑
↑
1
1
1
1
1
1
1
b
b
b
↑
↑
↑
↑
↑
↑
.
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
b
b
b
.
↑
↑
↑
↑
↑
↑
.
b
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
b
.
↑
↑
↑
↑
↑
.
b
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
.
1
↑
↑
↑
↑
.
b
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
.
1
↑
↑
.
b
1
1
1
1
1
1
1
1
1
.
1
Obliczalność funkcji w sensie Turinga—definicja
N = {0,1,2,…} (zbiór liczb naturalnych z zerem)
Funkcję f
f: (x1,…,xk) ∈ N k ! N ∋ f(x1,…,xk), k=1,2,…
nazywamy obliczalną w sensie Turinga jeżeli
(∃A∈AT) ((q0, ↑1x1b1x2b…b1x2) "* (q,1f(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) Ii,n(x1,…,xi,…xn) = xi — projekcja (identyczność)
↑
.
b
1
1
1
1
1
1
1
1
.
1
.
↑
b
2. Jeśli f1,…,fn są funkcjami rekurencyjnymi m argumentów, g jest funkcją rekurencyjną
n argumentów, to funkcją rekurencyjną jest
h(x1,…,xm) = g(f1(x1,…,xm),…, fn(x1,…,xm)) — podstawienie
3. Jeśli f jest funkcją rekurencyjną n argumentów, g jest funkcją rekurencyjną n+2
argumentów, to h(y,x1,…,xn) (funkcja n+1 argumentów) jest funkcją rekurencyjną
określoną jako:
h(0,x1,…,xn) = f(x1,…,xn)
h(y+1,x1,…,xn) = g(y, h(y,x1,…,xn),x1,…,xn) — rekursja prosta
4. Jeśli f jest funkcją rekurencyjną n+1 zmiennych to funkcja h(x1,…,xn) będąca funkcją
n zmiennych jest funkcją rekurencyjną określoną jako:
h(x1,…,xn)= µy(f(y,x1,…,xn))
gdzie µy(f(y,x1,…,xn)) oznacza najmniejszą liczbę y spełniającą równanie:
f(y,x1,…,xn)=0 dla danych x1,…,xn — minimum efektywne
5. Nic innego nie jest funkcją rekurencyjną.
Funkcje budowane przy pomocy operacji 1,2,3 (i 5) nazywają się funkcjami pierwotnie
rekurencyjnymi
FPR — klasa funkcji pierwotnie rekurencyjnych
FR — klasa funkcji rekurencyjnych
FPR ⊂ FR
FPR ≠ FR
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
... zobacz całą notatkę
Komentarze użytkowników (0)