ĐẠ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: http://dut.ud.edu.vn/itf, E-mail: [email protected]

BÀI TẬP LỚN MÔN
LÝ THUYẾT TÍNH TOÁN
Đề tài: Lý thuyết về máy Turning không đơn định,
vạn năng và bài tập về kỹ thuật dịch chuyển RASP
HỌC VIÊN : TẠ THỊ ÁI NHI
ĐỖ PHÚ DUY
LÊ THANH TÙNG
LỚP : KHMT K12
CBHD : PGS.TS. PHAN HUY KHÁNH
ĐÀ NẴNG, 05/2010
Mục lục
LÝ THUYẾT 1
.I Máy Turning không đơn định 1
.II Máy Turning vạn năng 7
BÀI TẬP ỨNG DỤNG 12
.I Thuật toán 12
.II Chương trình máy RASP 12
TÀI LIỆU THAM KHẢO 15
LỜI MỞ ĐẦU
Lý thuyết tính toán là là các từ được sinh ra bởi một văn phạm, tức tập các quy
tắc để sinh ra ngôn ngữ. Lý thuyết tính toán không sử dụng các lệnh gán biến và
không gây ra hiệu ứng phụ như vẫn gặp trong lập trình mệnh lệnh. Nguyên cứu
những phương pháp lập trình này giúp ích rất nhiều cho việc nghiên cứu về kỹ
thuật lập trình trong các lĩnh vực trí tuệ nhân tạo, giao tiếp hệ thống, xử lý ký
hiệu, tính toán hình thức,…v.v

0,
δ) được định nghĩa giống
như một máy Turning đơn định ngoại trừ các giá trị của hàm dịch chuyển δ là các tập hợp
của các phần tử đơn của tập hợp (Q ∪ {h
a
,h
r
}) x (Г ∪ {∆}) x {L, R, S}. Ta không cần nói
rằng δ là một hàm cơ bản bởi vì bây giờ δ(q,a) được phép nhận giá trị ø.
Diễn giải cho hình trạng máy Turning cũng không thay đổi.
(p, xay) |-
T
(q, wbz) có nghĩa là từ hình trạng đầu tiên, có ít nhất một dịch chuyển đến
hình trạng thứ hai. Tương tự, ta có (p, xay) |-
T
* (q, wbz) nghĩa là có ít nhất một dịch
chuyển rỗng hoặc nhiều dịch chuyển thông qua T từ hình trạng thứ nhất đến hình trạng
thứ hai. Với định nghĩa này, ta có thể nói rằng một xâu x
∈
∑* được thừa nhận bởi T nếu
tồn tại a
∈
Γ∪{∆} và tồn tại y, z
∈
(Γ∪{∆})* sao cho (q
0,
∆

x) |-
T

2
= (Q
2,
∑, Г
2
, q2
,
δ2) sao cho L(T
2
) = L(T
1
).
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 1
Bài tập lớn – Môn: Lý thuyết tính toán
Chứng minh
Máy Turning T
2
mà chúng ta đang tìm sẽ có tính chất sao cho bất kỳ x
∈
∑*, T
2
thừa
nhận x nếu và chỉ nếu có một vài dịch chuyển của T
1
với đầu vào x được chấp nhận.
Chiến lược cho việc xây dựng T
2
chỉ đơn giản là với mỗi thứ tự của các dịch chuyển của
T
1

chuyển và v.v Máy Turning mà ta xây dựng sẽ không hiệu quả bởi vì với n+1 bước thì sẽ
lặp lại n bước trước đó. Thậm chí nếu cây là hữu hạn (nghĩa là với một vài n, mỗi hình
trạng có thể có trong T
1
từ xâu x sẽ dẫn đến trạng thái dừng), thì T
2
sẽ lặp vô tận nếu T
1
không bao giờ chấp nhận: Nó sẽ cố gắng để thử tất cả các dịch chuyển và hiệu quả sẽ có
nếu nó kết thúc việc lặp các dịch chuyển giống nhau với cùng thứ tự và cứ thế. Tuy
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 2
1
0
1
0
1
0
0 1
…
…
Bài tập lớn – Môn: Lý thuyết tính toán
nhiên, nếu x
∈
L(T
1
) thì với mỗi n, có một thứ tự của n dịch chuyển làm T
1
thừa nhận x và
T
2

