Bài giảng Tin học lý thuyết - Chương 7 Máy Turing (Turing Machine)

Máy Turing(Turing Machine)Nội dung:Mô hình TMTM nhận dạng ngôn ngữTM tính toán hàm số nguyênCác kỹ thuật xây dựng TMChương 7:1Mô hình TMĐịnh nghĩa: TM là một hệ thống gồm 7 thành phầnM (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, Ø} q0 : trạng thái khởi đầu 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úcHì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ất23Phé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 4TM 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}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 ⊢ XXYYq4Ví 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}5TM nhận dạng ngôn ngữq0q3q1q2start(0,X,R)(Y,Y,R)(0,0,R)(Y,Y,R)(1,Y,L)(X,X,R)(0,0,L)(Y,Y,L)(Y,Y,R)q4(B,B,Ø)6TM như là máy tính hàm số nguyênVí 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}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, 37TM như là máy tính hàm số nguyênXét chuỗi nhập 0100 (1-2) ta có: q00100 ⊢ Bq1100 ⊢ B1q200 ⊢ Bq3110 ⊢ q3B110 ⊢ Bq0110 ⊢ BBq510 ⊢ BBBq50 ⊢ BBBBq5 ⊢ BBBBq6Xé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 ⊢ Bq60q0startq1q2q4q3q5q6(0,B,R)(1,B,R)(0,0,R)(1,1,R)(1,1,R)(0,1,L)(0,0,L)(1,1,L)(B,B,L)(B,B,R)(1,B,L)(0,0,L)(B,0,Ø)(0,B,R)(1,B,R)(B,B,Ø)8Kỹ thuật lưu trữ trong bộ điều khiểnVí 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, Ø)9Kỹ 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)10Kỹ thuật chương trình conVí dụ: thiết kế TM thực hiện phép nhân 2 số nguyên dương m và n Input: 0m10nB 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, phép nhân đã được thực hiện xong, xóa tiếp 10n1. Kếu quả còn lại sẽ là B0m*nBPhâ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 Copy n số 0 sang phải: B0m-11q10n1 ⊢ B0m-11q50n10n Quay lại trạng thái bắt đầu: B0m-11q50n10n ⊢ Bq00m-110n10n Chuẩn bị cho việc copy kế tiếp: B0m-11q50n10n ⊢ B20m-21q10n10n Copy n số 0 sang phải ...11Kỹ thuật chương trình conThủ 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: 12Kỹ thuật chương trình conq0startq6(0,B,R)(0,0,R)q1(1,1,R)q2q3(0,2,R)(0,0,R)(1,1,R)(B,0,L)(0,0,L)(1,1,L)(2,2,R)q4q5(1,1,L)(2,0,L)(1,1,R)q7q8q9(0,0,L)(1,1,L)(0,0,L)(0,0,L)q10(B,B,R)(B,B,R)q11q12(1,B,R)(1,B,Ø)(0,B,R)