Tiểu luận môn học Lý Thuyết Tính Toán
MỤC LỤC
MỤC LỤC 1
LỜI MỞ ĐẦU 2
PHẦN 1. LÝ THUYẾT MÁY TURING 3
8.2.1 NHIỆM VỤ GIẢI QUYẾT CÁC CÂU HỎI TOÁN HỌC 4
8.2.2 KÝ PHÁP CHO MÁY TURING 5
8.2.3 MÔ TẢ TỨC THỜI CHO MÁY TURING 7
8.2.4 NHỮNG SƠ ĐỒ CHUYỂN TIẾP CHO MÁY TURING 12
8.2.5 NGÔN NGỮ CỦA MÁY TURING 16
8.2.6 MÁY TURING VÀ TRẠNG THÁI DỪNG 17
PHẦN 2. BÀI TẬP 18
2.1. BÀI 8.2.1 18
2.2. BÀI 8.2.3 21
TÀI LIỆU THAM KHẢO 24
Lớp KHMT Khoá 26 Trang 1
Tiểu luận môn học Lý Thuyết Tính Toán
LỜI MỞ ĐẦU
Nhóm chúng em thực hiện việc nghiên cứu tài liệu “Introduction to
Automata Theory, Languages, and Computation”, phần 8.2 (tr. 316 – 328).
Rất mong được sự đóng góp ý kiến của Thầy PGS. TS. Phan Huy Khánh.
Xin chân thành cảm ơn!
Lớp KHMT Khóa 26
Trần Thanh Liêm
Nguyễn Trọng Nguyên
Nguyễn Minh Quỳnh
Lớp KHMT Khoá 26 Trang 2
Tiểu luận môn học Lý Thuyết Tính Toán
PHẦN 1. LÝ THUYẾT MÁY TURING
Mục đích của các lý thuyết về các vấn đề trên (8.1) không chỉ để thể hiện sự
tồn tại của chúng - một ý tưởng thú vị về mặt trí tuệ theo đúng nghĩa của nó –mà

Sử dụng ký pháp máy Turing, chúng ta sẽ chứng minh bài toán không thể
quyết định được không liên quan đến lập trình. Một ví dụ, chúng ta sẽ thấy trong
phần 9.4, một câu hỏi đơn giản liên quan đến hai danh sách các chuỗi, là không
thể quyết định được, và vấn đề này làm cho nó dễ dàng đưa ra câu hỏi về ngữ
pháp, chẳng hạn như sự mơ hồ, là không thể quyết định được. Tương tự, khi
chúng tôi giới thiệu các vấn đề khó, chúng ta sẽ thấy rằng một số câu hỏi, dường
như khó áp dụng các phương pháp tính toán (ví dụ như công thức của boolean).
8.2.1 Nhiệm vụ giải quyết các câu hỏi toán học
Bước vào thế kỷ 20, nhà toán học D. Hilbert đã hỏi rằng liệu có thể tìm thấy
một thuật toán để xác định sự chính xác hay là sai lầm của bất kỳ lời tuyên bố
toán học nào. Đặc biệt, ông hỏi có cách nào để xác định xem một công thức bất
kỳ là đúng. Kể từ khi các phép tính toán các số nguyên đủ mạnh mẽ để thể hiện
phát biểu như "ngữ pháp này là mơ hồ," hoặc "chương trình này in hello world"
thì Hilbert đã thành công, có những vấn đề sẽ có thuật toán mà đến bây giờ
chúng ta biết không tồn tại.
Tuy nhiên, vào năm 1931, K. Godel công bố định lý bất toàn nổi tiếng của
ông. Ông đã xây dựng một công thức trong tính toán áp dụng cho số nguyên,
khẳng định rằng công thức đó có thể không cần được chứng minh và cũng không
bác bỏ trong các tính toán. Kỹ thuật của Godel tương tự như việc xây dựng các
chương trình mâu thuẫn H2 tại mục 8.1.2, nhưng với các chức năng trên số
nguyên, chứ không phải với các chương trình C.
Tính toán vị từ không chỉ là khái niệm chỉ các lý thuyết liên quan đến tính
toán. Trong tính toán vị từ thực tế, các thành phần được khai báo chứ không phải
tính toán, phải hoàn tất với một loạt các ký hiệu, bao gồm cả chức năng đệ quy
một phần, giống một ký hiệu hơn là ngôn ngữ lập trình và những ký hiệu tương
tự khác. Năm 1936, A. M. Turing đề xuất các máy Turing như là một mô hình có
Lớp KHMT Khoá 26 Trang 4
Tiểu luận môn học Lý Thuyết Tính Toán
thể tính toán bất kỳ. Mô hình này giống như máy tính hơn là chương trình, mặc
dù điện tử, hoặc thậm chí máy tính điện tử thì nhiều năm sau đó mới được phát

