Итоги голосования для комментария:
Ahill_
Но конечным или конечно описываемым.
К чему ты это написал, я совсем не понял.
Если у нас есть возможность для любого элемента последовательности вычислить его за конечное количество ходов — то мы можем и поставить в соответствие каждому элементу последовательности немастерское правило.
Да, только проблема в том, что таких правил заранее известное количество (именно заранее известное, а не «конечное, но заранее неизвестное»).

Давай я приведу простой пример бордгейма. С выделенным болдом правилом он разрешим конечным автоматом, без этого правила — нет.

Да обрати внимание на подчёркнутые части текста, они на самом деле важны (для понимания ограничений конечных автоматов).
ПРАВИЛА:
1. СОСТАВ БОРДГЕЙМА:
В бордгейме есть колода из карт, состоящая из: 10 карт «0», 10 карт «1»; доной карты «е»;
2. ХОД ИГРОКА:
Каждый ход игрок берёт одну карту из колоды, в руку; после чего играет с руки карту; значение её запоминается (любым способом) и сыгранная карта замешивается в колоду, а колода перетасовывается;
3. ЗАВЕРШЕНИЕ ИГРЫ:
Игра заканчивается, когда игрок выложил карту «е» или на ход с номером 100500;
4. УСЛОВИЯ ПОБЕДЫ:
игрок победил, записанная последовательность соответствует рекурсивному правилу:
— «1»;
— «1»; «0»;
— «1»; «0»; «0»;
— «1»; карты «0» на 1 больше чем в редыдущей подпоследовательности
— и так далее

Заметь: если у нас ходов не более, чем 100500 (т.е. выделенное болдом правило в силе) — то мы можем задать конечный автомат (с числом состояний 100500 или «хитро запаковать» всё что нам надо в меньшее число состояний).
Если же у нас ходов сколь угодно много (потенциально неограниченно много), то конечный автомат тут бессилен. Всегда возникнет проблема, что ему не хватит состояний, чтобы произвести очередную операцию.
+