Изолированный автомат – автомат, на входе которого присутствует сигнал, имеющий постоянное значение, что эквивалентно "отключению" входа. На графе изолированного детерминированного автомата из каждой вершины исходит только одна стрелка, в графе обязательно присутствует поглощающее состояние или цикл.

Заметим, что на графе изолированного детерминированного автомата из каждой вершины исходит только одна стрелка. Если при этом автомат является синхронными, то переходы между состояниями возможны, но такой автомат неизбежно должен попасть в состояние, в котором уже находился ранее. Иными словами в графах переходов детерминированного изолированного автомата обязательно будет присутствовать поглощающее состояние или цикл.

Проблема умножения произвольных чисел

Теорема. Никакой конечный автомат не может перемножать пары чисел с произвольно большим числом разрядов.

Доказательство.

• Предположим противное: существует автомат A, перемножающий пары двоичных чисел с произвольно большим числом разрядов (система счисления может быть любой без ограничения общности).
• Используем для опровержения последнего утверждения частный случай: оба сомножителя равны 2n .
• В этом случае каждый из сомножителей содержит единицу, за которой следуют n нулей;
• Результат умножения (2n ´ 2n = 22n) содержит единицу  и  2n  нулей.

Причина заключается в том, что с возрастанием числа разрядов сомножителей при умножении необходимо накапливать неограниченно большие (по объему занимаемой памяти) промежуточные результаты.