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 →Mô tả |
|||
Dòng 27:
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 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.
* Bảng ký tự ''V'' hữu hạn chứa các ký tự ghi trên băng.
* Hàm chuyển trạng thái ''f'' : ''S''×''V'' → ''S''×''V''×{''Phải'' , ''Trái''}
Ngoài ra có thể định nghĩa thêm:
* Phần tử đặc biệt là ''ký tự trống'' ''B'' trong ''V'', các ký tự khác trống trong ''V'' được gọi là các ''ký tự đầu vào''.
* Trạng thái đặc biệt là ''trạng thái ban đầu'' ''S''<sub>0</sub> trong ''S''.
* Các ''trạng thái kết thúc'' trong ''S''.
[[Thể loại:Khoa học máy tính]]
| |||