Bài giảng Lý thuyết tính toán: Bài 8 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về máy Turing; khái niệm máy Turing; định nghĩa hình thức; ngôn ngữ của Turing Machine; cấu trúc dữ liệu Turing Machine; thành phần của Turing Machine; trạng thái hoạt động của Turing Machine; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LÝ THUYẾT TÍNH TOÁN BÀI 8 Máy Turing Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Khái niệm 2. Định nghĩa hình thức 3. Ngôn ngữ của TM 1 Khái niệm Khái niệm Máy Turing Turing Machine TM TM - Được đề xuất đầu tiên vào năm 1936 bởi Alan Turing - Là một mô hình tính toán mạnh hơn PDA và FSM - Là một mô hình chính xác hơn rất nhiều của máy tính đa năng - Tương tự như DFA nhưng có một bộ nhớ vô hạn và không hạn định . b b b a a a a . q1 Finite Control 2 Cấu trúc dữ liệu của TM FSM Lưu trữ hữu hạn các trạng từ dữ liệu vào PDA Chuỗi đầu vào và ngăn xếp TM Băng nhớ Sự khác biệt giữa TM và FSM 1. TM có thể đọc ghi ký tự lên ô mà đầu đọc đang nằm trên nó 2. Đầu đọc có thể di chuyển sang trái hoặc phải 3. Dải băng tape là dài vô tận 4. Những trạng thái đặc biệt cho việc bác bỏ và chấp thuận có hiệu lực tức thì 3 Thành phần của TM Bộ chữ của băng tape alphabet Σ 0 1 hoặc thông thường là Σ 0 1 a b x Ký hiệu dấu trắng là một ký hiệu đặc biệt và Σ Cấu hình ban đầu chỉ có xâu vào và phần còn lại là ký hiệu 0 1 1 0 1 1 0 1 . q1 Finite State Machine 4 TM hoạt động như thế nào Tại mỗi bước tính toán Đọc ký hiệu của ô hiện tại trên băng mà con trỏ trỏ tới Có thể cập nhật ký hiệu trên ô đang được trỏ tới đó Dịch chuyển từng ô một theo chiều chỉ định trái hoặc phải Biểu diễn hình học a b R - a là ký hiệu được đọc thuộc ô hiện tại trên băng - b là ký hiệu sẽ được ghi vào ô hiện tại trên băng - R là chiều dịch chuyển L left R right 5 TM hoạt động như thế nào Thao tác chỉ đọc ký hiệu 1 1 R Các trường hợp của sự tính toán computation Tam dừng và chấp thuận Halt and accept Nếu đạt được trạng thái chấp thuận thì dừng ngay lập tức Tạm dừng và bác bỏ Halt and reject Nếu đạt được trạng thái bác bỏ thì dừng ngay lập tức Lặp loop Máy sẽ chạy liên tục không dừng TM là đơn định 6 Ví dụ 1 TM sau đoán nhận ngôn ngữ L 01 0 1 y R 0 x R 0 x R A B C 1 1 R 0 0 R 1 1 R R R R Reject Accept 7 Ví dụ 2 Đưa ra TM đoán nhận ngôn ngữ L 0n 1n Thuật toán để xây dựng TM cho ngôn