2. Viết một biểu tượng băng trong ô quét. Biểu tượng băng này thay thế
biểu tượng đã có trong ô. Tuy nhiên, biểu tượng có thể giống như biểu
tượng hiện có.
3. Di chuyển đầu băng sang trái hoặc phải. Sau mỗi trạng thái, chúng ta yêu
cầu một di chuyển, và không cho phép đầu đọc đứng yên một chỗ. Hạn
chế này không không hạn chế những gì một máy Turing có thể tính toán.
Ký hiệu chính thức mà chúng ta sẽ sử dụng cho một máy Turing (TM) là
tương tự như sử dụng automát hữu hạn hoặc PDA. Chúng ta mô tả một TM bởi
tuple-7:
M = (Q, ∑, Γ, δ, q0, B, F)
Các thành phần có ý nghĩa như sau:
Q: tập hữu hạn của các trạng thái kiểm soát hữu hạn.
∑: tập hợp hữu hạn các ký hiệu đầu vào.
Γ: bộ hoàn chỉnh các biểu tượng băng; E luôn là một tập hợp con của Γ.
δ: Hàm chuyển đổi. Những tham số của hàm δ(q, X) là một trạng thái q và
một ký hiệu băng X. Giá trị của hàm δ(q, X), nếu nó được định nghĩa, là một bộ
ba (p, Y, D), trong đó:
1. p là trạng thái tiếp theo, trong Q.
Lớp KHMT Khoá 26 Trang 6
Tiểu luận môn học Lý Thuyết Tính Toán
2. Y là biểu tượng, trong Γ, được viết trong ô được quét, thay thế
biểu tượng đã có.
3. D là một hướng, hoặc L hoặc R, là viết tắt của chữ "left" hoặc
"right", và cho chúng ta biết hướng di chuyển đầu đọc/ghi.
q
0
: Trạng thái bắt đầu, là một phần tử của Q, trong đó kiểm soát hữu hạn
được tìm thấy ban đầu.
B: Biểu tượng rỗng. Biểu tượng này là trong Γ nhưng không phải trong ∑,
nghĩa là, nó không phải là một biểu tượng đầu vào. Biểu tượng rỗng xuất hiện

X
2
… X
i-1q
X
i
X
i+1
X
n
để biểu diễn cho một ID, trong đó:
1. q là trạng thái của máy Turing.
2. Đầu đọc băng quét các ký hiệu thứ i từ bên trái.
3. X
1
X
2
… X
n
là một phần của băng giữa tận cùng bên trái và bên phải
không trống. Như một ngoại lệ, nếu đầu đọc đến bên trái của tận cùng
bên trái không trống hoặc đến bên phải của tận cùng bên phải không
trống, thì một số tiền tố hoặc hậu tố của X
1
X
2
X
n
sẽ được để trống, và
i sẽ là 1 hoặc n, tương ứng.

