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ả |
n →Mô tả |
||
Dòng 26:
Trong số các trạng thái trong ''S'', có thể quy định ra những trạng thái được gọi là trạng thái ''kết thúc''. Trong lý thuyết về [[ngôn ngữ hình thức]], nếu một đoạn ký tự (gọi là một ''từ'' hay một ''câu'') ghi trên dải băng đưa máy Turing chạy từ trạng thái ban đầu đến một trong số các trạng thái kết thúc thì câu viết đó được gọi là ''đoán nhận'' bởi máy Turing đã cho.
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==
| |||