<< Chapter < Page Chapter >> Page >
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

Mô hình máy turing (tm)

Một mô hình hình thức cho một thủ tục hiệu quả sẽ có những đặc tính cụ thể. Đầu tiên, mỗi thủ tục sẽ được mô tả một cách hữu hạn. Tiếp đó, thủ tục sẽ được phân thành một số bước độc lập, mà mỗi bước thực thi một vấn đề. Nguyên tắc này cũng được hình thức trong mô hình máy Turing.

Máy Turing có một băng nhớ, dùng để ghi mọi loại dữ liệu (dữ liệu nhập, dữ liệu dùng cho việc điều khiển tương tự như một chương trình máy tính và các kết quả trung gian khi làm việc). Với một bộ điều khiển chứa một số hữu hạn trạng thái, TM cũng như các ôtômát khác, làm việc theo lối "ngắt quãng" theo từng bước chuyển.

Mô tả tm

Máy Turing có rất nhiều dạng đồng khả năng, nghĩa là có nhiều mô hình và định nghĩa khác nhau cho máy Turing nhưng tất cả chúng đều tương đương nhau. Song, nói chung mô hình cơ bản của một máy Turing gồm :

- Một bộ điều khiển hữu hạn.

- Một băng được chia thành các ô.

- Một đầu đọc-viết, mỗi lần đọc có thể duyệt qua một ô trên băng để đọc hay viết ký hiệu.

Mỗi ô có thể giữ được một ký hiệu trong số hữu hạn các ký hiệu băng (các ký hiệu được phép viết trên băng). Khởi đầu xem như n ô bên trái của băng (n  0) giữ chuỗi nhập (input), chuỗi nhập là một chuỗi các ký tự được chọn từ một tập hợp con của tập hợp các ký hiệu băng, tập hợp con này gọi là tập các ký hiệu nhập. Phần còn lại của băng coi như có vô hạn khoảng trống, ký hiệu B (Blank), B là một ký hiệu đặc biệt của băng nhưng không phải là ký hiệu nhập.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Giáo trình tin học lý thuyết. OpenStax CNX. Jul 30, 2009 Download for free at http://cnx.org/content/col10826/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Giáo trình tin học lý thuyết' conversation and receive update notifications?

Ask