1. Nếu i = n thì ô thứ (i + 1) giữ một khoảng trống, và ô này không phải là
một phần của ID trước. Vì vậy, thay vào chúng ta có:
2. Nếu i = 1 và Y = B, ký hiệu B viết đè lên X1 tham gia vào chuỗi vô hạn
các khoảng trống đầu hàng và không xuất hiện trong các ID tiếp theo. Vì vậy:
Ví dụ 8.2: Chúng ta thiết kế một máy Turing và xem nó hoạt động như thế
nào trên một đầu vào chuẩn. Các TM chúng ta xây dựng sẽ chấp nhận ngôn ngữ
{0
n
1
n
|N≥1}. Ban đầu, nó cho 1 chuỗi hữu hạn các số 0 và l trên băng của nó,
trước và sau là vô hạn của khoảng trống. Cách khác, TM sẽ thay đổi từ số 0
thành X và sau đó thay đổi số 1 thành Y, cho đến khi tất cả các số 0 và l đã được
thay đổi phù hợp.
Chi tiết hơn, bắt đầu từ đầu bên trái của đầu vào, nó liên tục thay đổi từ số 0
thành X và di chuyển sang phải qua bất cứ khi nó nhìn thấy số 0 và Y, cho đến
khi nó đến số 1. Nó thay đổi số 1 thành Y và di chuyển sang trái, qua Y và số 0,
cho đến khi nó tìm thấy X. Vào thời điểm đó, nó lập tức cho số 0 ngay bên phải,
Lớp KHMT Khoá 26 Trang 9
Tiểu luận môn học Lý Thuyết Tính Toán
và nếu tìm thấy số 1, nó thay đổi thành X và lặp đi lặp lại các quy trình, thay đổi
số 1 thành Y.
Nếu đầu vào không trống không thuộc 0*1*, thì TM cuối cùng sẽ không có
một sự di chuyển tiếp theo và sẽ ngừng hoạt động mà không có sự chấp nhận.
Tuy nhiên, nếu nó hoàn thành việc thay đổi tất cả các số 0 thành các X trên cùng
một vòng, thay đổi số 1 cuối cùng thành Y, thì nó đã tìm thấy đầu vào của mẫu
hình thức 0
n
l
n

đã được thay đổi thành Y, thì đầu vào là một dạng của 0
n
l
n
, và M phải chấp nhận.
Như vậy, M đi đến trạng thái q3, và bắt đầu di chuyển sang bên phải, qua các Y.
Nếu biểu tượng khác so với Y thì M nhìn thấy đầu tiên là một khoảng trống, thì
thực sự đã có một số lượng của số 0 bằng số lượng của l, do đó, M đi vào trạng
thái q4 và chấp nhận. Mặt khác, nếu M gặp số khác 1 thì có quá nhiều số 1, khi
đó M ngừng hoạt động mà không chấp nhận. Nếu nó gặp một số 0 thì đầu vào
của các hình thức sai, và M cũng ngừng hoạt động.
Đây là một ví dụ của một tính toán chấp nhận bởi M. Đầu vào của nó là
0011. Ban đầu, M là trạng thái qo, quét số 0 đầu tiên, nghĩa là, ID ban đầu của M
là q
0
0011. Trình tự toàn bộ di chuyển của M là:
Ví dụ khác, hãy xem xét M nhập vào 0010, đó không phải là ngôn ngữ
được chấp nhận.
Các hành vi của M trên 0010 giống như các hành vi trên 0011, cho đến khi
trong ID XXYq
1
0 M quét số 0 cuối cùng cho lần đầu tiên. M phải di chuyển sang
phải, ở trong trạng thái q1, đưa đến ID XXY0q
1
B. Tuy nhiên, ở trạng thái q
1
M
Lớp KHMT Khoá 26 Trang 11
Tiểu luận môn học Lý Thuyết Tính Toán
không có di chuyển trên băng biểu tượng B, do đó M ngừng hoạt động và không

Lưu ý rằng, kể từ khi TM này không được sử dụng để chấp nhận đầu vào,
chúng ta đã bỏ qua thành phần thứ bảy, là các thiết lập của các trạng thái đang
chấp nhận. M sẽ bắt đầu với một băng gồm 0
m
10
n
bao quanh bởi khoảng trống. M
tạm dừng với 0
m n
trên băng của nó, bao quanh bởi các khoảng trống.
Hình 8.10: sơ đồ chuyển tiếp cho một TM chấp nhận chuỗi hình thức 0
n
1
n
M lặp lại việc tìm kiếm số 0 còn lại tận cùng bên trái của nó và thay thế
bằng một khoảng trắng. Sau đó tìm kiếm số 1 ở bên phải. Sau khi tìm thấy một
số 1, nó vẫn tiếp tục tìm bên phải cho đến khi nó đến số 0 thì thay thế số 0 bởi
một số 1. M sau đó trở về bên trái, tìm kiếm số 0 tận cùng bên trái mà nó xác
định khi lần đầu tiên nó gặp một khoảng trống và sau đó di chuyển một ô đến bên
phải. Quá trình lặp kết thúc nếu thỏa mãn một trong hai trường hợp:
1. Tìm kiếm số 0 bên phải, M gặp một khoảng trống. Sau đó tất cả n số 0
trong 0
m
10
n
đều được thay đổi thành số 1, và n + 1 của m số 0 được thay đổi
thành B. M thay thế n+1 số 1 bằng một số 0 và n B, để lại m - n số 0 của băng.
Khi m ≥ n trong trường hợp này, m - n =m n.
Lớp KHMT Khoá 26 Trang 13
Tiểu luận môn học Lý Thuyết Tính Toán

