Неразрешимые проблемы, связанные с КА

[SakumaRei]

Собственно, такой вопрос: какие вы знаете неразрешимые проблемы, связанные с конечными автоматами (КА)? Преподаватель задал такой вопрос, а я не знаю как на него отвечать.

[Профессор Снэйп]

В каком смысле неразрешимые? В смысле алгоритмически неразрешимые проблемы, вроде проблемы остановки? Или в смысле открытые математические проблемы, то есть не доказанные и не опровергнутые гипотезы, в формулировке которых присутсвует словосочетание "конечный автомат"?

[SakumaRei]

Профессор Снэйп в сообщении #572483 писал(а):

В каком смысле неразрешимые? В смысле алгоритмически неразрешимые проблемы, вроде проблемы остановки? Или в смысле открытые математические проблемы, то есть не доказанные и не опровергнутые гипотезы, в формулировке которых присутсвует словосочетание "конечный автомат"?

Алгоритмически неразрешимые.

[SakumaRei]

Помогите же, пожалуйста. С машиной Тьюринга гораздо проще - там проблем хватает. А вот с КА имеются проблемы в лице нехватки проблем :)

[Crystaly]

Ну вот например проблема: "С помощью КА нельзя выполнить умножение произвольных чисел". То что надо или нет?