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

_>Что такое целое число в терминах МТ?
То же самое, что и в обычной алгебре.

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

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