История изменений

Да. Потому что где-то должна быть бесконечность. Машина Тьюринга потому и машина Тьюринга, что у неё по определению бесконечная лента с памятью и существует бесконечное количество программ для неё. И проблема останова как раз и говорит о том, что машина Тьюринга не может за конечное время перебрать бесконечное количество программ под саму себя.

Можно построить эквивалентное доказательство несуществования функции h(p, d), которая за конечное время отвечает на вопрос: «остановится ли вычисление p(d)» в виде «да» или «нет». Но для этого понадобится программа, которая проверяет наличие конкретной бесконечной последовательности в бесконечной последовательности бесконечных последовательностей, что те же яйца, только в профиль.

Да. Потому что где-то должна быть бесконечность. Машина Тьюринга потому и машина Тьюринга, что у неё по определению бесконечная лента с памятью и существует бесконечное количество программ для неё. И проблема останова как раз и говорит о том, что машина Тьюринга не может за конечное время перебрать бесконечное количество программ под саму себя.