Tiểu luận Lý thuyết tính toán
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TIỂU LUẬN MÔN HỌC
LÝ THUYẾT TÍNH TOÁN
ĐỀ TÀI:
8.2. THE TURING MACHINE
Giảng viên hướng dẫn : PGS.TS. Phan Huy Khánh
Nhóm học viên: Nguyễn Nương Quỳnh
Lê Nam Trung
Nguyễn Duy Linh
Hoàng Đình Tuyền
Lớp: Khoa học Máy tính - K24 Quảng Bình
Khóa: 2011-2013
Quảng Bình, tháng 12 năm 2012
MỤC LỤC
Nhóm 3 Trang 1
Tiểu luận Lý thuyết tính toán
1
Nhóm học viên: Nguyễn Nương Quỳnh 1
Lớp: Khoa học Máy tính - K24 Quảng Bình 1
Nhóm 3 Trang 2
Tiểu luận Lý thuyết tính toán
8.2 Máy Turing
Mục đích của lý thuyết của các vấn đề không giải được là không chỉ thiết
lập sự tồn tại các vấn đề như vậy - một ý tưởng trí tuệ thú vị của riêng nó – mà
còn để cung cấp hướng dẫn cho các lập trình viên về những gì họ có thể hay
không thể thực hiện thông qua lập trình. Lý thuyết này cũng có tác động tích cực
khi ta thảo luận, như chúng ta quy định trong chương 10, các vấn đề mặc dù giải
quyết được, vẫn cần nhiều thời gian để giải quyết chúng. Những vấn đề này,
được gọi là "vấn đề nan giải", có xu hướng trình bày khó khăn hơn cho các lập

giản liên quan đến hai danh sách các chuỗi, là không giải quyết được, và vấn đề
này làm cho nó dễ dàng để hiển thị câu hỏi về ngữ pháp, chẳng hạn như sự mơ
hồ, là không giải quyết được. tương tự như vậy, khi chúng tôi giới thiệu các vấn
đề khó, chúng ta sẽ thấy rằng câu hỏi nào đó, dường như có ít để làm với tính
toán (ví dụ, khả năng đáp ứng các công thức boolean), là khó chữa.
8.2.1 Các Quest để quyết định tất cả 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 liệu đã có thể tìm thấy một
thuật toán để xác định sự thật hay dối trá của bất kỳ mệnh đề toán học. Đặc biệt,
ông hỏi nếu có một cách để xác định xem bất kỳ công thức trong tính toán vị
đầu tiên để áp dụng cho số nguyên, là sự thật. Kể từ khi các tính toán vị đầu tiên
để tính toán các số nguyên là đủ mạnh để thể hiện báo cáo như "ngữ pháp này là
mơ hồ", hay "Chương trình này in chào, thế giới", có phải Hilbert đã thành công,
những vấn đề này sẽ có các thuật toán mà chúng ta biết không tồn tại.
Tuy nhiên, vào năm 1931, K. Gödel 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 tính toán vị áp dụng cho số nguyên, trong
đó khẳng định rằng công thức đó có thể được chứng minh không phải và cũng
không bác bỏ trong các tính toán. Gödel kỹ thuật tương tự như việc xây dựng
các chương trình mâu thuẫn sefl-H2 trong phần 8.1.2, nhưng giao dịch với các
chức năng trên các số nguyên, chứ không phải với các chương trình C.
Các tính toán vị không phải là khái niệm duy nhất mà các nhà toán học đã
có "bất kỳ tính toán có thể". Trong thực tế tính toán vị, khai báo chứ không phải
là tính toán, phải cạnh tranh với một loạt các chỉ số, bao gồm cả "một phần các
Nhóm 3 Trang 4
Tiểu luận Lý thuyết tính toán
hàm đệ quy", thay vì một ký hiệu giống như ngôn ngữ lập trình, và các ký hiệu
tương tự khác. Năm 1936, sáng Turing đề xuất các máy Turing là một mô hình
"bất kỳ tính toán có thể". Mô hình này giống như máy tính, chứ không phải là
chương trình như thế, mặc dù điện tử đúng , hoặc thậm chí máy tính điện tử là
của những năm trong tương lai (Turing đã tự mình tham gia trong việc xây dựng
của máy như vậy trong Thế chiến thứ II).

