Khác biệt giữa bản sửa đổi của “Máy Turing”
Nội dung được xóa Nội dung được thêm vào
n Qbot: Việt hóa |
n robot Thêm: be-x-old:Машына Т'юрынга; sửa cách trình bày |
||
Dòng 6:
Trong lý thuyết về [[ngôn ngữ hình thức]], máy Turing có khả năng đoán nhận tất cả các ngôn ngữ sinh bởi [[văn phạm cấu trúc câu]].
== Mô tả ==
[[Tập tin:TuringMachine-Band.svg|nhỏ|250px|Dải băng trên máy Turing]]
Ở dạng đơn giản và thông dụng, máy Turing có thể được mô tả với các bộ phận sau:
* Một dải băng (dài vô hạn), ở trên có nhiều ô. Mỗi ô có ghi một ký tự, và ký tự này có thể được đọc ra bên ngoài, hoặc được bên ngoài ghi đè lên (thay thế bằng ký tự khác). Các ký tự thuộc một bảng ký tự hữu hạn ''V'' (tức là có hữu hạn các ký tự), trong đó có một ký tự đặc biệt gọi là ''ký tự trống''. Các ô trên dải băng chưa bao giờ được ghi đè lên từ bên ngoài, luôn được coi là có ghi sẵn ký tự trống.
[[Tập tin:TuringMachine-Head.svg|nhỏ|phải|250px|Đầu đọc trên máy Turing]]
* Một đầu đọc và ghi, chạy trên dải băng (hoặc đứng yên cho dải băng chạy qua). Tại một thời điểm, đầu đọc này có thể thực hiện một trong 4 nhiệm vụ:
** Đọc ký tự trên ô mà đầu đọc đang nằm trên nó.
** Ghi ký tự mới lên ô mà đầu đọc đang nằm trên nó.
** Di chuyển sang ô bên trái
** Di chuyển sang ô bên phải
[[Tập tin:TuringMachine-State.svg|nhỏ|phải|250px|Ghi nhớ trạng thái trên máy Turing]]
* Một bộ phận ghi nhớ lại các ''trạng thái'' của máy Turing. Tại một thời điểm, máy Turing luôn ở 1 trong số hữu hạn các trạng thái, và bộ ghi nhớ cho biết máy đang ở trạng thái nào. Tập tất cả các trạng thái có thể ký hiệu là ''S''. Trong số các trạng thái, có trạng thái khởi động (hay trạng thái ban đầu), mặc định là máy Turing sẽ luôn ở trạng thái này khi bắt đầu hoạt động (ví dụ khi bật máy lên).
* Một ''hàm chuyển trạng thái'' hay ''bảng câu lệnh'' quy định hoạt động của máy Turing. Bảng này thường là danh sách chứa các quy tắc có dạng S<sub>i</sub> C<sub>i</sub> → S<sub>j</sub> C<sub>j</sub> D<sub>j</sub>. Ở đây S<sub>i</sub>, S<sub>j</sub> là các trạng thái trong ''S''. C<sub>i</sub>, C<sub>j</sub> là các ký tự trong bảng ký tự ''V'' (đọc được từ băng hoặc ghi lên băng). D<sub>j</sub> là 1 trong 2 hướng di chuyển của đầu đọc, sang trái hoặc sang phải. Quy tắc S<sub>i</sub> C<sub>i</sub> → S<sub>j</sub> C<sub>j</sub> D<sub>j</sub> có thể hiểu là: nếu máy đang ở trạng thái S<sub>i</sub> và đầu đọc đọc được ký tự C<sub>i</sub> thì thực hiện các công việc sau:
** Ghi đè ký tự C<sub>j</sub> lên ô mà đầu đọc đang nằm trên
** Di chuyển đầu đọc lệch 1 ô theo hướng D<sub>j</sub> (sang trái hoặc phải)
** Chuyển máy sang trạng thái S<sub>j</sub> và ghi nhớ nó vào bộ ghi nhớ trạng thái.
Trong một số mô hình, nếu máy đang ở trạng thái S<sub>i</sub> và đầu đọc đọc được ký tự C<sub>i</sub>, nhưng chưa có quy tắc nào quy định việc hành xử của máy lúc đó, thì máy được dừng lại và không tiếp tục chạy nữa.
Dòng 28:
Ngoài mô hình đã miêu tả, còn có nhiều dạng khác như dải băng chỉ có một đầu (trái hoặc phải) là vô tận; hoặc máy có nhiều dải băng, nhiều đầu đọc, ... tuy nhiên tất cả các máy đó đều có hoạt động tương đương với máy đã mô tả. Cụ thể hơn, trong lý thuyết ngôn ngữ hình thức, nếu có thể xây dựng máy theo một dạng bất kỳ đoán nhận một tập hợp các từ nào đó, thì luôn có thể xây dựng máy Turing theo dạng đã mô tả ở trên đoán nhận cùng tập hợp các từ này.
== Định nghĩa ==
Về mặt toán học, máy Turing có thể được định nghĩa bằng một bộ chứa các phần tử sau:
* [[tập hợp|Tập]] ''S'' hữu hạn chứa các trạng thái của máy.
Dòng 38:
* Các ''trạng thái kết thúc'' thuộc tập ''F'' là [[tập con]] trong ''S''.
== Tham khảo ==
* Kenneth Rosen, ''Toán học rời rạc Ứng dụng trong tin học'', Nhà xuất bản Giáo dục, 2007
== Xem thêm ==
* [[Máy hữu hạn trạng thái]]
* [[Ôtômát]]
* [[Ôtômát hữu hạn]]
* [[Ôtômát đẩy xuống]]
{{Commonscat|Turing machine}}
Dòng 55:
[[id:Mesin Turing]]
[[be:Машына Т'юрынга]]
[[be-x-old:Машына Т'юрынга]]
[[bs:Turingova mašina]]
[[bg:Машина на Тюринг]]
| |||