Giáo trình Tin học lý thuyết - Chương 7: Máy Turing

ược sinh ở lần sinh thứ : 
(i + j - 1)(i + j - 2) / 2+ i. 
Máy Turing sinh ra các cặp sinh (i, j) viết trong hệ nhị phân là dễ dàng được 
thiết kế và ta gọi máy Turing này là bộ sinh cặp. 
ĐỊNH LÝ 7.7 : Một ngôn ngữ là tập đệ qui liệt kê nếu và chỉ nếu nó là G(M2) với 
TM M2 nào đó. 
Chứng minh 
Với bổ đề 1 ta chỉ cần chỉ ra rằng nếu L = L(M1) thì L được sinh ra bởi TM 
M2. M2 tương tự như bộ sinh cặp. Khi (i, j) được sinh ra, M2 sản xuất từ thứ i theo thứ 
tự chuẩn và làm tương tự M1 trên từ wi với j bước. Nếu M1 chấp nhận từ thứ i với j 
bước thì M2 sinh ra wi. Chắc chắn rằng M2 không sinh ra từ không thuộc L, đặt w là 
từ thứ i trong thứ tự chuẩn trên bộ chữ cái L và M1 chấp nhận w bằng j bước. Vì chỉ 
cần một lượng thời gian hữu hạn để M2 sinh ra bất kỳ từ nào và làm tương tự như M1 
nên M2 chắc chắn sinh ra (i, j). Lúc này w sẽ được sinh ra bởi M2. Vậy L = G(M2) 
HỆ QUẢ : Nếu L là tập đệ qui liệt kê thì có một bộ sinh sinh ra mỗi từ trong L 
đúng một lần. 
6.2. Tính chất đệ qui của tập sinh 
BỔ ĐỀ 7.2: Nếu L là tập đệ qui thì có một bộ sinh in ra các từ của L theo thứ tự 
chuẩn và không in ra các từ khác. 
Chứng minh 
Đặt L = L(M1) ∈ Σ* trong đó M1 dừng với mọi input. Ta xây dựng M2 sinh ra 
L như sau M2 sinh ra các từ thuộc Σ* mỗi lần một từ theo thứ tự chuẩn. Sau khi sinh 
Chương VII : Máy Turing 
 129
ra một từ w, M2 làm tương tự M1 trên w. Nếu M1 chấp nhận w thì M2 sinh ra w. Vì 
M1 chắc chắn dừng nên M2 cũng sẽ dừng sau hữu hạn bước và chắc chắn sẽ xét mỗi 
từ thuộc Σ*. Vậy M2 sinh ra L theo thứ tự chuẩn. 
Điều ngược lại của bổ đề trên cũng đúng, tức là, nếu L được sinh ra theo thứ tự 
chuẩn thì L là tập đệ qui. Nghĩa là có TM nhận diện M tồn tại, tuy nhiên không có 
một giải thuật cụ thể cho TM này. 
Giả sử M1 sinh ra L theo thứ tự chuẩn. Một ý nghĩ tự nhiên là ta xây dựng M2 
làm tương tự M1 trên input w cho tới khi M1 sinh ra w hoặc sinh ra từ sau w (theo thứ 
tự chuẩn). Trong trường hợp đầu, M2 chấp nhận w, trong trường hợp sau M2 dừng 
nhưng không chấp nhận w. Rõ ràng nếu L hữu hạn thì M1 có thể không dừng sau khi 
sinh ra từ cuối cùng trong L (vì theo định lý trên M1 không sinh từ nào không thuộc 
L). Trong trường hợp này M2 cũng không dừng. Điều này chỉ gặp khi L hữu hạn, 
nhưng do không có cách xác định TM có sinh ra tập hữu hạn hay không hoặc nếu biết 
TM sinh ra tập hữu hạn thì cũng không thể biết tập hợp đó là gì. Vậy ta biết là có TM 
chấp nhận L, nhưng không thể đưa ra một giải thuật cụ thể cho TM này. 
ĐỊNH LÝ 7.8 : L là tập đệ qui nếu và chỉ nếu L được sinh ra theo thứ tự chuẩn. 
Chứng minh 
Ta chỉ cần chứng minh phần nếu. 
Khi L hữu hạn thì sẽ có một ôtômát chấp nhận L và vì vậy L được chấp nhận 
bởi TM luôn luôn dừng trên tất cả các input. 
VII. SỰ TƯƠNG ĐƯƠNG GIỮA VĂN PHẠM kIỂU 0 
VÀ MÁY TURING 
Họ văn phạm rộng lớn nhất theo sự phân cấp của Noam Chomsky đòi hỏi các luật 
sinh có dạng α → β, với α, β là các chuỗi tùy ý chứa ký hiệu văn phạm sao cho α ≠ ε. 
Lớp văn phạm này được biết như là văn phạm kiểu 0, văn phạm ngữ cấu hay văn 
phạm không hạn chế. 
Thí dụ 7.10 : Cho một văn phạm không hạn chế sinh ra ngôn ngữ 
L = { ai | i là lũy thừa dương của 2 } với tập luật sinh như sau : 
G ({S, A, B, C, D, E}, {a, ε }, P, S) 
Với P = { 1. S → ACaB 
2. Ca → aaC 
3. CB → DB 
4. CB → E 
5. aD → Da 
6. AD → AC 
7. aE → Ea 
8. AE → ε } 
Chương VII : Máy Turing 
 130
