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
Sửa vài chỗ đọc không trôi chảy Thẻ: Soạn thảo trực quan Sửa đổi di động Sửa đổi từ trang di động |
Không có tóm lược sửa đổi Thẻ: Soạn thảo trực quan Sửa đổi di động Sửa đổi từ trang di động |
||
Dòng 11:
* 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
** Đọ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 ở một 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 '''<u>trạng thái có thể</u>''' 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à một 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
| |||