trống.
Có một đầu băng luôn là vị trí tại một trong những ô của băng. Máy Turing
được cho là được quét ô đó. Ban đầu, đầu băng là các ô ngoài cùng bên trái chứa
các đầu vào.
Một di chuyển của máy Turing là một chức năng của trạng thái kiểm soát
hữu hạn và biểu tượng băng quét. Trong một động thái, máy Turing sẽ:
1. Thay đổi trạng thái. Trạng thái tiếp theo tùy chọn có thể giống như trạng
thái hiện tại.
2. Viết một biểu tượng băng trong các ô được quét. Biểu tượng băng này
thay thế bất cứ biểu tượng từng có trong ô đó. Tùy chọn, biểu tượng được viết
vào có thể là giống như biểu tượng hiện đang có.
3. Di chuyển đầu băng sang trái hoặc phải. Trong hình thức của chúng ta,
chúng ta yêu cầu di chuyển, và không cho phép đầu băng vẫn đứng yên. Hạn chế
này không hạn chế những gì một máy Turing có thể tính toán, từ bất kỳ trình tự
di chuyển với một đầu băng cố định có thể ngưng tụ, cùng với sự di chuyển của
đầu băng tiếp theo, vào một thay đổi trạng thái duy nhất, một biểu tượng băng
mới, và di chuyển sang trái hoặc phải.
Các ký hiệu chính thức chúng ta sẽ sử dụng cho một máy Turing (TM) là
tương tự như được sử dụng cho automat hữu hạn hoặc PDA. Chúng tôi mô tả
một TM bởi các 7 thành phần.
M = (Q, Σ, Г, δ, q
0
, B, F)
Có các thành phần có ý nghĩa sau đây:
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.
Г: tập hợp đầy đủ các biểu tượng băng;
Σ: luôn luôn là một tập hợp con của Г
δ: chức năng chuyển đổi. Những lập luận của δ (q, X) là một trạng thái q và
một băng biểu tượng X. Giá trị của δ(q, X), nếu nó được định nghĩa, là một bộ

biệt, khi đầu đọc đang quét một trong những khoảng trắng hàng đầu hoặc cuối,
một số hữu hạn các khoảng trắng từ bên trái hoặc bên phải của các ký hiệu
không phải khoảng trắng trên băng cũng phải được bao gồm trong các ID.
Nhóm 3 Trang 7
Tiểu luận Lý thuyết tính toán
Ngoài việc mô tả băng, chúng ta phải mô tả sự kiểm soát hữu hạn và vị trí
đầu đọc băng. Để làm như vậy, chúng ta nhúng các trạng thái trong băng, và đặt
nó ngay bên trái của các ô đã được quét. Để phân biệt với chuỗi băng cộng với
trạng thái, chúng ta phải đảm bảo rằng chúng ta không sử dụng như là một biểu
tượng trạng thái bất kỳ đó cũng là một biểu tượng băng. Tuy nhiên, nó rất dễ
dàng để thay đổi tên của các trạng thái để không có gì chung với các ký hiệu
băng, từ khi hoạt động của máy Turing không phụ thuộc vào tên gọi các trạng
thái. Do đó, chúng ta sẽ sử dụng chuỗi X
1
X
2
X
i-1
qX
i
X
i +1
X
n
để mô tả cho một
ID, trong đó:
1. q là trạng thái của máy Turing.
2. Đầu đọc băng quét qua ký hiệu thứ i từ trái sang.
3. X
1

) = (p,Y,L) tức là bước dịch chuyển tiếp theo là sang trái.
Thì :
X
1
X
2
…X
i-1
q X
i
X
i+1
…X
n
├
M
X
1
X
2
…X
i-2
p X
i-1
Y X
i+1
…X
n
Chú ý động thái này phản ánh sự thay đổi trạng thái p như thế nào và thực
tế rằng người đầu đọc băng được đặt tại vị trí ô i-1. Có hai trường hợp ngoại lệ

n
├
M
X
1
X
2
…X
n-2
p X
n-1
Bây giờ, cho rằng δ(q, X
i
) = (p,Y,R) ; tức là bước dịch chuyển tiếp theo là
sang phải. Thì:
X
1
X
2
…X
i-1
q X
i
X
i+1
…X
n
├
M
X