Trong văn phạm trên, biến A và B giữ vai trò là ký hiệu đánh dấu cận trái và 
cận phải của một chuỗi thuộc ngôn ngữ. C di chuyển từ trái sang phải qua chuỗi các 
ký hiệu a nằm giữa hai biến A và B, và gấp đôi số ký hiệu a đó lên theo luật sinh (2). 
Khi C chạm đến cận phải B, nó sẽ thay thế thành D hay E theo luật sinh (3) hoặc (4). 
Nếu D được chọn thay thế thì D lại quay về trái theo luật sinh (5), cho đến khi gặp 
cận trái A thì thay thế lại thành C theo luật sinh (6) và cho phép lặp lại chu trình. Còn 
nếu E được chọn để thay thế, thì theo luật sinh (4), B sẽ biến mất, sau đó E quay về 
trái theo luật sinh (7) cho đến khi gặp cận trái A thì xóa A và mất đi theo luật sinh (8), 
cho ra chuỗi có dạng 2i ký hiệu a, với i > 0. 
 Có thể chứng minh bằng quy nạp theo số bước dẫn xuất rằng nếu luật sinh (4) 
chưa được dùng đến thì chuỗi trong dẫn xuất có một trong ba dạng như sau : 
(i) S 
(ii) AaiCajB, với i + 2j là một lũy thừa dương của 2. 
(iii) AaiDajB, với i + j là một lũy thừa dương của 2. 
Khi luật sinh (4) được áp dụng thì ta sẽ có chuỗi dạng AaiE, trong đó i là một 
lũy thừa dương của 2. Sau đó, ta chỉ có thể áp dụng i lần luật sinh (7) để đi tới dạng 
câu AEai. Cuối cùng, với luật sinh (8), ta thu được chuỗi dạng ai với i là lũy thừa 
dương của 2. 
Phần tiếp theo dưới đây, chúng ta sẽ xét mối tương quan giữa văn phạm không hạn 
chế này và mô hình máy Turing. Chúng ta chứng minh hai Định lý dưới đây thể hiện 
mối tương quan giữa lớp văn phạm không hạn chế và lớp ngôn ngữ đệ quy liệt kê r.e 
– lớp ngôn ngữ được chấp nhận bởi một máy Turing. Định lý đầu tiên sẽ chứng tỏ 
rằng mọi ngôn ngữ kiểu 0 phát sinh một tập r.e. Và sau đó ta sẽ xây dựng một giải 
thuật để liệt kê tất cả các chuỗi thuộc văn phạm kiểu 0. 
ĐỊNH LÝ 7.9 : Nếu L là L(G) với một văn phạm không hạn chế G(V, T, P, S) thì 
L là ngôn ngữ đệ quy liệt kê. 
Chứng minh 
Thiết lập một máy Turing M không đơn định, hai băng chấp nhận ngôn ngữ L. 
Băng thứ nhất (băng 1) của TM chứa chuỗi nhập w, còn băng thứ hai (băng 2), máy 
phát sinh các dạng chuỗi α của G. Đầu tiên, chuỗi α được phát sinh trên băng 2 là ký 
hiệu bắt đầu S. Sau đó, TM lặp lại quá trình sau : 
(i) Chọn một cách ngẫu nhiên một vị trí i trên α với 1 ≤ i ≤ | α |, nghĩa là TM 
xuất phát từ bên trái chuỗi α rồi tùy chọn giữa hai khả năng : hoặc chọn i là vị trí hiện 
tại, hoặc dịch chuyển sang phải và lặp lại quá trình. 
(ii) Chọn một luật sinh β → γ trong số các luật sinh thuộc tập luật sinh của G. 
(iii) Nếu chuỗi con β xuất hiện trong α kể từ vị trí thứ i, TM thay thế chuỗi β 
bởi γ (dĩ nhiên nếu | β | ≠ | γ | thì phải dịch chuyển phần cuối của α để đủ chỗ trống 
cần cho phép thay thế) 
(iv) So sánh chuỗi phát sinh được với chuỗi nhập w trên băng 1. Nếu giống 
nhau thì chuỗi mới phát sinh sẽ được chấp nhận. Nếu khác nhau thì TM trở về bước 
Chương VII : Máy Turing 
 131
