0.6 Máy turing

Nội dung chính : Trong chương này, ta sẽ xét thêm một loại máy trừu tượng khác - máy Turing (TM - Turing Machines). Chúng có khả năng đoán nhận được lớp ngôn ngữ lớn hơn lớp ngôn ngữ phi ngữ cảnh. Đây còn là một mô hình của sự tính toán, mô hình của các thủ tục hiệu quả, là nền tảng cho quá trình xử lý của máy tính hiện đại, được giới thiệu bởi Alan Turing vào năm 1936. Nhờ đó, các khái niệm về "sự tính được", "sự giải được" được xác định một cách rõ ràng trên cơ sở sự xuất hiện của một số hàm không tính được, các bài toán không giải được. Mục tiêu cần đạt: Cuối chương, sinh viên cần phải nắm vững: Khái niệm TM, định nghĩa và các thành phần.  Các kỹ thuật thiết kế TM. Một số biến dạng TM từ mô hình chuẩn.  Xây dựng TM dùng nhận dạng ngôn ngữ hoặc tính toán các hàm số nguyên đơn giản được biểu diễn trong hệ nhất phân. Các tính chất của lớp ngôn ngữ được chấp nhận bởi TM. Kiến thức cơ bản: Để tiếp thu tốt nội dung của chương này, sinh viên cần hiểu rõ cách thiết kế các hàm chuyển trạng thái trên mô hình máy tính toán; ý tưởng thiết kế một số thuật toán đơn giản trên tập hợp số, …Tài liệu tham khảo : [1]John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages and Computation – Addison – Wesley Publishing Company, Inc – 1979 (Chapter 7 : Turing Machines ) [2]Peter Linz – An Introduction to Formal Languages and Automata – D.C. Heath and Company – 1990. [3]David Barker-Plummer - Stanford Encyclopedia of Philosophy – Turing Machines: http://plato.stanford.edu/entries/turing-machine/[4] Turing Machinesimplemented in JavaScript:http://www.turing.org.uk/turing/scrapbook/tmjava.html [5]By Jon Barwise and John Etchemendy -Turing Machines: http://www-csli.stanford.edu/hp/Turing1.html