Bài giảng "Toán giải tích - Chương 7: Máy Turing" cung cấp cho người đọc các kiến thức: Mô hình TM, TM nhận dạng ngôn ngữ, TM tính toán hàm số nguyên, các kỹ thuật xây dựng TM. Mời các bạn cùng tham khảo nội dung chi tiết.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Toán giải tích - Chương 7: Máy Turing
- Chương 7: Máy Turing
(Turing Machine)
Nội dung:
• Mô hình TM
• TM nhận dạng ngôn ngữ
• TM tính toán hàm số nguyên
• Các kỹ thuật xây dựng TM
1
- Mô hình TM
Định nghĩa: TM là một hệ thống gồm 7 thành phần
M (Q, Σ, Γ, δ, q0, B, F)
● Q : tập hữu hạn các trạng thái
● Σ : bộ ký hiệu nhập
● Γ : tập hữu hạn các ký hiệu được viết trên băng
● δ : hàm chuyển Q x Γ → Q x Γ x {L, R, Ø}
● q : trạng thái khởi đầu
0
● B : ký hiệu dùng để chỉ khoảng trống trên băng
● F Q : tập các trạng thái kết thúc
Hình thái: α1qα2 với q là trạng thái hiện hành của TM, α1α2 là nội
dung của băng tính từ đầu băng cho đến ký hiệu khác Blank bên
phải nhất
2
- Phép chuyển
Định nghĩa: Đặt X1X2...Xi-1qXi...Xn là một hình thái (ID)
Giả sử : δ(q, Xi) = (p, Y, L)
• Nếu i - 1 = n thì Xi là B
• Nếu i = 1 thì không có ID kế tiếp (đầu đọc không được phép vượt qua cận trái
của băng.
• Nếu i > 1 ta viết:
X1X2...Xi-1qXi...Xn ⊢ X1X2...Xi-2pXi-1YXi+1...Xn
Tương tự : δ(q, Xi) = (p, Y, R)
X1X2...Xi-1qXi...Xn ⊢ X1X2...Xi-2Xi-1YpXi+1...Xn
Và với : δ(q, Xi) = (p, Y, Ø)
X1X2...Xi-1qXi...Xn ⊢ X1X2...Xi-2Xi-1pYXi+1...Xn
3
- TM nhận dạng ngôn ngữ
Định nghĩa: ngôn ngữ được chấp nhận bởi TM M là
L(M) = {w | w Γ* và q0w ⊢ α1pα2 với p F}
Ví dụ: thiết kế TM chấp nhận L = {0n1n | n > 0}
Đặt TM M(Q, Σ, Γ, δ, q0, B, F) với
Q = {q0, q1, q2, q3, q4}, Γ = {0, 1, X, Y, B}, F = {q4}
Xét chuỗi 0011 ta có: q00011 ⊢ Xq1011 ⊢ X0q111 ⊢ X q20Y1 ⊢ q2X0Y1 ⊢ X
q00Y1 ⊢ XXq1Y1 ⊢ XXY q11 ⊢ XX q2YY ⊢ X q2XYY ⊢ XX q0YY ⊢ XXYq3Y
⊢ XXYYq3 ⊢ XXYYq4
4
- TM nhận dạng ngôn ngữ
start q
(Y,Y,R) q (B,B,Ø) q
0 3 4
(X,X,R) (Y,Y,R)
(0,X,R)
(1,Y,L) q
q
1 2
(0,0,R) (0,0,L)
(Y,Y,R) (Y,Y,L)
5
- TM như là máy tính hàm số nguyên
Quy ước: một số nguyên trong TM được viết dưới dạng nhất phân
là một chuỗi số 0, cách nhau bởi 1 số 1.
000001001000B = 5, 2, 3
Ví dụ: thiết kế TM tính toán phép trừ riêng
• Nếu m < n thì m \ n = 0
• Ngược lại thì m \ n = m – n
• Input: 0m10nB Output: 0m\nB
Đặt TM M(Q, Σ, Γ, δ, q0, B, F) với
• Q = {q0, q1, q2, q3, q4, q5, q6}, Γ = {0, 1, B}, F = {q6}
6
- TM như là máy tính hàm số nguyên
Xét chuỗi nhập 0010 (2-1)ta có: q00010 ⊢ B q1010 ⊢ B0q110 ⊢ B01q20 ⊢
B0q311 ⊢ Bq3011 ⊢ q3B011 ⊢ Bq0011 ⊢ BBq111 ⊢ BB1q21 ⊢ BB11q2 ⊢
BB1q41 ⊢ BBq41 ⊢ Bq4 ⊢ Bq60
Xét chuỗi nhập 0100 (1-2) ta có: q00100 ⊢ Bq1100 ⊢ B1q200 ⊢ Bq3110 ⊢
q3B110 ⊢ Bq0110 ⊢ BBq510 ⊢ BBBq50 ⊢ BBBBq5 ⊢ BBBBq6
q (B,B,Ø) q
5 6
(1,B,R)
(0,B,R) (B,0,Ø)
(1,B,R)
start q (0,B,R) q (1,B,L)
q
0 1 4 (0,0,L)
(B,B,R) (0,0,R) (B,B,L)
(1,1,R)
q q
(0,0,L) 3 (0,1,L) 2
(1,1,R)
(1,1,L) 7
- Kỹ thuật lưu trữ trong bộ điều khiển
Ví dụ: thiết kế TM kiểm tra ký tự đầu tiên của một chuỗi không xuất
hiện ở bất kỳ vị trí nào khác trong chuỗi.
Xây dựng: TM M(Q, {0, 1}, {0, 1, B}, δ, [q0, B], B, F)
trong đó các trạng thái thuộc Q là một cặp {q0, q1} x {0, 1, B}
F = {[q1, B]}
Phép chuyển:
δ([q0, B], 0) = ([q1, 0], 0, R)
δ([q1, 0], 0) = ([q1, 0], 0, R)
δ([q1, 0], B) = ([q1, B], B, Ø)
δ([q0, B], 1) = ([q1, 1], 1, R)
δ([q1, 1], 1) = ([q1, 1], 1, R)
δ([q1, 1], B) = ([q1, B], B, Ø)
8
- Kỹ thuật dịch qua (Shifting over)
Ví dụ: thiết kế máy Turing để dịch một chuỗi các ký hiệu khác B sang
phải 2 ô
Xây dựng: TM M(Q, Σ, Γ, δ, q0, B, F)
trong đó Q chứa các phần tử dạng [q, A1, A2] với q = q1 hoặc q2; A1
và A2 thuộc Γ. Trạng thái bắt đầu là [q1, B, B]
Phép chuyển:
δ([q1, B, B], A1) = ([q1, B, A1], X, R) (X là ký hiệu đặc biệt nào đó)
δ([q1, B, A1], A2) = ([q1, A1, A2], X, R)
δ([q1, A1, A2], A3) = ([q1, A2, A3], A1, R)
...
δ([q1, Ai-2, Ai-1], Ai) = ([q1, Ai-1, Ai], Ai-2, R)
...
δ([q1, An-1, An], B) = ([q2, An, B], An-1, R)
δ([q2, An, B], B) = ([q2, B, B], An, L)
9
- Kỹ thuật chương trình con
Ví dụ: thiết kế TM
m
thực
n
hiện phép nhân 2 số nguyên dương m và n
• Input: 0 10 B
• Output: 0m*nB
• Ý tưởng: đặt số 1 sau 0m10n (0m10n1), sau đó chép n số 0 sang phải m lần,
mỗi lần xóa đi 1 số 0 bên trái của m
• Sau khi m đã được xóa,m*nphép nhân đã được thực hiện xong, xóa tiếp 10n1.
Kếu quả còn lại sẽ là B0 B
Phân tích:
• Xóa 1 số 0 bên trái của m, dịch đầu đọc sang số n để chuẩn bị cho việc copy n số 0:
q00m10n1 ⊢ B0m-11q10n1 m-1 n1 ⊢ B0m-11q 0n10n
• Copy n số 0 sang phải: B0 1q 0
• Quay lại trạng thái bắt đầu: B0m-11q50n10n ⊢ Bq5 00m-110n10n
1
• Chuẩn bị cho việc copy kế tiếp:
B0m-11q50n10n ⊢ B20m-21q10n10n
• Copy n số 0 sang phải ...
10
- Kỹ thuật chương trình con
Thủ tục copy n số 0:
Biến đổi hình thái q00m10n1 ⊢ B0m-11q10n1:
(q0, 0) = (q6, B, R) (q6, 0) = (q6, 0, R) (q6, 1) = (q1, 1, R)
Biến đổi hình thái Bi0m-i1q50n10n*i ⊢ Bi+10m-i-11q10n10n*i:
11
- Kỹ thuật chương trình con
start q (0,B,R) q (0,0,R)
0 6
(1,1,R)
(2,2,R)
q (0,2,R) q (B,0,L) q
1 2 3
(1,1,L)
(0,0,R) (0,0,L) (B,B,R)
(2,0,L) q (1,1,R) (1,1,L)
4
(1,1,R)
q (0,0,L) q (1,1,L) q (0,0,L) q
5 7 8 9
(B,B,R) (0,0,L)
(0,B,R)
(1,B,Ø) (1,B,R)
q12 q11 q10
12
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
