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 Bot: Adding {{Commonscat|Turing machine}} |
n Qbot: Việt hóa |
||
Dòng 1:
[[
'''Máy Turing''' là một mô hình về thiết bị xử lý các ký tự, tuy đơn giản, nhưng có thể thực hiện được tất cả các [[thuật toán]] [[máy tính]]. Các máy Turing đã được [[Alan Turing]] trình bày vào năm [[1936]]. Các máy Turing được xây dựng không dành cho việc trực tiếp chế tạo ra máy tính, mà là dành cho các [[thí nghiệm tưởng tượng]] để tìm hiểu về các giới hạn của việc tính toán trên máy móc. Việc nghiên cứu các tính chất của máy Turing cho biết nhiều kiến thức quan trọng trong lĩnh vực [[khoa học máy tính]] và lý thuyết về [[độ phức tạp tính toán]].
Dòng 7:
==Mô tả==
[[
Ở 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.
[[
*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ó.
Dòng 16:
**Di chuyển sang ô bên trái
**Di chuyển sang ô bên phải
[[
*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:
| |||