1
sẽ chuyển
đến C
2
. Bởi vì các dịch chuyển 0 và 1 có thể như nhau vì thể có một vài chuỗi số mô tả
các bước dịch chuyển giống nhau. Cũng có thể các chuỗi số không tương ứng với thứ tự
của sự dịch chuyển bởi vì một vài dịch chuyển đầu tiên làm T
1
dừng. Khi T
1
gặp một số
không thích hợp để thực hiện việc dịch chuyển, nó sẽ bỏ qua chuỗi đó.
Ta sẽ dùng thứ tự canonical của {0,1}* thì các xâu được sắp xếp như thứ tự
Λ, 0, 1, 00, 01, 10, 11, 000, 001, …, 111, 0000, …
(Với 2 xâu có chiều dài khác nhau thì xâu ngắn hơn xử lý trước và thứ tự của 2 xâu có
cùng chiều dài được đánh số). Cho một xâu α thể hiện các trạng thái dịch chuyển, T
2
tạo
ra xâu tiếp theo với thứ tự này bằng việc tích hợp α như xâu nhị phân bằng việc cộng
thêm 1. Nếu không α = 1
k
với xâu kế tiếp là 0
k+1
.
Thật dễ để mô tả cấu trúc chung của T
2
bây giờ. Nó bao gồm 5 máy Turning nhỏ hơn
gọi là InitializeTapes2&3, CopyInput, Execute, EraseTape2 và NextSequence trong Hình
9.16
Hình 9.16. Mô phỏng máy Turning không đơn định bởi máy Turning có 3 băng

EraseTape3 lưu trữ băng 3 với hình trạng #∆ . Nó có thể hoàn thành hoạt động này bởi vì
chiều dài của xâu trên băng 2 giới hạn ký hiệu bên phải nhất không được là ký tự không
trống trên băng 3. Cuối cùng, NextSequence là thành phần đã sẵn sàng được đề cập để
cập nhật chuỗi số trên băng 2 bằng việc thêm 1 vào chuỗi nhị phân. Hình 9.17 thể hiện
một băng của máy Turning thực hiện sự chuyển hóa này với một xâu vào chứa 0 và 1;
NextSequence là máy Turning thứ ba mang dịch chuyển đến băng 2, bỏ qua băng 1 và 3.
Hình 9.17. Phiên bản một băng của NextSequence
Vấn đề của việc xây dựng T
2
được giảm bằng việc xây dựng thành phần Execute,
thành phần này cần mô phỏng các dịch chuyển của T
1
từ chuỗi của các số trên băng 2.
Để mô tả thành phần này một cách cụ thể thì khó, vì thế thay vì làm việc đó, ta xem xét
một phần nhỏ của sơ đồ dịch chuyển cho T
1
như Hình 9.18a và đưa ra sơ đồ cho Execute
tương ứng như Hình 9.18b. Các trạng thái của Execute bao gồm các trạng thái của T
1
và
những thứ khác. Ta tiếp tục giả định số sự lựa chọn lớn nhất tại bất kỳ vị trí nào của T
1
là
2. Ta đơn giản hóa mọi thứ bằng việc giả định rằng Г
1
= {a} vì thế a và ∆ chỉ là các ký tự
trên băng của T
1
. Cuối cùng, vì băng 1 được bỏ qua bởi Execute, nên chúng ta chỉ biểu
diễn máy này như là máy 2 băng trong Hình 9.18b.

1
bỏ đi
ký hiệu * tại vị trí hiện tại trên băng 3 và làm Execute chấp nhận. Đây là các dịch chuyển
đầu tiên được thể hiện từ p đến h trong Hình 9.18b. Chú ý rắng nó loại bỏ các chỉ lệnh để
chuyển đầu đọc trên băng 3 sang phải với giả thiết rằng nếu T
1
bị hóc tại vị trí hiện tại
trên băng là bất hợp lệ. Hai trạng thái kế tiếp từ p đến h tương ứng với các chuyển tiếp
làm T
1
đẩy ra. Hai trạng thái cuối cùng dành cho tình huống khi ký tự trên băng 2 là ∆,
xác định rằng dịch chuyển hiện tại được mô phỏng hoàn toàn.
Một dịch chuyển khác từ trạng thái p trong Execute là dịch chuyển tương ứng với sự
lựa chọn 1. Điều này xuất hiện khi số hiện tại trên băng 2 là 1 và ký hiệu trên băng 2 là a.
Lý do dịch chuyển này không trực tiếp chuyển sang trạng thái q là Execute cần kiểm tra
trước liệu dịch chuyển này có khả năng với T
1
không. Nó thực hiện bằng việc dịch đầu
đọc trên băng 3 sang trái và chuyển đến trạng thái tạm. Từ trạng thái này, bất kỳ ký tự
nào trên băng 3 khác # thì xác định rằng T
1
đã dịch chuyển an toàn và Execute có thể
chuyển đến trạng thái q ngay khi T
1
có vị trí đầu tiên. Ký hiệu # xác định một va chạm
bởi T
1
và Execute dừng bình thường sau khi trả đầu đọc về ô bên phải của #.
Mặc dù ví dụ nhỏ này không chỉ ra từng tình huống có thể xuất hiện nhưng nó giúp
cho việc chứng mình rằng toàn bộ sơ đồ trạng thái cho T1 có thể được đổi thành một sơ

