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 | 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 Đinh 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 ữ1qữ2với q là trạng thái hiện hành của TM ữ1ữ2là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 Đinh nghĩa Đặt là một hình thái ID Giả sử ổ q Xi P 1 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. .XMqXi. .Xn I- X1X2. .Xi-2pXi-1 YXi 1. .Xn Tương tự ổ q Xs p Y R X1X2. .XMqXị. .Xn - X1X2. .Xi-2XMYpXi 1. .Xn Và với ổ q Xi p Y 0 qXi. .Xn - X1X2. .Xi-2XM pYXi 1. .Xn
