Есть ли термин для конечного автомата, который гарантированно остановится?

Question

Ранее я обсуждал конечный автомат, и возник вопрос, не может ли он остановиться на каком-либо вводе. Это похоже на свойство конечных автоматов, которое важно и часто упоминается, но я не могу на всю жизнь понять, как называется это свойство. Есть ли такой термин? Это «недопустимо», «не бесконечно петля» или что-то еще?

Answer 1

Машина, которая всегда останавливается, называется решающим .

Решающим фактором должна быть только машина, которая останавливается на всех входах. Например, все DFA являются решающими, как и DPDA.

Answer 2

Мое предположение будет "остановка", полученная из известной "проблемы остановки" , которая похожа на ваш вопрос, а именно, остановится ли она при заданном входе.Важным соображением является то, что машина не определяется как «остановка» в целом, а скорее для конкретного ввода.Общий случай доказан неразрешимым (сам Тьюринг).