Có một thuật ngữ cho một máy trạng thái hữu hạn được đảm bảo dừng lại không?

Question

Tôi đã có một cuộc thảo luận trước đó về một máy nhà nước, và có một câu hỏi là liệu nó có thể không dừng lại trên một số đầu vào. Nó có vẻ giống như một tài sản của máy nhà nước đó là quan trọng và thường xuyên được đề cập, nhưng tôi không thể cho cuộc sống của tôi tìm ra những gì tên của tài sản đó. Có một thuật ngữ như vậy? Có phải là "có thể chữa được", "không vô hạn-loopy", hay cái gì khác?

Answer 1

Máy luôn bị tạm dừng được gọi là decider.

Người quyết định chỉ cần một máy dừng trên tất cả các yếu tố đầu vào. Ví dụ, tất cả các DFA là những người quyết định, cũng như các DPDA.

Answer 2

Dự đoán của tôi sẽ "tạm dừng", bắt nguồn từ số "halting problem" nổi tiếng, tương tự như câu hỏi của bạn, cụ thể là liệu nó có dừng lại trên một đầu vào nhất định hay không. Một lưu ý quan trọng là một máy không được định nghĩa là "tạm dừng" nói chung, mà là cho một đầu vào cụ thể. Trường hợp chung được chứng minh là không thể giải quyết được (bởi chính Turing).