Chương 1: Luận văn trình bày tổng quan về máy Turing và các vấn đền liên quan đến thuật toán. Chương 2: Luận văn cài đặt máy Turing trên ngôn ngữ C++ và cải tiến một số bộ nhớ tăng hiệu quả làm việc của máy. Chương 3: Luận văn sử dụng máy Turing để giải một số bài toán và đánh giá độ phức tạp cụ thể từng bài. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 1 Chƣơng 1 TỔNG QUAN MÔ HÌNH MÁY TURING Trong chương này của luận văn học viên giới thiệu lại một số định nghĩa về máy Turing và thuật toán.
Trong đó có mô tả về máy Turing học viên đã cài đặt, từ đó chỉ ra quan hệ giữa máy Turing và độ phức tạp của thuật toán. Giới thiệu chung Máy Turing là một mô hình thiết bị xử lý kí tự, tuy đơn giản, nhưng có thể thực hiện tất cả các thuật toán máy tính. Các máy Turing được Alan Turing trình bày năm 1936. Các máy Turing không dành cho việc trực tiếp tạo ra các máy tính thực tế mà dành cho các thí nghiệm tưởng tượng để tìm hiểu về giới hạn của việc tính toán trên máy móc.
Việc nghiên cứu tính chất máy Turing cho nhiều kiến thức quan trọng trong lĩnh vực khoa học máy tính và lý thuyết độ phức tạp thuật toán. [2] Trong luận đề Church-Turing đã khẳng định mọi hàm toán học tính được đều có thể dùng máy Turing để tính toán do đó có phép định nghĩa về các khái niệm về sự tính được của hàm hoặc thuật toán. Máy Turing có nhiều dạng đồng khả năng, tức là có nhiều mô hình và định nghĩa cho máy Turing nhưng chúng đều tương đương nhau. Về cơ bản mô hình máy Turing gồm 3 phần chính sau: - Một bộ điều khiển hữu hạn.
- Một băng chia thành các ô. - Một đầu đọc-ghi, mỗi lần đọc có thể duyệt qua một ô trên băng để đọc hay viết ký hiệu.[2] Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 Bộ điều khiển có số trạng thái hữu hạn trong đó có trạng thái ban đầu và trạng thái kết thúc. Như vậy khi máy Turing bắt đầu hoạt động sẽ nhận trạng thái đầu tiên là trạng thái ban đầu, máy chỉ dừng khi đạt trạng thái kết thúc. Trên băng mỗi ô có thể giữ một ký hiệu hợp lệ (ký hiệu được phép ghi trên băng) khởi đầu xem như n ô bên trái ( n 0 ) giữ chuỗi nhập (input), các ô còn lại là các ký tự trắng (ký tự trắng là ký tự đặc biệt nhưng không thuộc chuỗi nhập), phần còn lại của băng được coi là vô hạn.
Đầu đọc ghi có thể di chuyển sang trái, phải hoặc đứng yên tùy vào trạng thái hiện tại và ký tự nhận được. Đầu đọc ghi có thể nhận dạng kí tự hiện hành và viết đè một ký tự khác vào ô đó để thay ký tự cũ. Mô hình máy Turing 1. Cấu trúc máy Turing Về mặt toán học máy Turing có thể được định nghĩa như sau: Định nghĩa máy Turing:[7] Máy Turing là một hệ thống M (Q, , , , q0 , B, F ) , trong đó: Q là tập hữu hạn các trạng thái.
là bộ ký hiệu nhập. là tập hữu hạn các kí tự được phép viết trên băng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 B là ký hiệu thuộc dùng chỉ khoảng trắng trên băng (Blank). q0 Q là trạng thái bắt đầu của hệ thống.
F Q là trạng thái kết thúc của hệ thống. Hàm chuyển hoạt động như sau: : Qx Qxx (trái, phải, không dịch chuyển). Hàm chuyển được định nghĩa trước và máy Turing chỉ có thể hoạt động theo hàm chuyển này. Trong khuôn khổ luận văn, học viên cài đặt máy Turing theo các câu lệnh để biểu diễn thuật toán.
Trong đó mỗi câu lệnh có năm thành phần dạng (S, C, R, T, Q) Trong đó: S: là trạng thái hiện hành của máy Turing. C: là ký tự tại ô mà con trỏ đang trỏ. R: là kí tự sẽ điền thay vào vị trị của C, nếu R = _ tức là giữ nguyên kí tự C. T: là hướng dịch chuyển của con trỏ bao gồm L: dịch trái.
R: là dịch phải. N: là không dịch chuyển. Q: là trạng thái máy Turing chuyển đến sau khi thực hiện dãy lệnh. Ngoài ra chương trình mặc định các trạng thái của máy Turing theo dạng số nguyên dương, trạng thái bắt đầu là trạng thái 1, trạng thái kết thúc là trạng thái 0.
Ví dụ: 1abR2 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 Câu lệnh trên sẽ hoạt động như sau: Trạng thái hiện hành của máy Turing là 1, con trỏ máy đang chỉ vào ô chứa kí tự “a”, máy Turing sẽ điền kí tự “b” thay thế vào ô đó. Con trỏ máy sau đó chuyển dịch sang phải 1 ô, trạng thái máy chuyển thành 2. Để cải tiến cách soạn thảo học viên cài đặt máy Turing nhận các câu lệnh trong đó thay thế các thành phần không thay đổi trong lệnh máy thành dấu gạch dưới. Và có thể dùng câu lệnh gộp khi 1 trạng thái gặp nhiều kí tự khác nhau nhưng có cùng cách xử lý như nhau.
Ví dụ: Lệnh 1 _ _ _ _ sẽ hoạt động như sau: Nếu máy đang ở trạng thái 1. Ô nhớ đang được con trỏ máy trỏ vào chứa bất cứ ký tự nào; Giữ nguyên ký tự đó; Con trỏ không dịch chuyển; Trạng thái sau khi thực hiện lệnh không thay đổi là trạng thái 1. Ví dụ: câu lệnh gộp. 1 {a,b,c} _ R _ sẽ hoạt động như sau: Trạng thái hiện hành của máy Turing là trạng thái “1”.
Đầu đọc ghi trỏ tới một trong các kí tự “a”, “b”, “c” sẽ giữ nguyên kí tự đó. Đầu đọc ghi dịch chuyển sang phải 1 ô. Trạng thái máy Turing giữ nguyên là trạng thái “1”. Ví dụ: Xét tính chẵn lẻ của một số.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 - Tư tưởng thuật toán: để xét một số là chẵn hay lẻ chỉ cần chia lấy phần dư cho 2, nếu kết quả là 1 suy ra số đó là số lẻ, còn kết quả là 0 số đó là số chẵn. Hoặc nếu biểu diễn số cần xét là một dãy các chữ số: X = X1X2 .Xn1Xn , nếu chữ số cuối cùng X n {0, 2, 4,6,8} thì số cần xét X là số chẵn, nếu chữ số cuối cùng X n {1,3,5,7,9} thì số cần xét X là số lẻ. Mã chương trình máy Turing: 1 _ _ R _ // dịch phải chuỗi số. 1#_L2 2 {0,2,4,6,8} 0 L 3 // kí tự “0” biểu thị số chẵn.
2 {1,3,5,7,9} 1 L 3 // kí tự “1” biểu thị số lẻ. 3 {0,1,2,3,4,5,6,7,8,9} # L 3 // loại các số không ở trong kết quả. 3 # _ _ 0 // trạng thái 0 là trạng thái kết thúc. Kết quả của chương trình: Mô phỏng với số đầu vào là 33.
Input: #33# (2) Command: 1 _ _ R _ #33# (2) Command: 1 _ _ R _ #33# (2) Command: 1 # _ L 2 #33# (2) Command: 2 3 1 L 3 #31# (2) Command: 3 3 # R 3 #1# (2) Command: 3 # _ N 0 #1# (2) Final output: #1# (1) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Timer = 6 Chương trình trải qua 6 bước để đưa ra kết luận số 33 là số lẻ (tương ứng với kết quả là “1”). Vậy với thuật toán trên máy Turing trải qua 6 bước chuyển, số ô sử dụng là 2. So sánh cách soạn thảo viết rõ từng lệnh máy với cách sử dụng những kí hiệu mà học viên cài đặt: Bảng 1. So sánh câu lệnh giữa cách viết thông thƣờng và cách viết gộp Cách viết thông thường Cách viết gộp 200L3 2 {0,2,4,6,8} 0 L 3 220L3 240L3 260L3 280L3 Hai cách viết trên đều hoạt động giống nhau đó là khi máy Turing ở trạng thái 2 gặp các kí tự “0”, “2”, “4”, “6”, “8” chuyển thành kí tự “0”, dịch con trỏ sang trái một ô, chuyển trạng thái máy Turing thành trạng thái “3”.
Nhưng với cách viết thông thường học viên sẽ phải viết 5 dòng lệnh, trong đó với cách viết lệnh gộp học viên chỉ cần 1 lệnh duy nhất để thực hiện. Hoạt động của máy Turing Máy Turing hoạt động theo cơ chế như sau:[5] Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 - Đầu đọc ghi đọc một kí tự trên ô của băng, phụ thuộc vào trạng thái bên trong mà đầu đọc ghi ghi một kí tự hợp lệ vào ô đó (kí tự thuộc tập ). - Đầu đọc ghi dịch chuyển sang trái, sang phải hoặc đứng yên tại chỗ. - Trạng thái bên trong được thay đổi tùy vào kí tự được đọc và trạng thái hiện hành.
- Máy Turing bắt đầu từ trạng thái ban đầu và dừng khi đạt trạng thái kết thúc. Máy Turing được mô tả trong luận văn của học viên hoạt động theo đúng cơ chế trên, cụ thể trong chương trình học viên quy ước trạng thái bắt đầu của máy Turing là trạng thái “1”, trạng thái kết thúc là trạng thái “0”. Vậy một chương trình viết bởi các câu lệnh để mô tả thuật toán sẽ dừng lại khi gặp câu lệnh dạng (S C R T 0). Các thành phần của câu lệnh đã được học viên trình bày ở phần 1.
Trạng thái và sơ đồ trạng thái của máy Turing[2] Một hình thái của máy Turing M được cho bởi α 1 q α2, trong đó q là trạng thái hiện hành của M; α1α2 ∈ Γ* là nội dung của băng tính từ đầu băng cho tới ký hiệu khác Blank bên phải nhất của băng. Giả sử Q và Γ rời nhau: đầu đọc đang đọc ký hiệu bên trái nhất của α 2 hoặc nếu α2 = ε thì đầu đọc đọc Blank. Hàm chuyển Ta định nghĩa một phép chuyển trạng thái của TM như sau: Đặt X1X2. Xn là một hình thái của máy Turing.
+ Giả sử δ (q, Xi) = (p, Y, L), trong đó: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 - Nếu i - 1 = n thì Xi là B. - Nếu i =1 thì không có ID kế tiếp, nghĩa là đầ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-2p Xi-1Y Xi+1.