Проблема не в машине Тьюринга, а в «алгоритме». Причина, по которой вы не можете предсказать, остановится ли алгоритм или нет, заключается в следующем:
function confusion()
{
if( halts( confusion ) )
{
while True:
no-op
}
else
return;
}
Любой язык, который не может выполнять рекурсию или циклы, на самом деле не был бы "универсальным".
Регулярные выражения и конечные автоматы - это одно и то же! Лексирование и сопоставление строк - это одно и то же! Причина, по которой FSM останавливаются, заключается в том, что они никогда не зацикливаются; они просто передают вход char-by-char и выходят.
EDIT:
Для многих алгоритмов очевидно, остановятся они или нет.
например:
function nonhalting()
{
while 1:
no-op
}
Эта функция явно никогда не останавливается.
И эта функция, очевидно, останавливается:
function simple_halting_function()
{
return 1;
}
Итак, суть: вы МОЖЕТЕ гарантировать, что ваш алгоритм остановится, просто спроектируйте его так, чтобы он работал.
Если вы не уверены, будет ли алгоритм все время останавливаться; тогда вы, вероятно, не сможете реализовать его ни на одном языке, который гарантирует «остановку».