Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA CÔNG NGHỆ THÔNG TIN
Tel. (84-511) 736 949, Fax. (84-511) 842 771
Website: itf.ud.edu.vn, E-mail: [email protected]

Tiểu luận môn học
LÝ THUYẾT TÍNH TOÁN
Đề tài:
CÁC NGÔN NGỮ ĐỆ QUY VÀ ĐỆ QUY
LIỆT KÊ
NHÓM HỌC VIÊN : - TRƯƠNG TIẾN DƯỠNG
- NGUYỄN ĐÔNG KỲ
- VÕ TRƯƠNG HOÀNG OANH
- NGUYỄN THỊ UYÊN THẢO
LỚP : Cao học khoá 12 (2009-2011)
CBHD : PGS. TS PHAN HUY KHÁNH
ĐÀ NẴNG, 05/2010
Trang - -
1
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
MỤC LỤC
10.1 ĐỆ QUY VÀ LIỆT KÊ ĐỆ QUY 3
10.2 LIỆT KÊ MỘT NGÔN NGỮ 6
10.3 KHÔNG PHẢI MỌI NGÔN NGỮ ĐỀU LÀ LIỆT KÊ ĐỆ QUY 9
PHẦN 2: BÀI TẬP 17
PHẦN 3: TÀI LIỆU THAM KHẢO 19
Trang - -
2
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh

L và ngược lại
trả về là 0.
Một ngôn ngữ L là liệt kê đệ quy (recursively enumerable) nếu có tồn
tại một máy Turing T chấp nhận (accept) L và đệ quy nếu có một máy Turing
nhận ra L.
Mọi ngôn ngữ đệ quy cũng đều là liệt kê đệ quy nếu: T là một máy
Turing nào đó nhận ra L thì khi đó một máy bổ sung sẽ crash thay vì trả về kết
quả 0 chấp nhận L. Vậy là chúng ta đã nhận diện được vấn đề còn tồn đọng
(potential) với hướng đi trái ngược nhau. Nếu T là một máy Turing chấp nhận
L thì có thể có các chuỗi không nằm trong L mà T crashes và khi đó sẽ không
bao giờ có được câu trả lời. Sau chương này chúng ta sẽ nghiên cứu
(investigate) thêm các ngôn ngữ có khả năng không thể loại bỏ (khử) được.
Còn bây giờ chúng ta hãy ghi nhận một phần (partial) kết quả mà chúng ta đã
đề cập.
Định lý 10.1 Nếu L được chấp nhận bởi một máy Turing T không xác định và
mỗi bước di chuyển có thể của T cho ra kết quả hoặc là dừng hoặc là crash thì
khi ấy L là đệ quy.
Trang - -
3
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
Chứng minh: chúng ta xây dựng máy Turing T’ sao cho có một sự thay đổi
của máy Turing T
2
trong phần chứng minh định lý 9.2. Trong trường hợp đó,
T
2
tái tạo mỗi bước di chuyển hữu hạn có thể của T, máy T dừng lại nếu T tìm
thấy bước mà gây cho T dừng, và ngược lại máy T sẽ lặp mãi mãi. Máy mà
chúng ta cần bây giờ phải khác với hai dấu hiệu này. Trước tiên, nếu và khi T’
tìm thấy một bước di chuyển của T làm cho T dừng thì T sẽ tạo xuất ra

