У меня было обсуждение ранее о машине состояния, и возник вопрос о том, может ли она не останавливаться на каком-либо вводе. Похоже, что свойство государственных машин важно и часто упоминается, но я не могу для жизни понять, что такое имя этого имущества. Есть ли такой термин? Является ли это "haltable", "not-infinitely-loopy" или что-то еще?
Существует ли термин для конечного автомата, который гарантированно остановится?
Ответ 1
Машина, которая всегда останавливается, называется decider.
Решителю может быть только машина, которая останавливается на всех входах. Например, все DFA являются решающими, а также DPDA.
Ответ 2
Мое предположение было бы "остановлено", полученное из знаменитого "проблема с остановкой" , что похоже на ваш вопрос, а именно: будет останавливаться на заданном входе. Важное соображение состоит в том, что машина не определена как "остановка" в целом, а скорее для конкретного ввода. Доказано, что общий случай неразрешим (сам Тьюрингом).