Nếu i = 1 và Y=B, thì ký hiệu B ghi đè lên X
1
tham gia vào chuỗi vô hạn
các khoảng trắng trước đó và không xuất hiện trong ID tiếp theo. Do đó:
q X
1
X
2
…X
n
├
M
p X
2
…X
n
Ví dụ 8.2: Chúng ta sẽ thiết kế một máy Turing và xem cách nó hoạt động
trên một đầu vào điển hình. Máy Turing sẽ chấp nhận ngôn ngữ {0
n
1
n
| n≥ 1}.
Ban đầu, nó được cung cấp một chuỗi hữu hạn 0 và 1 trên băng, trước và sau bởi
các khoảng trắng đến vô cùng. Luân phiên, TM sẽ thay mỗi ký tự 0 bởi X và mỗi
ký tự 1 bởi Y, cho đến khi tất cả các ký tự 0 và 1 đều được thay thế.
Chi tiết hơn, bắt đầu từ phía bên trái nhất của dãy dữ liệu vào, nó liên tục
thay đổi mỗi ký tự 0 bởi X và di chuyển về bên phải qua bất kỳ ký tự 0 và Y nào
được tìm thấy, cho đến khi nó tìm thấy ký tự 1. Thay 1 bởi Y , và chuyển sang
trái, qua bất kỳ ký tự Y và 0, đến khi tìm thấy ký tự X. Lúc đó, nó tìm kiếm ký tự
0 ngay phía bên phải, và nếu tìm thấy một ký tự, thay nó bởi X và lặp lại tiến

được thay thế bởi Y, một số ký tự 1 chưa được thay thế bởi Y. Có thể có hoặc
không có một số ký tự 0 và 1 theo sau.
Bảng 8.9: TM chấp nhận {0
n
1
n
| n≥ 1}.
Khởi động bởi trạng thái q
0
, M cũng nhập từ trạng thái q
0
mỗi khi nó quay
về ký tự 0 còn lại bên trái nhất. Nếu M đang ở trạng thái q
0
và quét qua ký tự 0,
theo quy tắc góc trên bên trái trong hình 8.9 thì nó sẽ dịch chuyển đến trạng thái
q
1
, thay 0 bởi X, và chuyển sang phải. Mỗi lần ở trạng thái q
1
, M chuyển sang
phải qua tất cả các ký tự 0 và Y được tìm thấy trên băng, lưu lại trạng thái q
1
.
Nếu M tìm thấy ký tự X hoặc B, nó lỗi. Tuy nhiên, nếu M thấy 1 ở trạng thái q
1
,
nó thay 1 bởi Y, chuyển sang trạng thái q
2
, và bắt đầu dịch chuyển sang trái.

0
, quét ký tự 0 đầu tiên, tức là ID khởi động của M là
q
0
0011. Toàn bộ các bước di chuyển của M là:
q
0
0011 ├ Xq
1
011 ├ X0q
1
11 ├ Xq
2
0Y1 ├q
2
X0Y1 ├ Xq
0
0Y1 ├ XXq
1
Y1 ├
XXYq
1
1├ XXq
2
YY ├ Xq
2
Xyy ├ XXq
0
YY ├ XXYq
3