q5: Trạng thái q5 được chuyển từ q0 khi nó tìm thấy tất cả các số 0 trong
khối đầu tiên đã được thay đổi thành B. Trường hợp này được mô tả trong (2) ở
trên, kết quả của phép trừ thích hợp (proper subtaction) là 0. M thay đổi tất cả
các số 0 và các số 1 còn lại thành B và đi vào trạng thái q6.
q6: Mục đích duy nhất của trạng thái này là cho phép M dừng khi nó đã
hoàn tất nhiệm vụ của mình. Nếu phép trừ là một chương trình con của một số
hàm phức tạp hơn thì q6 sẽ bắt đầu bước tiếp theo của tính toán lớn hơn.
Hình 8.11: Một máy Turing tính toán chức năng proper-subtraction
Hình 8.12: Sơ đồ chuyển đổi cho TM của ví dụ 8.4
Lớp KHMT Khoá 26 Trang 15
Tiểu luận môn học Lý Thuyết Tính Toán
8.2.5 Ngôn ngữ của máy Turing
Chúng ta đã thấy cách mà máy Turing chấp nhận một ngôn ngữ một cách
trực quan. Chuỗi đầu vào được đặt trên một băng từ và đầu đọc bắt đầu từ ký tự
đầu tiên tận cùng bên trái. Nếu máy Turing cuối cùng chấp nhận trạng thái thì
đầu vào được chấp nhận, ngược lại thì không.
Thông thường, đặt M=(Q,
Σ
,
Γ
,
δ
, q
0
, B, F) vào một máy Turing. Thiết lập
L(M)
1
là tập hợp của chuỗi w trong Σ
*
chẳng hạn như q

3. Các ký tự thường gần cuối bảng chữ cái là các chuỗi của biểu tượng đầu
vào.
1
Tập hợp các chuỗi trong Γ* là nguyên nhân đưa TM M đi vào trạng thái kết thúc khi đã thực hiện việc
thay thế từ bên trái các ký hiệu trên băng của M với trạng thái bắt đầu q0
Lớp KHMT Khoá 26 Trang 16
*
Tiểu luận môn học Lý Thuyết Tính Toán
4. Các ký tự Hy Lạp là chuỗi của biểu tượng băng.
5. Các ký tự như q, p và các ký tự gần đó dùng để chỉ trạng thái.
8.2.6 Máy Turing và trạng thái dừng
Còn có một khái niệm “chấp nhận” thường được sử dụng cho máy Turing:
chấp nhận bằng cách dừng. Ta nói một máy Turing “dừng” nếu nó vào trạng thái
q, quét biểu tượng băng X và không có một sự dịch chuyển trong điều kiện này.
Ví dụ,
δ
(q, X) không được định nghĩa.
Ví dụ 8.5: Một máy Turing M trong ví dụ 8.4 không được thiết kế để chấp
nhận một ngôn ngữ; thay vì vậy ta xem nó như là như máy tính để tính các hàm
số học. Tuy nhiên máy M dừng với tất cả chuỗi của 0 và 1, vì M không tìm thấy
chuỗi nào trên băng.
Chúng ta luôn luôn giả định một máy Turing ở trạng thái dừng nếu nó chấp
nhận. Do đó, không có sự thay đổi đối với một ngôn ngữ được chấp nhận. Chúng
ta có thể tạo
δ
(q, X) không xác định bất cứ khi nào q là một trạng thái được chấp
nhận. Nói chung:
• Chúng tôi giả định rằng một máy Turing luôn luôn tạm dừng khi nó
trong một trạng thái được chấp nhận.
Không may, không phải lúc nào cũng có thể yêu cầu rằng một máy Turing