∩
L
2
cũng là ngôn ngữ liệt kê đệ quy.
Chứng minh: Giả sử rằng T
1
= (Q
1
,
∑
,
1
Γ
, q
1
,
1
δ
) và T
2
= ((Q
2
,
∑
,
2
Γ
, q
2
,

2
x Q
2
.
Nên nhớ lại (recall) kỹ thuật này không làm việc với PDAs vì các ngăn xếp.
Lý do để máy Turing thực hiện được ở đây là chúng ta thoải mái sử dụng 2
băng trong máy Turing. Chúng ta mô tả giải pháp này cho L
1
∪
L
2
.
Máy Turing 2 băng (two – tape) T = (Q
1
,
∑
,
Γ
, q
0
,
δ
) bắt đầu bằng
việc sao chép chuỗi nhập x trên băng 2 và chèn một dấu # để đánh dấu lúc bắt
đầu trên mỗi băng. Mô phỏng đồng thời (the simultaneous simulation) máy
Turing T
1
trên băng 1 và máy Turing T
2
trên băng 2 thực hiện (to accomplish)

i
, a
i
) = (q
i
, b
i
, D
i
). Các kết quả mô phỏng này
có thể là:
1. Cả T
1
và T
2
đều dừng lại trong trường hợp T không bao giờ dừng.
2. Ít nhất một trong hai máy T
1
và T
2
dừng trong trường hợp T dừng
3. Một trong hai máy crash. Nếu cả hai máy crash đồng thời thì T crash.
Nếu một máy crash, T cũng bỏ qua mô phỏng này (ví dụ như là bỏ qua
băng đó) và tiếp tục với máy khác. Nếu một máy dừng lại do hoặc là
crash hoặc là dừng, thì T cũng dừng theo cách đó.
Việc xây dựng gây cho T dừng khi và chỉ khi có ít nhất một trong hay máy
T
1
và T
2

trường hợp nào rõ ràng trong các ngôn ngữ liệt kê đệ quy. It does not
immediatetly follow that the coresponding statement for RE languages is false
(although it is); howerver, the next result suggests that it is at least less likely
to be true.
Định lý 10.4 Nếu L là ngôn ngữ liệt kê đệ quy whose complement is RE thì L
là đệ quy.
Trang - -
5
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
Chứng minh: Cho T1 và T2 là các máy Turing chấp nhận ngôn ngữ L và L’.
Chúng ta xây dựng một máy Turing T hai băng dùng để đón nhận L, bắt đầu
việc xây dựng như trong chứng minh định lý 10.2 cho trường hợp hợp của 2
ngôn ngữ. Sự khác nhau ở chỗ là bây giờ chúng ta biết trước (in advance)
được bất cứ chuỗi nhập x nào, rõ ràng (precisely) là một trong 2 máy Turing
T1 và T2 sẽ dừng lại. Do đó, có đủ khả năng để hiệu chỉnh máy T như sau:
Lúc T1 hoặc T2 dừng, T sẽ xóa bỏ trên băng 1 và xuất ra 0 hoặc 1 trước khi
dừng, điều này tùy thuộc vào máy dừng chấp nhận L hoặc L’ hay không.
10.2 LIỆT KÊ MỘT NGÔN NGỮ
Chúng ta bắt đầu bằng việc mô tả một cách chính xác cách mà một máy
Turing liệt kê 1 ngôn ngữ. Điều này có ích khi sử dụng máy Turing có ít nhất
hai băng, trong đó một băng được thiết kế như là băng xuất.
Định nghĩa 10.2 Cho T là máy Turing k băng, trong đó k >= 2, và cho L
∑
⊆
*
. Chúng ta nói rằng T liệt kê L nếu T hoạt động sao cho các điều kiện
sau được thỏa mãn:
1. Băng đầu trên băng đầu tiên không được dịch chuyển sang trái
2. Tại mỗi một thời điểm trong hoạt động của T, băng 1 chứa:
x

Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
Mặc khác, nếu chúng ta có một máy Turing T dùng để liệt kê L thì khi
đó cho trước một chuỗi nhập x, chúng ta có thể thử (to attempt) kiểm tra xem
x đối với phần tử trong L bằng cách chờ xem (waiting to see) x có xuất hiện
trên băng xuất của T hay không. Máy Turing T
1
có thực hiện chiến lược này
bảo đảm (guarantee) chấp nhận L vì nếu chuỗi x nằm trong L thì cuối cùng x
cũng sẽ xuất hiện, còn nếu x không nằm trong L thì x sẽ không xuất hiện (vì
thế máy Turing sẽ lặp mãi trừ phi L là hữu hạn)
Mặc khác, nếu T là một máy Turing chấp nhận L thì khi đó liệt kê L,
chúng ta bắt đầu bằng một vài thứ tự chuẩn của tất cả các chuỗi nằm trong
∑
*
, chẳng hạn như thứ tự kinh điển (canonical order) đã được giới thiệu
trong phần 9.6. Trong thứ tự này, những chuỗi nào ngắn hơn đến trước (to
precede) những chuỗi dài hơn, đồng thời những chuỗi nào có cùng độ dài thì
được xếp theo thứ tự alphabe. Chúng ta xét tất cả các chuỗi theo thứ tự này,
đồng thời với mỗi chuỗi x chúng ta thử chọn kể cả x trong việc liệt kê của
chúng ta. Đây là chỗ mà lý luận cần phức tạp một chút: máy T có thể lặp mãi
trên chuỗi nhập x. Chứng minh chính thức của chúng ta có thể sẽ vận dụng
(handle) vấn đề này.
Định lý 10.5 Một ngôn ngữ L
⊆
∑
*
là liệt kê đệ quy (có thể được chấp nhận
bởi một số mát Turing) khi và chỉ khi L có thể được liệt kê bởi một số máy
Turing.
Chứng minh: Giả sử T là một máy Turing liệt kê L. Một máy T

1
ba băng liệt kê ngôn ngữ L. Băng 1 là
băng xuất, băng 2 được dùng bởi T
1
để tạo ra các chuỗi trong tập
∑
*
và băng
3 là băng T
1
sử dụng để mô phỏng hành động của T trên mỗi chuỗi được tạo.
Để tránh khó khăn được thảo luận ở trước, T
1
mô phỏng tuần tự hữu hạn
các bước chuyển động của T hơn là cố tiếp tục hoàn thành việc xử lý T trên
một chuỗi đơn . Vì lý do này trên băng 2 không chỉ lưu lại các chuỗi được tạo
ra cho đến bây giờ (so far) mà số lượng các bước di chuyển của T cũng được
thực hiện trên mỗi chuỗi đó.
Chúng ta chọn (adopt) thứ tự trên
∑
*
. Lấy ví dụ nếu
∑
={a,b} thì các
chuỗi được tạo ra theo thứ tự sẽ là :
∧
, a, b, aa, ab, ba, bb, aaa, aab, …, bbb, aaaa, aaab,…
Máy Turing T
1
tạo một dãy các vị trí (pass). Với vị trí đầu tiên, T

Trang - -
8
i i - 1 i - 2
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
vị trí này là để kết thúc băng 2 phần tử tiếp theo của
∑
*
(phần tử này đứng
sau x), đặt một chữ 1 sau x đồng thời mô phỏng bước di chuyển của T trên
chuỗi nhập đó.
Chúng ta không chỉ ra một cách rõ ràng (explicitly) các thiết bị theo dõi
mà T cần để thực hiện những bước này, tuy nhiên các bước này hoàn toàn dễ
hiểu (straightforward). Rõ ràng mọi chuỗi đều được chấp nhận bởi máy T
ngay cả chuỗi được liệt kê trên băng 1 và không có chuỗi được liệt kê.
Trong phần chứng minh định lý 10.5, chúng ta nên lưu ý rằng mặc dầu
những chuỗi trong
∑
*
được tạo theo thứ tự cổ điển trên băng 2, nói chung các
chuỗi trong ngôn ngữ L không được liệt kê theo thứ tự trên băng 1. Với các
giả định tốt hơn (stronger assumption) về máy T có nghĩa là giả định rằng
(amount to assuming) ngôn ngữ L không chỉ là có thể liệt kê đệ quy mà còn đệ
quy. Ngược lại, dễ dàng chỉ ra rằng nếu có một máy Turing T liệt kê ngôn ngữ
L theo thứ tự cổ điển thì khi ấy L phải là đệ quy.
Định lý 10. 6: L là đệ quy khi và chỉ khi có một máy Turing liệt kê ngôn ngữ
L theo thứ tự cổ điển.
Chứng minh: Chứng minh xem bài tập Exercise 10.7
10.3 KHÔNG PHẢI MỌI NGÔN NGỮ ĐỀU LÀ LIỆT KÊ ĐỆ QUY
Các mô hình tính toán đơn giản mà chúng ta vừa xem xét trước đây,
Automat hữu hạn (Fas) và Automat đẩy xuống (PDAs) đều có khả năng

như ở trên sao cho bất kì chuỗi x
∈
S, nếu chúng ta ghi xuống đầy đủ các số
hạng (term) f(0), f(1), thì khi đó x xuất hiện như là một trong những số hạng
này. Quan trọng hơn nữa, khi chúng ta nói rằng một tập S là vô hạn đếm được,
chúng ta không nói có một số giải thuật để liệt kê các phần tử này. Chúng ta
chỉ nói rằng “có tồn tại” một song ánh (bijection) f; có thể có hoặc không có
một giải thuật nào cho phép chúng ta tìm ra được f(n) đối với một số tự nhiên
n đã cho.
Lưu ý rằng bất kì 2 tập hữu hạn đếm được nào cũng đều có kích thước
tương tự nhau. Nó có thể là trường hợp mà tất cả các tập không đếm được đều
có kích thước giống nhau. Nếu trên thực tế (in fact) có các tập vô hạn kích
thước khác nhau, tuy nhiên bất cứ một tập không đếm được nào cũng đều lớn
hơn một tập có thể đếm được. Mặc dù điều này không được rõ ràng lắm nhưng
đây là một kết quả có được ngay tức thì (immediate consequence) của cơ sở
lập luận (fact) sau.
Trang - -
10
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
Bổ đề 10.1. Mọi tập vô hạn đều có một tập con vô hạn đếm được.
Chứng minh: Chúng ta chỉ ra rằng nếu S là vô hạn, có một song ánh f từ N
đối với tập con của S. Lúc này chúng ta định nghĩa f là một số nguyên, as
follows. Vì S là vô hạn do đó có ít nhất một phần tử; chọn một phần tử đồng
thời gọi phần tử này là f(0). Nói chung, giả sử ta có một số n >0 , f(0), f(1),
…,f(n) là các phần tử S phân biệt nhau. Vì S là vô hạn do đó sẽ có một phần tử
của S không phải là một trong những phần tử này; chọn bất kì phần tử nào, và
gọi nó là f(n+1). Do đó, bằng phương pháp quy nạp toán học (by the principle
of methematical induction), f(n) có thể được định nghĩa với mọi n > = 0 sao
cho tất cả các phần tử f(i) đều phân biệt được nhau.
Một yếu tố khác của các tập đếm được này là tính hữu dụng: bất cứ tập

Giả sử rằng chúng ta định nghĩa hàm f như sau:
Trang - -
11
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
F(i) =
Khi đó f là một song ánh, hoặc từ {0,1,…,m} đến S hoặc từ N đến S, phụ
thuộc vào tập S là hữu hạn hoặc vô hạn hay không. Do đó, S là một tập đếm
được.
a
0,0
a
0,1
a
0,2
a
0,3
a
0,4
…
a
1,0
a
1,1
a
1,2
a
1,3
a
1,4
a


∞
=0n
n
S
Vì mỗi tập

k
n
n
S
0=
là một tập hợp con của S, chúng ta có thể kết luận
(conclude) rằng hợp của các tập đếm được hữu hạn thì cũng là đếm được.
Ví dụ 10.1: Cho S = N x N, là tập tất cả các cặp số tự nhiên có thứ tự. Theo
định lý 10.7 thì S là đếm được vì:
N x N =

∞
=
×
0
)}({
m
Nm
Và mỗi tập {m}
×
N là đếm được vì hàm f
m
: N

Đây chỉ là một cách khác để nói rằng:
f
-1
(m,n) = (m+n)(m+n+1)/2 + m
Hàm f này thường được xem như là một hàm đôi và hữu dụng trong
một số các chủ đề về đếm.
Đối số được sử dụng trong ví dụ này có thể được hiệu chỉnh một cách
dễ dàng để cho biết bất kì tập S đếm được nào đó thì S x S cũng là tập đếm
được.
Ví dụ 10.2 Cho một tập
∑
bất kỳ, tập
∑
*
của tất cả các chuỗi trên
∑
là
đếm được. Chúng ta viết:
∑
*
=

∞
=
∑
0n
n
Trong đó
∑
n

đếm được.
Ví dụ 10.3 cung cấp một nữa kết quả mà chúng ta tìm kiếm. Chúng ta
đã chỉ ra tập các ngôn ngữ liệt kê đệ quy là đếm được, chứng minh rằng có
nhiều ngôn ngữ không thể đếm được (ví dụ tập các ngôn ngữ không đếm
được) sẽ chỉ ra rằng phải có các ngôn ngữ không phải là liệt kê đệ quy.
Chứng minh nổi tiếng nhất 1 tập không thể đếm được là lý luận đường
chéo cổ điển (the classic diagonal argument) của nhà toán học Đức Georg
Cantor vào thế kỉ thứ 19 chỉ ra tập các số thực là không thể đếm được.
Định lý 10.8 Nếu S là một tập vô hạn đếm được bất kỳ, khi ấy tập 2
S
của tất cả các tập hợp con của S là vô hạn không đếm được. Rõ ràng là với bất
cứ tập aphabet
∑
không rỗng nào thì tập các ngôn ngữ trên
∑
là không đếm
được.
Chứng minh: Đơn giản chúng ta có thể chứng minh bằng một lưu ý đó
là vì có một song ánh từ N tới S, do đó có một song ánh từ 2
N
đến 2
S
. Do đó đủ
để nói rằng 2
N
là không đếm được, khi đó 2
S
cũng không đếm được.
Ta chứng minh ngược lại. Giả sử 2
N

(fails to satisfy) định nghĩa điều kiện của A, và do đó I
∉
A = A
I
. Mặt khác,
nếu I
∉
A
I
thì khi đó I thõa mãn điều kiện phần tử trong A, và do đó I
∈
A =
A
I
.
Tại thời điểm này, bắt đầu bằng việc giả định (assumption) rằng 2
N
là vô hạn
đếm được, chúng ta đã tìm ra được tập A
⊆
N và một số tự nhiên I sao cho:
1. Nếu I
∈
A thì I
∉
A ; và
2. Nếu I
∉
A thì I
∈

Trang - -
15
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
Định nghĩa A hy vọng chứng minh để dẫn đến tên gọi đối đường chéo
(diagonal argument). Chúng ta có thể trình bày lại vấn đề này theo khía cạnh
hình học. Xét một mảng hai chiều vô hạn như hình bên dưới với dòng i và cột
j được đánh số, phần tử thứ (i,j) là giá trị đúng của phát biểu i
∉
A
j
.
0 1 2 3 …
0 0
∉
A
0
0
∉
A
1
0
∉
A
2
0
∉
A
3
…
1 1

3
3 3
∉
A
0
3
∉
A
1
3
∉
A
2
3
∉
A
3
…
Các phần tử đường chéo của ma trận được gạch dưới ở trong sơ đồ. Tập A là
tập các phần tử i để cho phần tử đường chéo i
∉
A
j
là đúng. Chúng ta sẽ xem
xét các loại đối số này trong các phần kế tiếp cũng như các phần sau.
Trang - -
16
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
PHẦN 2: BÀI TẬP
I. Để loại bỏ lệnh hoán đổi S<n,m> trong máy Ram thô sơ để chỉ còn lại các

Trang - -
17
Tiểu luận Lý thuyết tính toán GVHD: PGS.TS Phan Huy Khánh
R4 = 0;
}
While (R3 <> 0 )
{
R3 = R3 – 1
R4 = R2 + R1
R1 = R2
R2 = R4
}
• Chương trình Ram thô sơ
STT LỆNH RAM Ý NGHĨA
J <3> (KQ1, TIEP) Nếu R3 = 0 thì KQ1=0 &
halt, R3 <> 0 thì nhảy đến
nhãn TIEP
TIEP: Z <1> R1 = 0
Z <2>
I <2> R2 = 1
LAP: J <3> (KQ2, TINH)
TINH: D <3> R3 = R3 – 1
Z <4> R4 = 0
GR1R4: J <1> (ADDR2R4,GAN) Sau vòng lặp: R4 = R1 &
nhảy đến nhãn ADDR2R4
GAN: D <1> R1 = R1 – 1
I <4> R4 = R4 + 1
J <5> (GR1R4,GR1R4) Quay lại vòng lặp
ADDR2R4 : J <2> (GR4R2,ADD) Sau vòng lặp:
R4 = R4 + R2; R1 = R2 &