1
0 M quét ký tự 0 cuối cùng lần đầu tiên. M phải dịch chuyển sang phải,
dừng lại ở trạng thái q
1
, và có ID là XXY0q
1
B. Tuy nhiên, ở trạng thái q
1
M
không di chuyển trên băng ký hiệu B; do đó M lỗi và không chấp nhận dữ liệu
vào.
8.2.4. Sơ đồ quá trình chuyển đổi cho máy Turing
Chúng ta có thể đại diện cho các quá trình chuyển đổi hình ảnh của một
máy Turing, nhiều như chúng ta đã làm cho các PDA. Sơ đồ chuyển đổi bao
gồm một tập các nút tương ứng với các trạng thái của máy Turing. Một vòng
cung từ trạng thái q đến trạng thái p được dán nhãn của một hoặc nhiều mục của
mẫu X / YD, trong đó X và Y là biểu tượng băng, và D là một hướng, hoặc L
hoặc R. Đó là, bất cứ khi nào δ (q, X) = (p, Y, D), chúng ta tìm thấy nhãn X/YD
trên vòng cung từ q để p. Tuy nhiên, trong sơ đồ của chúng ta, hướng D được
thể hiện bởi hình ảnh ← "trái" và → cho "phải".
Đối với các loại biểu đồ chuyển đổi, chúng ta đại diện cho trạng thái bắt
đầu bằng từ "Start" và một mũi tên vào trạng thái đó. Trạng thái chấp nhận được
chỉ định bởi các vòng tròn đôi. Như vậy, thông tin duy nhất về máy Turing
Nhóm 3 Trang 11
Tiểu luận Lý thuyết tính toán
không thể đọc trực tiếp từ biểu đồ là biểu tượng được sử dụng trống. Chúng ta sẽ
giả định rằng biểu tượng là B trừ khi chúng ta trạng thái khác.
Ví dụ 8.3: Hình 8.10 cho thấy sơ đồ chuyển tiếp cho máy Turing của ví dụ
8.2, có chức năng chuyển đổi đã được đưa ra trong hình. 8.9.
Ví dụ 8.4: Trong khi ngày nay chúng ta tìm thấy nó thuận tiện nhất để suy

một chỗ trống. Nó sau đó tìm kiếm bên phải, tìm kiếm một 1. Sau khi tìm thấy
một 1, nó tiếp tục sang phải, cho đến khi nó đến 0, mà nó thay thế bởi một 1. M
sau đó trở về trái, tìm kiếm số 0 tận cùng bên trái, nó xác định khi lần đầu tiên
gặp một chỗ trống và sau đó di chuyển một ô sang bên phải.
Lặp đi kết thúc nếu một trong hai trường hợp:
1. Tìm kiếm bên phải với một 0, M gặp một chỗ trống. Sau đó, các n của ký
tự 0 trong 0
m
10
n
tất cả được thay đổi thành 1, và n +1 của m ký tự 0 đã được
thay đổi thành B. M thay thế các n + 1 ký tự 1 thành một ký tự 0 và n ký tự B,
để lại m-n ký tự 0 trên băng. Kể từ khi m> = n trong trường hợp này, m-n = m_
+ n.
2. Bắt đầu chu kỳ, M không thể tìm thấy một ký tự 0 để thay thế thành một
chỗ trống, bởi vì n ký hiệu 0đầu tiên đã được thay đổi thành B. Sau đó, n> = m,
do đó, m-+ n = 0. M thay thế tất cả các ký tự 1 và 0 còn lại thành B và kết thức
với một băng hoàng toàn trống.
Hình 8.11 đưa ra các quy tắc của chức năng chuyển đổi δ, và chúng ta cũng
đã đại diện δ như một sơ đồ chuyển đổi trong hình 8.12. Sau đây là một bản tóm
tắt vai trò của từng trạng thái trong 7 trạng thái:
q
0
: Trạng thái này bắt đầu chu kỳ, và cũng có thể phá vỡ chu kỳ khi thích
hợp. Nếu M đang quét một ký tự 0, chu kỳ phải lặp lại. 0 được thay thế bằng B,
đầu đọc di chuyển sang bên phải, và trạng thái q1 được nhập. Mặt khác, nếu M
đang quét ký tự 1, sau đó tất cả các trận đấu (matches) có thể có giữa hai nhóm
của ký tự 0 trên băng đã được thực hiện, và M đi đến trạng thái q5 để làm trống
băng.
Nhóm 3 Trang 13

, bắt đầu
chu kỳ một lần nữa.
Nhóm 3 Trang 14
Tiểu luận Lý thuyết tính toán
q
4
: Ở đây, trừ hoàn tất, nhưng chưa từng có một ký tự 0 trong khối đầu tiên
đã được thay đổi không chính xác thành B. M do đó di chuyển trái, thay đổi 1
thành B, cho đến khi nó gặp một B trên băng. Nó thay đổi mà B trở về 0, và vào
trạng thái q
6
, trong đó M tạm dừng.
q
5
: Trạng thái q
5
được nhập vào từ trạng thái q
0
khi nó được tìm thấy rằng
tất cả các ký tự 0 trong khối đầu tiên đã được thay đổi thành B. Trong 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 là 0. M thay
đổi tất cả 0 và 1 còn lại thành B và đi vào trạng thái q6.
q
6
: 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 xử lý con của một số chức
năng phức tạp hơn, sau đó q
6
sẽ bắt đầu bước tiếp theo của tính toán lớn hơn đó.
8.2.5. Ngôn ngữ của máy Turing

