tailieunhanh - Bài giảng Tin học lí thuyết: Chương 7 - Võ Huỳnh Trâm

Bài giảng "Tin học lí thuyết - Chương 7: Máy Turing (Turing Machine)" cung cấp cho người họ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. nội dung chi tiết. | 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 Z r ỗ q0 B F Q tập hữu hạn các trạng thái Z bộ ký hiệu nhập r tập hữu hạn các ký hiệu được viết trên băng õ hàm chuyển Q x r Q x r x L R 0 q0 trạng thái khởi đầu B ký hiệu dùng để chỉ khoảng trống trên băng F c Q tập các trạng thái kết thúc Hình thái a1qa2 với q là trạng thái hiện hành của TM 0102 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 là một hình thái ID Giả sử ỗ q X. 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 -XX .X pX YK Xn 12 i-1 i n 12 i-2 i-1 i 1 n Tương tự ỗ q X. p Y R X1X2. X - X1X2. .Xi-2Xi-1 YpXi 1. .Xn Và với õ q Xi p Y 0 X1X2. .Xi-1 qX .Xn I- X1X2. .Xi-2Xi-1 pYXi 1 .Xn