Возможно, конкретный ответ на заданный вопрос уже был дан выше (всю тему не читал, каюсь), но тем не менее.

Для ответа на вопрос, удобно рассмотреть проблему остановки в терминах множеств. Теорема Тьюринга, по сути, доказывает неразрешимость множества алгоритмов, останавливающихся на заданном наборе входных данных, являясь при этом частным случаем теоремы Райса-Успенского, которая доказывает ровно то же самое, но для любого нетривиального свойства, а не только остановки.

GC>"Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам.
GC>И не рассматривает остальные варианты.

Это называется "полуразрешающий алгоритм". Если для элементов множества существует такой алгоритм, то оно является перечислимым.

GC>Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
GC>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.

А это называется "разрешающий алгоритм". Множества, для элементов которого такой алгоритм существует, являются разрешимыми.

Диагональный аргумент, заимствованный Тьюрингом у Гёделя (который, в свою очередь позаимствовал его у Кантора), как уже сказано выше, доказывает неперечислимость множества алгоритмов, останавливающихся на заданном наборе данных. По теореме Поста, для того, чтобы оно было разрешимым, его дополнение (т.е. множество всех алгоритмов, зависающих на заданном наборе данных) должно быть перечислимым. Но с помощью того же самого диагонального аргумента можно показать неперечислимость также и дополнения, следовательно рассматриваемое изначально множество является неразрешимым.

Иными словами, "остальные варианты" (включая и упомянутый всюду определённый анализатор, который всегда останавливается) являются лишь частными случаями варианта, рассмотренного Тьюрингом, хотя это сходу, действительно, не так уж и очевидно.

Возможно, конкретный ответ на заданный вопрос уже был дан выше (всю тему не читал, каюсь), но тем не менее.

Для ответа на вопрос, удобно рассмотреть проблему остановки в терминах множеств. Теорема Тьюринга, по сути, доказывает неразрешимость множества алгоритмов, останавливающихся на заданном наборе входных данных, являясь при этом частным случаем теоремы Райса-Успенского, которая доказывает ровно то же самое, но для любого нетривиального свойства, а не только остановки.

GC>"Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам.
GC>И не рассматривает остальные варианты.

Это называется "полуразрешающий алгоритм". Если для элементов множества существует такой алгоритм, то оно является перечислимым.

GC>Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
GC>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.

А это называется "разрешающий алгоритм". Множества, для элементов которого такой алгоритм существует, являются разрешимыми.

Диагональный аргумент, заимствованный Тьюрингом у Гёделя (который, в свою очередь позаимствовал его у Кантора) доказывает неперечислимость множества алгоритмов, останавливающихся на заданном наборе данных. По теореме Поста, для того, чтобы оно было разрешимым, его дополнение (т.е. множество всех алгоритмов, зависающих на заданном наборе данных) должно быть перечислимым. Но с помощью того же самого диагонального аргумента можно показать неперечислимость также и дополнения, следовательно рассматриваемое изначально множество является неразрешимым.

Иными словами, "остальные варианты" (включая и упомянутый всюду определённый анализатор, который всегда останавливается) являются лишь частными случаями варианта, рассмотренного Тьюрингом, хотя это сходу, действительно, не так уж и очевидно.