3. Các chữ thường gần cuối của bảng chữ cái là chuỗi các ký hiệu đầu vào.
4. Chữ Hy Lạp là chuỗi các ký hiệu băng.
5. Các chữ cái như q, p và chữ gần đó là những trạng thái.
8.2.6 Máy Turing và Tạm dừng
Còn có một khái niệm khác về "chấp nhận" thường được sử dụng cho máy
Turing: chấp nhận do tạm ngừng. Chúng tôi nói một TM tạm dừng nếu nó đi vào
một trạng thái q, quét một biểu tượng băng X, và không có di chuyển trong tình
huống này, tức là, δ(q, X) là không xác định.
Ví dụ 8.5: Các máy Turing M Ví dụ 8.4 không được thiết kế để chấp nhận
một ngôn ngữ mà w xem nó như là tính toán một chức năng số học. Lưu ý, tuy
nhiên, rằng M tạm dừng tất cả các chuỗi của 0 và 1, kể từ khi không có đồng hồ
đo những gì chuỗi M tìm thấy trên băng của nó, nó cuối cùng sẽ hủy bỏ nhóm 2
của số 0, nếu nó có thể tìm thấy một nhóm nhạc, so với nhóm 1 của nó = 0 , và
do đó phải đạt trạng thái q
6
và dừng lại.
Chúng ta luôn luôn có thể giả định rằng một máy Turing tạm dừng nếu nó
chấp nhận. Đó là, mà không thay đổi ngôn ngữ được chấp nhận, chúng ta có thể
làm cho δ (q, X) không xác định bất cứ khi nào q là một trạng thái chấp nhận.
Nói chung, không có nếu không nói như vậy:
* Chúng ta cho rằng một TM luôn luôn tạm dừng khi nó là một trong trạng
thái chấp nhận.
Thật không may, nó không phải lúc nào cũng có thể yêu cầu rằng một TM
tạm dừng thậm chí nếu nó không chấp nhận. Những ngôn ngữ với các máy
Turing mà làm dừng cuối cùng, bất kể chúng có chấp nhận hay không, được gọi
là đệ quy, và chúng tôi sẽ xem xét các thuộc tính quan trọng của chúng bắt đầu
Nhóm 3 Trang 16
Tiểu luận Lý thuyết tính toán
trong mục 9.2.1. Máy Turing mà luôn luôn dừng, bất kể chúng có chấp nhận hay
không, là một mô hình tốt của một "thuật toán". Nếu một thuật toán để giải

2
0Y11├ Xq
2
00Y11
├ q
2
X00Y11├ Xq
0
00Y11├ XXq
1
0Y11├ XX0q
1
Y11├ XX0Yq
1
11
├ XX0q
2
YY1├ XXq
2
0YY1├ Xq
2
X0YY1├ XXq
0
0YY1├ XXXq
1
YY1
├ XXXYq
1
Y1├ XXXYYq
1

0
0Y11
├ XXq
1
Y11├ XXYq
1
11├ XXq
2
YY1├ Xq
2
XYY1├ XXq
0
YY1
├ XXYq
3
Y1├ XXYYq
3
1
Nhóm 3 Trang 17
Tiểu luận Lý thuyết tính toán
Tiếp theo không có luật để áp dụng do đó ngôn ngữ không được đoán nhận.
! Bài tập 8.2.2: Thiết kế máy Turing cho các ngôn ngữ sau:
*a) Các thiết lập các chuỗi với một số lượng bằng 0 và 1.
b) {a
n
b
n
c
n
| n> = 1}

0
, B, {q
f
})
Chính thức nhưng mô tả rõ ràng ngôn ngữ L(M) nếu δ bao gồm các bộ quy
tắc sau đây:
*a) δ (q
0
, 0) = (q
1
, 1, R), δ (q
1
, 1) = (q
0
, 0, R); δ (q
1
, B) = (q
f
, B, R).
L(M) = 01.
b) δ (q
0
, 0) = (q
0
, B, R), δ (q
0
, 1) = (q
1
, B, R); δ (q
1