Hướng dẫn làm bài tập về máy turing năm 2024
|
toán.......................................................................................... 2 Ứng dụng của máy Turing trong việc đánh giá về độ phức tạp của thuật
Chương 1: Kiến thức cơ bản.................................................1. Mở đầu.............................................................................Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đó, ta cần phải đưa ra phương pháp giải quyết mà thực chất đó là thuật toán giải quyết vấn đề này. Rõ ràng rằng, nếu không tìm được một phương pháp giải quyết thì không thể lập trình được. Chính vì thế, thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học. Ta có thể hiểu khái niệm thuật toán như sau: Nếu cho trước một bài toán thì một cách giải bài toán được phân định ra thành một số hữu hạn bước, có kết thúc cuối cùng và đạt được kết quả mong muốn gọi là thuật toán. Về mặt lịch sử, trong những năm 30 của thế kỷ trước, khi khoa học và công nghệ phát triển, nhân loại đã nêu ra nhiều bài toán mà không tìm thấy lời giải. Có nghĩa là không tìm được thuật toán để giải chúng. Người ta đã phải tìm cách định nghĩa chính xác khái niệm thuật toán. Năm 1936, Alan Turing đã đưa ra một công cụ rất tốt để mô tả thuật toán mà ngày nay người ta gọi là máy Turing. Để ghi nhớ công lao này, Hội Tin học Mỹ (ACM) đã đặt ra giải thưởng Turing trong tin học. Cho đến nay, giải thưởng Turing là giải thưởng tin học lớn nhất thế giới. Tiếp theo Turing, một số nhà khoa học khác đã đưa ra các công cụ chính xác hoá khái niệm thuật toán. Đó là các khái niệm hàm đệ quy, thuật toán Marcop, văn phạm sinh của N. Chomsky. Những khái niệm này là cơ sở phát triển của việc nghiên cứu và ứng dụng thuật toán. Mặt khác chính nhờ các khái niệm này, người ta cũng xác định được những bài toán không thể giải được bằng thuật toán. A. Turing đã đề xuất khái niệm máy Turing nhằm chính xác hoá khái niệm thuật toán. Thực tế đã chứng tỏ rằng máy Turing là một công cụ rất tốt để mô tả thuật toán. Trải qua nhiều thập niên, lý thuyết về máy Turing đã phát triển không ngừng bởi sự đóng góp công sức của nhiều nhà khoa học, trong đó có những công trình nền tảng của Hartmanis, Lewis, Stearns, Minsky, Blum, Hopcroft, Ullman.
Do đó, rõ ràng là máy Turing là tổng quát hơn các mô hình tính toán khác mà ta đã nghiên cứu. Việc khẳng định rằng máy Turing là một mô hình toán học đủ tổng quát cho khái niệm trực giác về tính hiệu quả giải được thường được gọi là luận đề Church, được đề cập ở phần sau. Một cách hình thức, ta định nghĩa một máy Turing như sau: Định nghĩa 1: Máy Turing là một hệ thống gồm 7 thành phần MT = (Q, ∑, , , q 0 , B, F), trong đó: Q: tập khác rỗng, hữu hạn các trạng thái. : tập khác rỗng, hữu hạn các ký tự được phép viết trên băng. B: ký hiệu thuộc , ký hiệu trắng (Blank) trên băng. ∑: tập các ký tự đầu vào và là tập con của , B . : hàm chuyển: Q Q {L, R, } (đơn định) Q 2 ^ (Q {L, R, }) (đa định) Trong đó, L và R biểu diễn “trái” hay “phải” là hướng di chuyển của đầu đọc. q 0 Q là trạng thái bắt đầu F Q là tập các trạng thái kết thúc. Lưu ý:
1. Biểu diễn máy Turing............................................................Máy Turing có thể được mô tả theo ba cách: (i) Các mô tả hiện trạng (ii) Bảng chuyển trạng thái (iii) Biểu đồ (đồ thị) chuyển trạng thái. 1.3 Biểu diễn bằng các mô tả hiện thời Một bức ảnh chụp (Snapshot) hoạt động của MT có thể được sử dụng để mô tả về máy Turing. Những bức ảnh đó chính là các mô tả hiện thời của MT. Định nghĩa 2: Một mô tả hiện trạng (thể hiện) (ID) của máy Turing MT là dãy q , trong đó q là trạng thái hiện thời của MT; * là nội dung có trên băng, được tính từ đầu băng (những ký hiệu khác B) cho tới ký hiệu khác B (Blank) bên phải nhất của băng và đầu đọc đang nhìn ký tự bên trái nhất của . Giả sử ký hiệu ở dưới đầu R/W là a, ký hiệu đầu tiên của , thì là dãy các ký hiệu bên trái của a. Nếu = thì ký hiệu ở đầu đọc là B. Ví dụ. Xét một thể hiện của một MT được cho như hình
x 1 x 2 ... xi-1 q xi ... xn ⊢M x 1 x 2 ... xi-1 y p xi+1 ... xn
1.3 Biểu diễn bằng đồ thị chuyển trạng thái Máy Turing MT có thể biểu diễn bằng đồ thị định hướng được gắn nhãn, trong đó
Hình 3 – Đồ thị chuyển trạng thái của MT Hiển nhiên trên băng dữ liệu ta có B0011B. Trạng thái bắt đầu của MT là q1 và ký tự ở đầu đọc là 0. Từ hình 3 suy ra có một cung đi từ q1 đến q2 với nhãn là (0, x, R). Khi đó, ký tự 0 sẽ được thay bằng x và đầu R/W chuyển sang phải một ô, đồng thời bộ điều khiển chuyển sang trạng thái q2. Tương tự như vậy, ta có dãy tính toán như sau: Chúng ta hãy xét máy Turing MT = (Q, ∑, , , q0, B, F). Một tính toán của MT với dãy ký tự vào * , là dãy hiện trạng C 0 , C 1 , ..., Cn, sao cho C 0 = q 0 ; Ci ⊢MT Ci+1, với 0 i < n; và trạng thái của Cn là trạng thái kết thúc. Máy MT không đoán nhận nếu nó hoặc dừng ở trạng thái không được đoán nhận (trạng thái không kết thúc) hoặc nói chung là không dừng. Như vậy, băng vô hạn có thể xem vừa như kênh vào / ra, vừa như một bộ nhớ ngoài vô hạn tiềm năng của MT. ⊢ xxq 2 y1 ⊢ xxyq 21 ⊢ xxq 3 yy ⊢ xq 3 xyy ⊢ xxq 5 yy ⊢ xxyq 5 y ⊢ xxyyq 5 B ⊢ xxyyBq 6. MT dừng ở trạng thái kết thúc là q 6 , vậy 0011 là từ được MT chấp nhận. (c) q 1001 ⊢ xq 201 ⊢ x0q 21 ⊢ xq 3 0y ⊢ q 4 x0y ⊢ xq 1 0y ⊢ xxq 2 y ⊢ xxyq 2. MT dừng ở trạng thái q 2 không phải là trạng thái kết thúc, nên 001 không đoán nhận được bởi MT. 1. Thiết kế máy Turing.............................................................Để xây dựng một máy Turing ta có thể thực hiện theo sự hướng dẫn dưới đây:
(i) Từ trạng thái bắt đầu q1, MT đọc 1, chuyển sang q 2 và ghi B (ký hiệu trắng) (ii) Ở trạng thái q 2 , MT đọc 1, chuyển về q 1 và cũng ghi B. (iii) q 1 cũng là trạng thái kết thúc. Vậy, MT = ({q 1 , q 2 }, {1, B}, {1, B}, , q 1 , B, {q 1 }), trong đó được định nghĩa như trong bảng Dễ dàng kiểm tra được 11, 1111, ... là các dãy (chẵn các số 1) được MT đoán nhận và 111, 11111, ..., sẽ không được MT chấp nhận. Ví dụ. Thiết kế MT đoán nhận ngôn ngữ L = { 0n 1 n n 1}. Khởi đầu MT chứa 0n 1 n bên trái nhất trên băng sau đó là vô hạn khoảng trống B. MT lặp lại quá trình sau: MT thay 0 bên trái nhất bằng X rồi chuyển sang phải tới 1 trái nhất, MT thay chữ số 1 này bằng Y rồi dịch chuyển về bên trái cho tới khi gặp X phải nhất nó chuyển sang phải một ô (tới 0 trái nhất) rồi tiếp tục lặp một chu trình mới. Nếu trong khi dịch chuyển sang phải để tìm 1 mà MT gặp B thì MT dừng và không đoán nhận dãy vào. Tương tự, khi MT đã thay hết 0 bằng X và kiểm tra còn 1 trên băng thì MT cũng dừng và không đoán nhận dãy vào. MT đoán nhận dãy vào nếu như không còn ký hiệu 1 nào nữa trên băng. Đặt MT = (Q, ∑, , , q 0 , B, F) với các thành phần: Q = {q 0 , q 1 , q 2 , q 3 , q 4 }; ∑= {0, 1}; = {0, 1, X, Y, B} và F = {q 4 }. Ta có thể hình dung mỗi trạng thái là một câu lệnh hoặc một nhóm các câu lệnh trong chương trình. Trạng thái q 0 là trạng thái khởi đầu và nó làm cho ký hiệu 0 bên trái nhất thay bằng X. Trạng thái q 1 được dùng để tiến sang phải bỏ qua các số 0 và Y để tìm 1 bên trái nhất. Nếu MT tìm thấy 1 nó thay 1 bằng Y rồi đi vào trạng thái q 2. Trạng thái q 2 đưa MT tiến sang trái cho tới X đầu tiên và đi vào trạng thái q 0 , dịch chuyển sang phải để tới 0 bên trái nhất và tiếp tục một chu trình mới. Khi MT tiến sang phải trong trạng thái q 1 , nếu B hoặc cảnh và những ngôn ngữ không thể xác định được các thành phần một cách máy móc. 1.5 Máy Turing như là một máy tính hàm số nguyên Máy Turing cũng có thể được xem như là một máy tính của các hàm số nguyên (đi từ tập số nguyên đến tập số nguyên). Mỗi số nguyên ta viết dưới dạng số trong hệ nhất phân (unary), tức là với một số i 0 ta viết thành chuỗi 0 i (gồm i chữ số 0). Nếu hàm f() có k đối số i 1 , i 2 , ..., ik thì ta viết lần lượt các số nguyên này trên băng của MT ngăn cách nhau bởi 1, nghĩa là dãy vào có dạng 0 i(1) 10 i(2)1 ... 10i(k) . Nếu MT dừng (đoán nhận hoặc không đoán nhận dãy vào) với băng 0m thì ta nói f (i 1 , i 2 , ..., ik ) = m. Chú ý rằng, ta cũng có thể tính được hàm chỉ có một đối số. Nếu f() xác định với mọi bộ đối số i 1 , i 2 , ..., ik thì ta gọi f() là hàm đệ qui toàn bộ. Một hàm f() tính được bởi máy Turing ta gọi là hàm đệ qui bộ phận. Hàm đệ qui bộ phận tương tự như ngôn ngữ đệ qui đếm được, bởi vì nó tính được bởi máy Turing, nhưng có thể không dừng với một số đối số nào đó. Hàm đệ qui toàn bộ tương tự như ngôn ngữ đệ qui vì MT sẽ dừng trên mọi dãy vào. Ví dụ. Thiết kế máy Turing tính toán phép trừ riêng Ta định nghĩa phép trừ riêng như sau: m – n, nếu m ≥ n f(m, n) = m \ n = 0, ngược lại m < n
ii) Khi bắt đầu một vòng lặp mới, MT không tìm thấy 0 để đổi thành B, lúc này m số 0 đầu đã bị đổi thành B, trường hợp này xảy ra khi n m. Khi đó, MT thay tất cả các số 1 và 0 trên băng thành B để cho kết quả phép trừ là 0 (biểu diễn gồm toàn ký hiệu B trong hệ nhất phân). Ta xây dựng MT như sau: MT = ({q 0 , q 1 , ..., q 6 }, {0, 1}, {0, 1, B}, , q 0 , B, {q 6 }) MT sẽ bắt đầu bằng 0m 10 n trên băng và kết thúc với 0m \ n trên băng. Các phép chuyển trạng thái được định nghĩa như sau:
MT dịch trái tới khi gặp B, trở về trạng thái q0 và bắt đầu một vòng lặp mới.
đó trong một máy khác. Nghĩa là từ trạng thái trở về của máy này ta tiếp tục các phép chuyển của một máy khác, sự kiện này có ý nghĩa như là lời gọi một chương trình con khác hoặc tiếp tục thực hiện chương trình cấp trên. Lưu ý, các trạng thái của chương trình con phải phân biệt với chương trình cấp trên của nó trong cấu trúc phân cấp của các chương trình con. Ví dụ. Thiết kế MT thực hiện phép nhân 2 số nguyên m với n. + Dãy vào: 0m 10 n + Dãy ra: 0m x n MT bắt đầu với 0m 10 n trên băng và kết thúc với 0m x n trên băng được bao quanh bởi các B. Ý tưởng chung: là đặt thêm số 1 sau 0m 10 n rồi chép khối n số 0 sang phải m lần, mỗi lần xoá một con 0 bên trái của 0m . Ta được kết quả cuối cùng là 10 n 10 m x n . Bây giờ ta chỉ việc xoá 10n1 ta sẽ được kết quả 0m x n. Phần chính của thuật toán trên là thủ tục COPY để chép n số 0 sang phải. Thủ tục này được xác định bằng các hàm chuyển sau: Ở trạng thái q 1 nhìn thấy 0, MT đổi 0 thành 2 và đi vào trạng thái q 2. Ở trạng thái q 2 , MT dịch phải tới B, ghi 0 rồi dịch trái trong trạng thái q 3. Khi ở trạng thái q 3 mà gặp 2, MT đi vào trạng thái q 1 để tiếp tục lặp lại quá trình trên cho tới khi gặp 1. Trạng thái q 4 được dùng để biến đổi 2 thành 0 và thủ tục dừng tại q 5. Để làm đầy đủ chương trình ta phải thêm các trạng thái để biến đổi hình trạng khởi đầu q 00 m 10 n thành B0m-11q 10 n1. Tức là ta cần ba qui tắc: (q 0 , 0) = (q 6 , B, R), (q 6 , 0) = (q 6 , 0, R), (q 6 , 1) = (q 1 , 1, R) Sau đó, ta lại thêm các phép chuyển và trạng thái cần thiết để biến đổi từ hình thái Bi 0 m-i1q 50 n 10 n x i thành Bi+1 0 m-i-11q 10 n 10 n x i là trạng thái bắt đầu lại việc COPY, đồng thời kiểm tra i = m hay không (khi tất cả các 0 của 0m đã bị xoá). Nếu i = m thì 10n1 bị xoá và quá trình tính toán sẽ dừng ở trạng thái q 12. 1. Máy Turing không đơn định...................................................Máy Turing trong mô hình gốc nêu trên được gọi là máy Turing đơn định vì hàm chuyển () là đơn trị. Máy Turing không đơn định có mô hình tương tự như mô hình gốc nhưng điểm khác biệt ở chỗ là trong mỗi lần chuyển, máy Turing có thể lựa chọn một trong một số hữu hạn các trạng thái kế tiếp (hàm chuyển () là không đơn trị), lựa chọn hướng chuyển đầu R/W, và lựa chọn ký hiệu ghi vào băng thay thế ký hiệu vừa đọc được. Lưu ý: máy Turing không đơn định vốn không dự định để mô hình hoá các hoạt động tính toán. Nó chỉ đơn thuần là một máy toán học bổ trợ và có thể hình dung như một máy để kiểm chứng một phỏng đoán có đúng hay không. 1. Luận đề Church – Turing.......................................................Giả thuyết cho rằng khái niệm trực giác “Hàm tính được” có thể được định nghĩa bằng lớp các hàm đệ quy bộ phận là giả thuyết Church hay còn được gọi là luận đề Church - Turing. Chúng ta không thể hy vọng chứng minh được giả thuyết Church cũng như những định nghĩa không hình thức về “sự tính được”, nhưng chúng ta có thể cho những dẫn chứng về những khả năng của chúng. Trong một thời gian dài, khái niệm trực giác về “sự tính được” đặt không giới hạn trên số bước hoặc tổng số các phép lưu trữ, có vẻ như các hàm đệ quy bộ phận có thể tính được một cách trực giác, mặc dù cũng có một số hàm không thể tính được, trừ khi ta đặt giới hạn cho việc tính toán sau đó hoặc ít nhất thiết lập được liệu có hay không có phép tính cuối cùng. Điều còn không rõ là, liệu lớp các hàm đệ quy bộ phận có thể bao hàm tất cả mọi “hàm tính được” hay không. Những nhà logic học đã đưa ra nhiều |
