Разница между Машиной Тьюринга и Конечным автоматом?

[Nerex]

Нужно найти такой язык который принимает Машина Тьюринга но не принимает Конечный автомат. Я подчеркиваю именно ЯЗЫК.

[незваный гость]

Давайте начнём с вопроса: какие языки порождаются машинной Тьюринга, и какие — конечными автоматами?

Если хотите, можно сделать ещё шаг назад: какие грамматики…

[Сомик]

Например язык со всеми словами длины $n^2$. т.е. $\{1,1111,111111111,1111111111111111,\dots\}$. То, что он НЕ распазнается конечным автоматом, следует из Леммы О Накачке (pumping lemma). То что он разпазается машиной Тюринга следует из вычислимости функции $n^2$