(i). Ta có thể chứng minh được rằng tất cả và chỉ có những chuỗi thuộc G mới xuất 
hiện trên băng 2 ở bước (iv). 
Vậy L(M) = L(G) = L. 
ĐỊNH LÝ 7.10 : Nếu L là ngôn ngữ đệ quy liệt kê thì L = L(G) với một văn phạm 
không hạn chế G nào đó. 
Chứng minh 
Giả sử ngôn ngữ L được chấp nhận bởi máy Turing M (Q, ∑, Γ, δ, q0, B, F). 
Ta sẽ xây dựng một văn phạm không hạn chế G mà mỗi chuỗi dẫn xuất của nó phát 
sinh theo ba bước như sau : 
(i) G phát sinh một cách ngẫu nhiên một chuỗi w thuộc Σ. Chuỗi này được viết 
thành hai bản : một sẽ lưu giữ cho đến khi kết thúc, một sẽ thay đổi trong quá trình 
làm việc của TM. 
(ii) G mô phỏng lại quá trình làm việc của của TM trên chuỗi w, bằng cách lặp 
lại đúng quá trình làm việc của TM. 
(iii) Khi bước (ii) kết thúc, với sự xuất hiện của một trạng thái kết thúc q ∈ F 
của TM (nghĩa là chuỗi w đã được TM chấp nhận). Lúc đó G tiếp tục thu giảm để 
chuyển dạng câu đã có về như chuỗi w. Và như vậy, có nghĩa là chuỗi w đã được G 
sinh ra. 
Một cách hình thức, ta thiết lập văn phạm G (V, Σ, P, S1) 
Với V = ( (Σ ∪ { ε }) × Γ) ∪ { S1, S2, # }) 
 Và tập luật sinh P được xây dựng như sau : 
1. a) S1 → #q0 S2# 
b) S2 → [a, a] S2#, ∀a ∈ ∑ 
c) S2 → ε 
 - Nếu δ(q, X) = (p, Y, R) với p, q ∈ ∑; X, Y ∈ Γ thì thêm các luật sinh dạng 
