Тьюринг наконец решает, может ли компьютер решить любую поставленную перед ним задачу.

В 1920-х годах сообщество математиков считало, что они находятся на пути к окончательному открытию, которое намного превзойдет любое другое открытие. Их целью было не что иное, как создание нового общего метода, способного решить любой математический вопрос.

Давид Гильберт был первым, кто обратил серьезное внимание на эту цель. Его надгробие находится в Геттингене, городе в центральной Германии. То, что выгравировано на надгробной плите, многое говорит о его оптимизме перед этим вопросом:

Не сомневайтесь.

Неправда.

Что переводится как:

Мы должны знать.

Мы узнаем.

Именно Гильберт первым поставил вопрос о разрешимости всех проблем. Он предположил, что любая задача, поставленная правильно, может быть решена путем написания соответствующего алгоритма. Если бы Гильберт был прав, то не было бы больше неразрешимых проблем. Все, что нужно было сделать математику, — это ввести параметры задачи в метод, запустить его, и решение будет выведено. Это может быть реализовано даже в машинной форме, то есть работа математика будет состоять в том, чтобы установить некоторые входные переключатели, потянуть за ручку какой-нибудь хитроумной штуки и прочитать результат… прямо как в аналитической машине Бэббиджа. Никогда больше математику не придется говорить: «Я не знаю» или «Нет никакого способа решить это». На самом деле, если существует какой-то оракулоподобный автомат, отвечающий на каждый вопрос, нам, возможно, никогда больше не понадобятся математики!

На протяжении 1920-х и 1930-х годов группа математиков работала над поиском супералгоритма, всезнающего процесса, который мог бы ответить на любой математический вопрос. Но эти математики, которых мы можем назвать первым поколением компьютерщиков, были сильно разочарованы. Как оказалось, существуют ограничения того, что мы можем надеяться вычислить. Жесткие, фундаментальные ограничения.

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

Когда я говорил об алгоритме Евклида, я указал, что он использует итерацию и, следовательно, повторяет одни и те же инструкции до тех пор, пока не будет выполнено какое-то условие, после чего он останавливается. Я также отбросил любые возможные опасения по поводу того, что условие не будет выполнено и, таким образом, предотвратит остановку алгоритма (другими словами, попадание в бесконечный цикл). Неспособность остановиться — оправданное беспокойство. Каждый программист сегодня чрезвычайно осторожен в использовании подобных итераций и делает все возможное, чтобы программа с циклом в какой-то момент остановилась. Это не просто вопрос удобства. Программа должна остановиться, чтобы сообщить о решении. Нет остановки, нет решения. В случае отдельных алгоритмов, подобных алгоритму Евклида, это легко доказать. Но некоторые алгоритмы очень сложны, поэтому доказательство может занять много времени и быть подвержено ошибкам.

Алан Тьюринг знал об этом, поэтому он спросил, не лучше ли разработать алгоритм, который фактически принимал бы в качестве входных данных другой алгоритм, чтобы посмотреть, остановится ли он. Идея Тьюринга заключалась в методе, который мог бы анализировать алгоритм, чтобы увидеть, остановится ли он (и, таким образом, даст решение), без фактического его запуска. Чтобы пояснить этот момент, обратимся к анализируемому входному алгоритму как к программе. Алгоритм проверки останова берет программу, анализирует ее, а затем выдает либо Истина, либо Ложь в качестве вывода (Истина: входная программа остановится в какой-то момент, или Ложь: она никогда не остановится). Такой алгоритм был бы очень полезен сегодняшним программистам, потому что они никогда больше не напишут программу, которая рискует попасть в бесконечный цикл. К сожалению, сколько ни рыскай по миру, такого алгоритма не найдешь, потому что Тьюринг в 1936 году доказал, что такого алгоритма не может быть. Тем самым он одним махом доказал, что неразрешимые проблемы реальны. Его хитрость заключалась в использовании доказательства от противного.

В 1936 году Тьюринг доказал, что неразрешимые проблемы реальны.

