Здравствуйте, Sinclair, Вы писали:

S>·>Хорошая оптимизация, но не ничем поможет в контексте обсуждения. Этот алгоритм предназначен чтобы находить _длину_ цикла в списке про который заведомо известно, что в нём конечное число элементов. Этот алгоритм неприменим если мы этого не знаем.
S>Этот алгоритм применим к любым машинам с ограниченной памятью. Он не работает на МТ ровно потому, что её память ничем не ограничена: мы запросто можем получить неостановимый алгоритм без циклов.
S>Физические машины имеют ограниченную память, так что рано или поздно алгоритм либо остановится, либо войдёт в состояние, которое уже было.
Ты подменяешь рассмотрение алгоритма конкретной его физической реализацией, это ошибка.
Теоретически, конечно, да. Любая физическая машина это конечный автомат, меньше по мощности чем МТ. Там не только объём памяти ограничен, но и количество шагов, которые машина способна выполнить, хотя бы из-за ограниченности доступного кол-ва энергии. Так что тут сомнений нет — любой алгоритм на любой физической машине завершается рано или поздно. Но это не делает сам алгоритм конечным и нисколечко не помогает обойти проблему неразрешимости.
К тому же, практически, если прикинуть количество состояний хотя бы для одного жалкого килобайтика памяти, то становится всё очень печально и использовать МТ для моделирования физических машин оказывается более адекватным.

Так что физические машины имеют практически бесконечную ленту как в МТ.