Tôi nghĩ rằng sự nhầm lẫn có thể đến từ việc bạn sử dụng "các bước" thay vì "trạng thái". Bạn có thể nghĩ về trạng thái của máy như là giá trị trong bộ nhớ của nó (mặc dù như một poster trước đã lưu ý, một số người cũng lấy trạng thái của máy để bao gồm nội dung của băng - tuy nhiên, tôi không nghĩ rằng định nghĩa đó có liên quan cho câu hỏi của bạn). Có thể sự thay đổi trong thuật ngữ này có thể là trái tim của sự nhầm lẫn của bạn. Hãy để tôi giải thích những gì tôi nghĩ rằng đó là bạn đang suy nghĩ. :)
Bạn đã liệt kê năm số - ví dụ: (1,0,1,1,2). Khi bạn nói đúng, điều này sẽ được diễn giải (đọc từ trái sang phải) là "Nếu máy ở trạng thái 1 VÀ ô vuông hiện tại chứa số 0, in 1, di chuyển sang phải và chuyển sang trạng thái 2." Tuy nhiên, việc bạn sử dụng từ "bước" dường như gợi ý rằng "bước 2" phải được theo sau bởi "bước 3", v.v., trong thực tế, máy Turing có thể đi qua lại giữa các trạng thái (và tất nhiên, có chỉ có thể có nhiều trạng thái hữu hạn).
Vì vậy, để giải đáp thắc mắc của bạn:
- máy Turing theo dõi "khẳng định" không phải là "bước";
- Những gì bạn mô tả là máy Turing hợp pháp;
- Máy Turing đơn giản hơn (mặc dù không thú vị) sẽ là máy bắt đầu ở trạng thái HALT.
Chỉnh sửa: Ngữ pháp, Định dạng và xóa mô tả không cần thiết về máy Turing.
Response to comment: Đúng tôi nếu tôi hiểu sai bình luận của bạn, nhưng tôi không có ý đề nghị một máy Turing có thể là nhiều hơn một nhà nước tại một thời điểm, chỉ rằng số lượng trạng thái có thể có thể là bất kỳ số hữu hạn nào. Ví dụ, đối với máy 3 trạng thái, bạn có thể gắn nhãn các trạng thái có thể A, B và C. (Trong ví dụ bạn đã cung cấp, bạn gắn nhãn hai trạng thái có thể là '1' và '2') Tại bất kỳ thời điểm nào, chính xác một trong những giá trị đó (trạng thái) sẽ nằm trong bộ nhớ của máy. Chúng tôi sẽ nói, "máy ở trạng thái A" hoặc "máy ở trạng thái B", v.v. (Máy của bạn bắt đầu ở trạng thái '1' và kết thúc sau khi nó vào trạng thái '2').
Ngoài ra, nó không còn rõ ràng với tôi những gì bạn có nghĩa là bởi một máy "đơn giản/est". Máy Turing phổ biến nhỏ nhất được biết đến (tức là máy Turing có thể mô phỏng một máy Turing khác, được đưa ra một băng thích hợp) yêu cầu 2 trạng thái và 5 ký hiệu (xem the relevant Wikipedia article).
Mặt khác, nếu bạn đang tìm kiếm một cái gì đó đơn giản hơn một máy Turing có cùng công suất tính toán, Post-Turing machines có thể được quan tâm.
Vậy sự khác nhau giữa FSM và TM là gì? – Yehonatan
@Yehonatan: FSM không có băng. Bạn nạp một đầu vào FSM (một luồng của các đầu vào và số 0), nhưng luồng này không giống như một băng, vì FSM không thể tua lại hoặc sửa đổi nó. – Seth
@Seth hiểu. – Yehonatan