Если он существует, он возвращает истину.Доказательство: предположим, он возвращает false.Тогда он попадает в бесконечный цикл и никогда не заканчивается.Это противоречие.
Но более интересной является программа Y, которая может быть получена из X и которая останавливается тогда и только тогда, когда ее параметры не останавливаются.Тогда Y (Y, Y) приводит к противоречию: либо он останавливается (имеется в виду, что он не останавливается), либо нет (в этом случае это происходит).Следовательно, X не существует.Детали опущены, например, мы немного махали рукой, что X и Y принимают один или два параметра.
Вопросы, связанные с этим вопросом, обсуждались в 19 веке: 10-я проблема Дэвида Гильберта (задается в 1900 г.) запрашивает алгоритм, чтобы определить, имеет ли решение какое-либо данное диофантово уравнение.Оглядываясь назад, это может быть выражено как частный случай проблемы остановки: найдите алгоритм, чтобы определить, останавливается ли поиск грубой силы для решения или нет.Таким образом, X решит 10-ю проблему, но отсутствие X оставило 10-ю проблему открытой.Он был окончательно закрыт в 1970 году, после 20 лет работы Мартина Дэвиса, Джулии Робинсон, Юрия Матиясевича и других.Гильберт полностью сформулировал «проблему Entscheidungs» в 1928 году, которая является той же идеей, что и проблема остановки, но для проверки правильности утверждений в арифметике, а не для проверки, останавливаются ли программы.
Я думаю, что Алан Тьюринг изобрел необходимую терминологиюсформулировать проблему остановки, как у вас, и доказал результат (1936).Но Алонзо Чёрч доказал существование неразрешимых проблем в лямбда-исчислении (также 1936), и теоремы Курта Гёделя о неполноте (1931) сделали так много, что использование его методов для получения результатов вычислимости, вероятно, было меньшим достижением в обоих случаях, чем формулировкапроблемы были (например, изобретение лямбда-исчисления и вычислительной модели Тьюринга).
Актуальность для парадокса Рассела (1901): да, доказательства имеют нечто похожее на них.В обоих случаях вы рассматриваете объект, который представляет предикат, оцененный в классе, включая сам объект («набор всех наборов, программа, которая действует на программы»).Вы предполагаете его существование, позволяя вам создать новый объект путем изменения предиката («набор всех наборов, которые не являются членами самих себя, программа, которая останавливается тогда и только тогда, когда ее ввод не останавливается»), приводя к противоречию при попыткеоценить новый предикат, «примененный к себе».Это опровергает предпосылку («существует множество всех наборов», «существует алгоритм для проверки остановки»).
Возможно, в теории Топоса (или другом структурном анализе математики) есть нечто, что формализуетсходство, но я не знаю, что это было бы.
Между результатами есть существенная практическая разница: несуществование X просто доказывает, что проблема остановки не решаема алгоритмомтак что если вы Дэвид Гильберт, вам придется пересмотреть свои ожидания относительно того, что возможно в математике.Парадокс Рассела доказал, что теории множеств , используемые в то время, были противоречивы, поэтому, если вы Георг Кантор, вам придется переоценивать каждое доказательство, которое вы когда-либо написали.Это спровоцировало первые формальные аксиоматические теории множеств и переосмысление работ Кантора, Дедекинда и других теоретиков множеств, которые работали с наивными определениями множеств, которые допускали парадокс.