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