Каков результат X (X, X)?
Друг, который изучает чистую математику, просит, чтобы я думал о следующей проблеме.
Предположим, что существует алгоритм, названный X, который имеет 2 исходных данные: A и a_1... a_n, где стенды для arbitary алгоритма и 'a_1.. a_n' являются исходными данными A. X получает A и его исходные данные и возвращает true если с a_1.. a_n мог быть завершен, и ложь если с a_1.. исходные данные a_n попадают в бесконечный цикл (никогда концы). Как это:
A(n):
while(n<5):
write "I'm immortal!"
и результат X(A,6) верно и X(A,2) ложь.
Таким образом, каков результат X(X,X)?
Кроме того, Вы знаете, кто первое должно было представить эту проблему?
отредактированный после одного часа, думая подробно: Вы могли видеть что-то эквивалентное парадоксу Russel здесь?
7 ответов
Если он существует, он возвращает истину. Доказательство: Предположим, он возвращает false. Затем он попадает в бесконечный цикл и никогда не заканчивается. Получили противоречие.
Но гораздо интереснее программа Y, которая может быть получена из X, и которая останавливается тогда и только тогда, когда ее параметры не останавливаются . Тогда Y (Y, Y) приводит к противоречию: либо он останавливается (это означает, что он не останавливается), либо нет (в этом случае он останавливается). Следовательно, X не существует. Детали опущены, например, мы немного помахали руками, чтобы узнать, принимают ли X и Y один параметр или два.
Вопросы, связанные с этим вопросом, обсуждались в 19 веке: 10-я проблема Дэвида Гильберта (заданная в 1900 году) требует алгоритма для определения того, имеет ли какое-либо данное диофантово уравнение решение. Оглядываясь назад, это можно выразить как частный случай проблемы остановки: найти алгоритм, чтобы определить, останавливается ли поиск решения методом грубой силы или нет. Таким образом, X решит 10-ю проблему, но отсутствие X оставило 10-ю проблему открытой. Окончательно его закрыли в 1970 году, после 20 лет работы Мартина Дэвиса, Юлии Робинсон, Юрия Матиясевича и других. Гильберт полностью сформулировал «Entscheidungsproblem» в 1928 году, которая представляет собой ту же идею, что и проблема остановки, но для проверки того, верны ли утверждения в арифметике, а не для проверки того, останавливаются ли программы.
Я думаю, что Алан Тьюринг изобрел терминологию, необходимую для постановки проблемы остановки, как вы, и доказал результат (1936). Но Алонзо Черч доказал существование неразрешимых проблем в лямбда-исчислении (также 1936 г.), а теоремы Курта Гёделя о неполноте (1931 г.) сделали настолько большой фундамент, что использование его методов для получения этих результатов вычислимости было, вероятно, меньшим достижением в обоих случаях, чем формулировка проблемы были (например, изобретение лямбда-исчисления и вычислительной модели Тьюринга).
Соответствие парадоксу Рассела (1901 г.): да, доказательства имеют что-то похожее на них. В обоих случаях вы рассматриваете объект, который представляет собой предикат, оцениваемый для класса, включая сам объект («набор всех наборов, программа, которая действует на программы»). Вы предполагаете его существование, что позволяет вам создать новый объект путем изменения предиката («набор всех наборов, которые не являются членами самих себя, программа, которая останавливается, если и только если ее ввод не останавливается»), что приводит к противоречию при попытке чтобы оценить новый предикат, «примененный к самому себе». Это опровергает предположение («существует набор всех наборов», «существует алгоритм проверки остановки»).
Возможно, что в теории Топоса (или другом структурном анализе математики) есть что-то, что формализует подобие, но я не знаю, что это было бы.
Между результатами есть существенная практическая разница: отсутствие X просто доказывает, что проблема остановки не может быть решена алгоритмом, поэтому, если вы Дэвид Гильберт, вы должны пересмотреть свои ожидания относительно что возможно в математике. Парадокс Рассела доказал, что использовавшиеся в то время теории множеств были непоследовательными, поэтому, если вы Георг Кантор, вам придется переоценить каждое доказательство, которое вы когда-либо писали. Это вызвало первые формальные аксиоматические теории множеств и переформулировки работ Кантора, Дедекинда и других теоретиков множеств, которые работали с наивными определениями множеств, допускающими парадокс.
На вопрос нет ответа. Программа X не существует. Алан Тьюринг доказал, что:
Не существует полностью вычислимой функции , которая решает, останавливается ли произвольная программа i на произвольном входе x
См. Доказательство здесь: http://en.wikipedia.org/wiki/Halting_problem
Таким образом, Алан Тьюринг определил проблему остановки как «учитывая описание программы, решите, завершит ли программа выполнение или будет работать вечно». Однако здесь возникает вопрос, каков был бы результат этой программы, если бы на входе была сама программа. Причина, по которой нет фактического ответа на этот вопрос, заключается в том, что, как доказал Алан Тьюринг (см. Ссылку в этом ответе), такой программы не существует: «не существует общей вычислимой функции, которая решает, останавливается ли произвольная программа на произвольной input x "
X имеет два входа, поэтому X (X) не имеет смысла, поэтому X (X, X) также не имеет большого смысла.
Это нормально, потому что X все равно не существует (см. Другие ответы):)
Это похоже на проблему остановки, и, чтобы ответить на ваш вопрос, я считаю, что это Алан Тьюринг первым обсуждал ее (хотя я не уверен, что он действительно звонил это «Проблема остановки»).
Предположим, что X существует, поэтому:
Допустим, X - наш «невозможный» алгоритм, который сообщает, завершается ли какой-либо другой алгоритм A для данного ввода. Если мы предоставим X сам X в качестве алгоритма для анализа и набор входных данных Y для тестирования в X, например:
X (X, Y)
Мы знаем, что он вернет истину . Теперь предположим, что X принимает в качестве входных данных сам X, что означает:
Давайте посмотрим, заканчивается ли X, когда X анализирует X ... Что верно, поскольку X может анализировать что угодно. Другими словами, если бы X существовал, то X (X, X) было бы истинным.