В доказательстве от противного вы просто делаете предположение, а затем демонстрируете, что, если ваше предположение истинно, оно ведет к невозможности и, следовательно, ложно. В качестве простого примера мы могли бы доказать от противного, что треугольник может иметь не более одного прямого угла. Для этого представьте себе треугольник с тремя углами — A, B и C, а затем предположите, что оба угла A и B прямые (т. е. по 900 каждый). Однако мы знаем, что сумма внутренних углов треугольника равна 1800 (A + B + C = 1800). Если A и B сами по себе дают в сумме 1800, то C должно быть равно 00, таким образом получается треугольник только с двумя углами. Это невозможно по определению, поэтому исходное предположение должно быть неверным. КЭД!

В своем собственном случае Тьюринг начал с предположения, что остановщик действительно существует. Затем он показал, что следствие существования остановленного доказательства было бы невозможным, таким образом продемонстрировав, что остановочное доказательство не может существовать. Вот как он это сделал.

Если бы останов-доказатель существовал, он имел бы такую ​​форму:

P, D → доказательство остановки → True/False

Это соответствует той же форме, что и наша модель вычислений «ввод-процесс-вывод», о которой говорилось в предыдущих статьях. Мы берем некоторые данные (D) и вводим их в программу (P), а затем вводим их в блок проверки. Мы должны исследовать данные, потому что данные могут определять поведение программы — программа может останавливаться для одних наборов данных, но вечно зацикливаться на других. Остановка, наш процесс, сообщает нам, остановится ли программа в конечном итоге, если мы выполним ее, используя эти данные.

Следующий шаг Тьюринга был вдохновлен. Он исследовал, что произойдет, если данные, предоставленные программе, будут самой программой. Другими словами:

P, P → доказательство остановки → True/False

Как бы странно это ни звучало, передача одной программы в качестве входных данных для другой программы — это совершенно правильное действие, которое происходит каждый день в компьютерном мире.

Каковы последствия этого для нашего доказывающего остановки? Проще говоря, когда мы пытаемся использовать остановку, мы вступаем на парадоксальный путь. Давайте напишем новую программу под названием paradox, которая использует гипотетический останов-доказатель (показан на изображении выше). Эта простая, но хлопотная программа берет результаты проверки остановки и принимает решение на основе того, истинны они или нет. Если false (P остановится), то paradox также остановится. Если true (P никогда не остановится), то paradox входит в бесконечный цикл.

Теперь это становится действительно головокружительным. Мы знаем, что программа может принимать себя в качестве входных данных — что, если мы введем paradox самой себе. Когда мы делаем это, средство проверки остановок пытается проанализировать парадокс, чтобы определить, остановится ли он в конечном итоге. Есть две возможности, каждая из которых имеет последствия:

  • Если средство проверки остановок утверждает, что paradox в конце концов остановится, то paradox будет зацикливаться вечно.
  • Если остановщик утверждает, что paradox никогда не останавливается, то paradox остановится.

В данном случае мы сделали только одно предположение: существует алгоритм, который может сказать нам, остановится ли программа в конце концов. Если это единственное допущение привело к невозможному парадоксальному результату, то неизбежным выводом (в соответствии с доказательством от противного) будет то, что допущение неверно. Алгоритм доказательства остановки не может существовать. Это означает, что мы не можем проанализировать алгоритм, чтобы увидеть, разрешим он или нет. Это открытие, теперь известное как проблема остановки, доказывает, что существует такая вещь, как неразрешимая проблема, по крайней мере, с помощью любых вычислительных средств. Для тех математиков, которые искали всезнающий алгоритм, это был карательный удар.

Я точно не знаю, был ли Алан Тьюринг среди тех, кто надеялся на существование супералгоритма. Возможно, он и был, но отказывался в это верить до тех пор, пока вопрос не разрешится вне всякого сомнения. Или, может быть, он боялся будущего, в котором математики не нужны, и поэтому изо всех сил старался разрушить это представление. В любом случае, он поступил правильно. Он сделал экстраординарное предложение и сделал все возможное, чтобы оно выдержало проверку. В этом случае предложение провалилось при тестировании. Каким бы запутанным вы ни сочли пример Тьюринга с парадоксом, он продемонстрировал монументально важный факт: существуют неразрешимые проблемы.

1 Обозначение halt-prover(P, P) является более удобной альтернативой P, P → halt-prover, что означает, что P и P являются входными данными для процесса, называемого останов-доказательство.