(─, a)/ (─, a), (S,S)
(─, ∆)/(─, ∆), (S,S)
(─, #)/(─, #), (S,R)
(a) (b)
Bài tập lớn – Môn: Lý thuyết tính toán
Một ví dụ đơn giản của không đơn định
Xem xét máy Turning Double làm việc như sau. Việc dùng máy Turning Copy trong
ví dụ 9.7 chỉnh sửa một ký hiệu trong ký tự vào, nó tạo ra một bản sao của đầu vào là số.
Sau khi xóa các tự trống trong đầu vào ban đầu từ bản sao và trả lại đầu đọc về ô số 0.
Giống như tên của nó, nó gấp đôi giá trị của đầu vào.
Hình 9.19. Một máy Turning không đơn định đoán nhận xâu có chiều dài 2
i
Bây giờ hãy xem xét máy Turning không đơn định T trong Hình 9.19. T dịch chuyển
qua xâu vào, thay thế 1 trên băng, tách riêng các ký tự vào bởi ký tự trống và sau đó đặt
đầu đọc tại ký tự trống, thự thi Double 0 hoặc nhiều lần trước khi trả đầu đọc về ô thứ 0.
Cuối cùng, nó thực thi TM Equal và máy TM này làm việc như sau: Bắt đầu với nội
dung trên băng ∆

x∆

y nơi mà x và y là xâu chứa 1, Equal thừa nhận nếu và chỉ nếu x=y
(xem ví dụ 9.9)
Tính không đơn định trong T sản sinh ra số lần Double không xác định được thực thi.
Khi Equal được thực thi hoàn toàn, xâu kế tiếp sau đầu vào trên băng là bội số của 2. Nếu
xâu ban đầu là bội số của 2 (2
i
) thì một thứ tự của các lựa chọn mà T có thể tạo ra sẽ làm
xâu đó được thừa nhận, Double được thực hiện chính xác i lần. Mặc khác, nếu xâu vào
không phải là bội số của 2, nó sẽ không được thừa nhận bởi vì tại bước cuối cùng nó
được so sánh với một chuỗi là bội số của 2. Kết luận là T thừa nhận ngôn ngữ {1

Bài tập lớn – Môn: Lý thuyết tính toán
.II Máy Turning vạn năng
Cho đến nay trong các cuộc thảo luận của chúng ta, một máy Turing được tạo ra để
thực hiện một thuật toán cụ thể. Nếu chúng ta có một máy Turing được dùng chỉ để tính
toán cho một hàm thì khi ta cần tính toán một hàm khác hoặc thực hiện một số tính toán
khác thì cần có một máy Turning khác. Ban đầu, máy tính điện tử cũng bị giới hạn một
cách tương tự như vậy, và thay đổi các tính toán sẽ được thực hiện bằng việc mắc lại
máy.
Một bài báo năm 1936 của Turing, với các máy tính với các chương trình được lưu
trữ (stored-program) mà bạn quen thuộc. Mặc dù một máy tính hiện đại vẫn còn được gắn
cứng (hard-wired), nhưng nó khá mềm dẻo để thực hiện các chỉ lệnh được lưu trữ trong
bộ nhớ và chúng có thể hiện được bằng bất kỳ thuật toán có khả năng. Turning đã mô tả
một máy Turning vạn năng như sau. Nó là một TM T
u
mà đầu vào bao gồm chủ yếu của
chương trình và tập hợp dữ liệu cần thiết để cho chương trình xử lý. Chương trình lấy các
từ của một chuỗi được xác định bới TM T
1
, và tập hợp dữ liệu là chuỗi thứ hai z được
xem là đầu vào cho T
1
. T
u
sau đó mô phỏng quá trình đoán nhận z bởi T
1
. Trong phần này
chúng tôi sẽ mô máy Turning vạn năng T
u
.
Bước đầu tiên là xây dựng một hệ thống ký hiệu để mã hóa một TM tùy ý T

bảo rằng mã hóa của chúng khác nhau, chúng ta phải đảm bảo rằng các số nguyên được
gán cho b và c là khác nhau. Để đáp bất kỳ TM và vẫn đảm bảo rằng mã hóa là một-một,
chúng tôi phải sửa chữa nó bằng cách nào đó để không có bất kỳ biểu tượng trong bảng
chữ cái của TM nhận được cùng một số với bất kỳ biểu tượng khác trong bảng chữ cái
bất kỳ TM khác. Cách dễ nhất để xử lý vấn đề này là để sửa một lần và liệt kê tất cả các
bộ biểu tượng có thể được sử dụng bởi TM và đánh số các biểu tượng này lúc ban đầu.
Đây là lý do.
Quy ước: Ta giả định từ thời điểm này với hai tập vô hạn được xác định Q = {q
1
, q
2
, }
và S = {a
1
, a
2
, } vì thế với bất kỳ máy Turing T = (Q, Σ, Г, q
0
, δ), ta có Q⊆Q và Г⊆ S.
Rõ ràng rằng, giả định này về các trạng thái không phải là một hạn chế ở tất cả, bởi vì
các gán cho các trạng thái của một TM là không thích hợp. Hơn nữa, S chứa tất cả các
chữ cái, chữ số, và các ký hiệu khác mà ta đặt vào bảng chữ cái đầu vào của, giả thiết
khác cũng tương tự (không có hạn chế hơn, ví dụ giới hạn tập ký tự là 256 ký tự) . Một
khi ta có một subscript được gán vào một trạng thái có thể và biểu tượng trên băng, chúng
tôi có thể biểu diễn một trạng thái hoặc một biểu tượng bởi một dãy số 0 với độ dài phù
hợp; dãy số 1 được sử dụng như những phần phân cách.
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 7
Bài tập lớn – Môn: Lý thuyết tính toán
Định nghĩa 9.5: Hàm mã hóa e
Trước tiên chúng ta kết hợp với từng biểu tượng băng (bao gồm cả Δ), từng trạng thái

s (L) = 00
s (R) = 000
Mỗi dịch chuyển m của một TM được mô tả bởi công thức
δ (p, a) = (q, b, D)
được mã hoá bằng chuỗi
e (m) = s (p)1s (a)1s(q)1s(b)1s(D)1
và cho bất kỳ T TM, với q trạng ban đầu, T được mã hoá bằng chuỗi
e (T) = s (q)1e(m
1
)1e(m
2
)1 e (m
k
) 1
với m
1
, m
2
, , m
k
là những dịch chuyển riêng biệt của T với một thứ tự tùy ý. Lưu ý rằng
việc mã hóa s(a) của ký tự a
∈
S khác với việc mã hóa e(a) của xâu a. Bởi vì các dịch
chuyển của TM T có thể xuất hiện trong xâu e(T) với thứ tự bất kỳ vì thế có nhiều cách
để mã hóa T. Tuy nhiên với chuỗi 0 và 1 thì mã hóa nhiều nhất là một TM.
Ví dụ: Mã hóa một máy Turning đơn giản
Xem xét TM trong Hình 9.20 biến đổi một chuỗi đầu vào của a và b của bằng cách
thay đổi tận cùng bên trái a, nếu có b. Hãy đơn giản hóa những biểu tượng trên băng a và
b bằng các số 1 và 2 để s(a)=00 và s(b)=000 và các trạng thái q

∆/∆, S
b/b, L
h
a
Bài tập lớn – Môn: Lý thuyết tính toán
Hãy nhớ rằng phần đầu tiên của chuỗi, trong trường hợp này 0001 xác định trạng thái
ban đầu của TM này. Việc di chuyển còn lại của chuỗi được phân cách bằng các khoảng
trắng cho dễ đọc.
Đầu vào của một máy Turning vạn năng T
u
sẽ bao gồm một chuỗi dạng e(T)e (z),
trong đó T là một TM và z là một chuỗi trên bảng chữ cái đầu vào của T. Trong ví dụ 9.11
nếu chuỗi đầu vào của T là baa thì chuỗi đầu vào tương ứng với T
u
sẽ bao gồm chuỗi các
e (T) đưa ra trong ví dụ theo sau là 10001001001. Trên bất kỳ chuỗi đầu vào có dạng e(T)
e(z), ta muốn T
u
chấp nhận khi và chỉ khi T chấp nhận đầu vào z và trong trường hợp này
ta muốn đầu ra từ T
u
là hình thức được mã hóa của đầu ra được tạo ra bởi T với đầu vào z.
Bây giờ chúng tôi đã sẵn sàng để xây dựng T
u
. Nó sẽ được thuận tiện để đưa ra ba
băng. Theo quy ước với nhiều TM, băng đầu tiên sẽ là băng vào và băng ra. Ban đầu, nó
sẽ chứa chứa chuỗi e(T)e(z). Băng thứ hai sẽ là băng làm việc trong các mô phỏng của T,
và băng thứ ba sẽ chứa các mã hoá của T ở trạng thái hiện tại.
Bước đầu tiên của T
u

(a, b, c) / (a, b, c), (D
1
, D
2
, D
3
)
Một khi các tuple-5 thích hợp được tìm thấy, ba phần cuối nói cho T
u
làm thế nào để
mô phỏng sự di chuyển. Để minh họa, giả sử rằng trước khi tìm kiếm, ba băng của T
u
như
sau:
Δ00010100001010001100001001000001000100110001
Δ010010010001Δ
Δ0000Δ
Băng tương ứng của T sẽ là
ΔaabΔ
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 9
Bài tập lớn – Môn: Lý thuyết tính toán
(0,-,-),(R,S,S)
(0,-,-),(R,S,S)
(0,-,0),(R,S,R)
(1,-,-),(R,S,S)
(1,-,-),(R,S,S)
(-,-, ),(S,S,R)
(-,-,0),(S,S,L)
(1,-, ),(R,S,L)
(0,-,1),(R,S,L)

Δ0100100010001Δ
Δ00000Δ
Và bây giờ T
u
đã sẵn sàng để mô phỏng các trạng thái tiếp theo.
Có một số cách làm quá trình này dừng lại. T có thể bị dừng một cách bất thường bởi
vì ở đó không có dịch chuyển xác định hoặc là dịch chuyển làm đầu đọc di chuyển ra
khỏi băng. Trong trường hợp đầu tiên, các hoạt động tìm kiếm hình trong Hình 9.21 cũng
tạm dừng bất thường (mặc dù di chuyển đến h
r
không được hiển thị rõ ràng), bởi vì khi
qua 5-tuple cuối cùng trên băng 1 đã thực hiện không thành công, thứ hai của 1 ở cuối
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 10
Bài tập lớn – Môn: Lý thuyết tính toán
cùng làm máy trở lại tình trạng ban đầu, và không có di chuyển từ trạng thái đó với 1 trên
băng 1. Chúng ta có thể dễ dàng sắp xếp cho T
u
để từ chối trong trường hợp thứ hai là tốt,
cuối cùng T có thể chấp nhận. T
u
phát hiện điều này khi nó xử lý một 5-tuple trên băng 1
có một phần thứ ba là 0. Trong trường hợp này, sau khi T
u
đã thay đổi băng 2 một cách
thích hợp, nó xóa băng 1 sao chép băng 2 vào băng 1 và chấp nhận.
CHƯƠNG 2
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 11
Bài tập lớn – Môn: Lý thuyết tính toán
BÀI TẬP ỨNG DỤNG
Yêu cầu: Sử dụng kỹ thuật dịch chuyển các địa chỉ thanh ghi của RASP trong bài giảng

Bài tập lớn – Môn: Lý thuyết tính toán
Chương trình RASP xuất phát P Sau khi dịch chuyển thành P’
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 13
Bài tập lớn – Môn: Lý thuyết tính toán
Nhãn Lệnh Giải thích Lệnh Giải thích
2
READ R
27
← a READ
3
27 37
4
READ R
28
← b READ
5
28 38
6
LOAD A: ACC←<R
27
> LOAD A:
7
27 37
8
STORE: R
26
← <ACC> STORE:
9
26 36
10

20
ADD I:
ACC← <ACC>+
<<R
26
>>
STORE
21
26 1
22
WRITE In ra <ACC>
LOAD
23
0
36
24
HALT Dừng
ADD A:
p 25
0
10
P+1 26
27/28 Nội dung 27 hoặc 28
STORE
27
a Chứa giá trị a
31
q 28
b Chứa giá trị b
LOAD

MacGraw-Hill Companies, Inc., 1997.
Nhóm 11 - Lớp: Khoa học máy tính – Khóa 12 16