1
, Y, R) -
q
2
(q
2
, 0, L) - (q
0
, X, R) (q
2
, Y, L) -
q
3
- - - (q
3
, Y, R) (q
4
, B, R)
q
4
- - - - -
Máy Turing chấp nhận {0
n
1
n
| n ≥ 1}
Giải:
Ta mô tả một TM: M=(Q,
Σ
,

q
0
: Trạng thái bắt đầu, một phần tử của Q, trong sự điều khiển có giới
hạn được tìm thấy lúc đầu.
B: Ký hiệu rỗng. Ký hiệu này trong
Γ
nhưng không trong
Σ
; ví dụ, nó là
một ký hiệu đầu vào. Ký hiệu rỗng xuất hiện lần đầu trong tất cả nhưng số
hữu hạn của các ô lúc đầu giữ các ký hiệu đầu vào.
F: Tập của các trạng thái cuối hoặc trạng thái chấp nhận, một tập con của
Q.
Cho biểu đồ 8.9, TM M được mô tả cụ thể như sau:
M= ({q
0
,q
1
,q
2
,q
3
,q
4
),{0,1},{0,1,X,Y,B},
δ
,q
0
,B,{q
4

Vì vậy M đi đến trạng thái q3, và bắt đầu việc di chuyển sang phải, qua
các ô Y. Nếu ký hiệu đầu tiên khác với một Y mà M gặp là một ô rỗng, thì
dẫn đến có sự bằng nhau của các ô số 0 và các ô số 1, vì thế M đi đến
trạng thái q4 và chấp nhận. Theo cách khác, nếu M bắt gặp số 1 khác, thì
có quá nhiều ô số 1, vì thế M dừng mà không chấp nhận. Nếu nó bắt gặp
một số 0, thì đầu vào là trong hình thức sai và M cũng dừng.
Theo qui luật trên, với đầu vào là 000111, ID của máy Turing M được
trình bày như sau:
- Khởi tạo máy Turing M ở trạng thái q
0
- ID khởi tạo của M là: q
0
000111
- Toàn bộ dãy mô tả M là:
Lớp KHMT Khoá 26 Trang 20
q
0
q
1
q
2
q
3
q
4
Y / Y →
0 / 0 →
Y / Y ←
0 / 0 ←
1 / Y ←

11 XX0q
2
YY1
XXq
2
0YY1 Xq
2
X0YY1 XXq
0
0YY1 XXXq
1
YY1 XXXYq
1
Y1
XXXYYq
1
1 XXXq
2
YYY XXq
2
XYYY XXXq
0
YYY XXXYq
3
YY
XXXYYq
3
Y XXXYYYq
3
B XXXYYYBq

0→0/R
B→B/L
0→1/L
0→0/L
1→0/L
1→0/L
$→1/L
0→1/L
1→1/L
$→$/R
q
01
$→$/R
Tiểu luận môn học Lý Thuyết Tính Toán
Giải thích mục đích của mỗi trạng thái
- Trạng thái q
0
: Đọc $ ghi $, đưa đầu đọc sang phải ($ là ký tự đầu tiên
của chuỗi dữ liệu vào) và chuyển sang trạng thái q
1
- Trạng thái q
1
: Đưa đầu đọc đến vị trí cuối cùng của dữ liệu vào (cực
phải – rightmost) có nghĩ tùy thuộc vào dữ liệu vào mà
trạng thái đọc 1 ghi 1, đưa đầu đọc sang phải hoặc đọc
0 ghi 0, đưa đầu đọc sang phải được thực hiện một số
lần cho đến lúc gặp rỗng (B – Blank) thì đọc rỗng ghi
rỗng, đưa đầu đọc sang trái và chuyển sang trạng thái
q
2

$ ghi $, đưa đầu đọc sang trái và chuyển sang trạng
thái q
5
.
Lớp KHMT Khoá 26 Trang 22
Tiểu luận môn học Lý Thuyết Tính Toán
b/ Các dãy biến đổi liên tiếp của máy Turing đó khi xâu vào là $111
q
0
$111 $q
1
111 $1q
1
11 $11q
1
1 $111q
1
B $11q
2
1B $1q
4
10B
$q
4
100B Bq
4
$000B q
3
B1000B q
5