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

_>>Что такое целое число в терминах МТ?
S>То же самое, что и в обычной алгебре.
Жду конфигурацию МТ, которая строит целые числа (-inf, +inf), пока без алгебры.

_>>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
S>Всем.
А именно?

_>>Кажется у этой проблемы есть общеизвестное название?
S>Да, halting problem, она же — проблема останова.
_>>Это _алгоритм_ в какой-то теории? Или неизвестно что?
_>>Я знаю, что есть бесконечное множество алгоритмов (которые конечны по определению)? А вот про бесконечные алгоритмы не слышал?
S>Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
Неформальное? Вроде как раз у бесконечных алгоритмов большие проблемы с формализацией.

S>Ну так halting problem как раз в том, чтобы понять, глядя на "вычислительный метод" (в терминологии Кнута), является ли он алгоритмом или нет.
S>Тьюринг доказал, что невозможно построить алгоритм, который бы с уверенностью определял, завершится ли произвольная МТ за конечное количество шагов на произвольном вводе.
То есть Тьюринг показал, что доказательство конечности алгоритма должно входить в определение конкретного алгоритма, иначе это не алгоритм.