(2a) và (2b) sau đây vào tập luật sinh P : 
 2. a) q[a, X][b, Z] → [a, Y]p[b, Z], ∀a, b ∈ Σ ∪ {ε} và ∀Z ∈ Γ 
 b) q[a, X]# → [a, Y]p[ε, B], ∀a ∈ Σ ∪ {ε} 
 - Nếu δ(q, X) = (p, Y, L) với p, q ∈ ∑; X, Y ∈ Γ thì thêm các luật sinh dạng 
(2c) sau đây vào tập luật sinh P : 
 c) [b, Z]q[a, X] → q[b, Z]p[a, Y], ∀a, b ∈ Σ ∪ {ε} và ∀Z ∈ Γ 
 - Nếu q ∈ F thì thêm các luật sinh (3a-e) sau đây vào tập luật sinh P: 
3. a) [a, X]q → qap, ∀a ∈ Σ ∪ {ε} và ∀X ∈ Γ 
b) q[a, X] → qap, ∀a ∈ Σ ∪ {ε} và ∀X ∈ Γ 
c) q# → ε 
d) #q → ε 
e) q → ε 
 Dùng các luật sinh (1a-c), ta có chuỗi dẫn xuất : 
 S1 ⇒ G* #q0 [a1, a1][a2, a2] … [an, an]# 
Chuỗi dẫn xuất này thể hiện hình thái bắt đầu của TM là : #q0a1a2 … an#. Bắt 
đầu từ bước này các quy tắc (2a-c) được áp dụng. Lưu ý rằng các luật sinh này trong 
Chương VII : Máy Turing 
 132
G phản ánh các quy tắc chuyển trạng thái đã được thiết kế cho TM. Cho nên quá trình 
dẫn xuất lại trong G sẽ mô phỏng lại các bước chuyển hình thái trong quá trình làm 
việc của TM. Nếu quá trình đó chuyển đến một trong những trạng thái kết thúc q ∈ F, 
tương ứng với trường hợp TM chấp nhận chuỗi a1a2 … an, thì trong văn phạm G các 
quy tắc (3a-e) sẽ được áp dụng tiếp theo và cho phép G dẫn xuất ra chính chuỗi nhập 
a1a2 … an. Hay ta có : S ⇒G* a1a2 … an
 Phần chứng minh L(M) ⊆ L(G) và L(G) ⊆ L(M) xem như bài tập. 
Tổng kết chương VII: Với sự giới thiệu mô hình máy Turing như là một mô hình 
của sự tính toán, người ta còn đi tới khái niệm về độ phức tạp của tính toán hay “độ 
khó” của các bài toán. Nghiên cứu về độ phức tạp của tính toán là một hướng nghiên 
cứu hiện đại trong Tin học, nó có ý nghĩa lớn lao về lý thuyết cũng như thực hành. 
Kết thúc chương này, sự phân lớp ngôn ngữ theo nguyên tắc của Noam Chomsky đã 
được thể hiện tương đối rõ ràng. 
BÀI TẬP CHƯƠNG VII 
7.1. Thiết kế máy Turing nhận diện ngôn ngữ: 
a) { 0n 1n 0n | n ≥ 1} 
b) {ww R | w ∈ (0+1)*} 
c) Tập hợp các chuỗi chứa 0 và 1, có số số 0 và số số 1 bằng nhau. 
7.2. Thiết kế máy Turing tính các hàm số nguyên: 
a) f(n) = n2
b) f(n) = 2n
c) f(n) = n ! 
7.3. Xây dựng văn phạm không hạn chế (loại 0) sinh ra các ngôn ngữ sau: 
a) { ww | w ∈ (0+1)*} 
b) { 0k | k = i2 và i ≥ 1} 
c) { 0i | i không là số nguyên tố} 
Chương VII : Máy Turing 
 133
BÀI TẬP LẬP TRÌNH 
7.4. Viết chương trình máy tính mô phỏng hoạt động của các TM thiết kế trong bài 
tập 7.1 và 7.2.