Алан Тьюринг и сила негативного мышления
Диагональное доказательство Тьюринга — это версия этой игры, в которой вопросы проходят через бесконечный список возможных алгоритмов, неоднократно задаваясь вопросом: «Может ли этот алгоритм решить проблему, неисчислимость которой мы хотим доказать?»
«Это своего рода бесконечный вопрос», — сказал Уильямс.
Чтобы выиграть игру, Тьюрингу нужно было сформулировать задачу, ответом на которую для каждого алгоритма было бы «нет». Это означает указание определенного входного сигнала, который заставляет первый алгоритм выдавать неверный ответ, другого входного сигнала, который приводит к сбою второго алгоритма, и так далее. Он нашел эти частные записи, используя трюк, похожий на тот, который недавно использовал Курт Гёдель. Доказывать Самореферентные утверждения, такие как «Это утверждение недоказуемо», создают проблему для основ математики.
Основная идея заключалась в том, что каждый алгоритм (или программу) можно представить в виде последовательности нулей и единиц. Это означает, как и в примере с проверкой ошибок, что алгоритм может принимать на вход код другого алгоритма. В принципе, алгоритм может принимать на вход собственный код.
С этой точки зрения мы можем определить невычислимую задачу, подобную той, что содержится в доказательстве Тьюринга: «Для входной строки, представляющей код алгоритма, выходной сигнал равен 1, если этот алгоритм выдает 0, когда его код является входным; в противном случае выход равен 0». Каждый алгоритм, который пытается решить эту проблему, будет выдавать неверный результат хотя бы на одном входе, то есть на входе, соответствующем его коду. Это значит, что эту вредную проблему вообще невозможно решить никаким алгоритмом.
Чего не может сделать отрицание
Ученые-компьютерщики еще не завершили процесс диагонализации. В 1965 году Йорис Хартманис и Ричард Стернс адаптировали аргумент Тьюринга к… Доказывать Не все арифметические задачи одинаковы, а некоторые по своей сути сложнее других. Это открытие положило начало развитию теории сложности вычислений, которая изучает сложность вычислительных задач.
Но теория сложности также выявила ограничения обратного метода Тьюринга. В 1975 году Теодор Беккер, Джон Гейл и Роберт Солови. Доказано Многие открытые вопросы теории сложности никогда не могут быть решены только с помощью диагонализма. Наиболее важной из них является знаменитая проблема P и NP, которая спрашивает, легко ли решить все проблемы с легко проверяемыми решениями с помощью правильного оригинального алгоритма.
Слепые пятна диагонализма являются прямым результатом высокого уровня абстракции, который делает его таким мощным. Доказательство Тьюринга не включало в себя какую-либо невычислимую задачу, которая могла бы возникнуть на практике; вместо этого он быстро придумал такую задачу. Другие диагональные доказательства также далеки от реального мира, поэтому они не могут решить вопросы, где важны детали реального мира.
«Они выполняют расчеты удаленно», — сказал Уильямс. «Я представляю себе человека, работающего с вирусами и получающего к ним доступ через перчаточный ящик».
Неудача диагонализации была ранним индикатором того, что решение проблемы P и NP будет настолько Долгая поездка. Но, несмотря на свои ограничения, отчуждение остается одним из ключевых инструментов в арсенале теоретиков сложности. В 2011 году Уильямс использовал его вместе с рядом других методов для достижения этой цели. Доказывать То, что определенная ограниченная модель вычислений не может решить некоторые очень сложные проблемы – результат, который ускользал от исследователей в течение 25 лет. Это было далеко от решения P против NP, но все равно представляло собой значительный прогресс.
Если вы хотите доказать, что что-то невозможно, не стоит недооценивать силу простого отказа.
Оригинальная история Перепечатано с разрешения Журнал Кванта, Редакционно независимое издание Фонд Симмонса Его миссия состоит в том, чтобы улучшить общественное понимание науки, освещая научные разработки и тенденции в области математики, физики и наук о жизни.