Вещи, которые компьютеры никогда не смогут сделать

Ссылка на источник: http://www.efgh.com/math/impossible.htm

Филипп Я. Эрдельский

Впервые опубликовано в журнале доктора Добба в мае 1987 г.

Пожалуйста, присылайте комментарии, исправления и дополнения веб-мастеру по адресу pje@efgh.com.

У любого, кто был свидетелем огромных улучшений компьютеров за последние 40 лет, может сложиться впечатление, что компьютеры в конечном итоге смогут решить каждую четко определенную проблему. Прогресс в понимании языка и других формах искусственного интеллекта разочаровывает, но человеческий язык полон двусмысленностей, так что это не является четко определенной проблемой. Шахматы, с другой стороны, очень хорошо определены. Хотя когда-то это считалось воплощением интеллектуальной деятельности, компьютеры теперь могут играть в шахматы лучше, чем все, кроме нескольких человек.

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

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

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

Алан Тьюринг в 1935 году спросил, существует ли метод, с помощью которого компьютерная программа может определить, остановится ли любая другая компьютерная программа. Это знаменитая «проблема остановки». Тьюринг показал, что у него нет решения.

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

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

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

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

Сам Тьюринг предложил минимальную машину, которая стала называться машиной Тьюринга. Его память должна была быть бесконечно длинной, но шириной всего в один бит, и у машины был только последовательный доступ к ней, как с лентой. Язык программирования по сути представлял собой блок-схему с несколькими базовыми командами. Тем не менее, Тьюринг показал, что его машина способна эмулировать любую другую машину, учитывая достаточно времени и подходящую программу. Такая конструкция не нужна для наших целей – вы можете себе представить, что компьютер запрограммирован на некотором знакомом языке высокого уровня.

Теперь рассмотрим проблему определения, может ли программа распечатать указанную строку S (с другим выводом или без него). Если вы можете решить проблему остановки, вы можете решить эту проблему. Просто замените каждый оператор печати в программе подпрограммой, которая не отправляет вывод на принтер, но отслеживает вывод и останавливает, когда появляется строка S. Затем, чтобы предотвратить остановку программы по любой другой причине, замените все операторы остановки в программе бесконечными циклами. Тогда решите проблему остановки для результата.

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

Поскольку это относится к любой строке S, вы также можете определить, печатает ли программа свою копию. Это не так любопытно, как кажется на первый взгляд. Легко написать программу из 1000 символов, которая распечатывает все комбинации из 1000 символов, включая себя. Фактически, 1000 символов – это, вероятно, завышенная оценка количества символов, необходимого для большинства языков высокого уровня

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

Эта программа, в процессе генерации всех программ, в конечном итоге будет генерировать себя. Распечатывает ли она свою копию? Если это так, то это нарушает правило, распечатывая копию программы, которая печатает саму копию. Если это не так, он нарушает правило, не распечатывая копию программы, которая не распечатывает копию самой себя. Это фатальное противоречие доказывает, что проблема остановки не имеет решения.

Вы можете признать это как парадокс Рассела (набор всех наборов, которые не содержат себя) или как парадокс парикмахера (парикмахер, который бреет каждого человека, который не бреет себя).

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

1. определение, достигнет ли программа определенной точки (программисты Ada: именно поэтому PROGRAM_ERROR должна быть ошибкой времени выполнения, а не ошибкой времени компиляции)
2. определить, инициализируется ли переменная перед ее использованием
3. определение, является ли данный сегмент кода недоступным и никогда не будет выполнен
4. определить, делают ли две программы одно и то же

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

Невозможность определить, выполняют ли две программы одно и то же, означает, что всегда можно победить определенный вид троянского коня. В лекции, перепечатанной в «Уведомлениях о ACM» (август 1984 г.), Кен Томпсон утверждал, что он может поместить троянского коня в компилятор C, который неправильно компилирует оператор входа в систему, чтобы дать ему доступ к любой системе Unix, скомпилированной с ним, и это неправильно компилировать компилятор C, чтобы вставить его копию. Сам троян не появится в исходном коде для компилятора C. В письме в редакцию Стив Дрэйпер отметил, что такого троянского коня можно победить, перефразировав компилятор C (написав другой код, который делает то же самое), а затем перекомпилировав его. Ни один троянский конь не может безошибочно распознавать перефразированные программы – следовательно, всегда есть парафраз, который победит троянского коня.

Мое собственное мнение в этом вопросе таково, что, если бы троянский конь не был умело написан, большинство парафраз победило бы его, и на самом деле это, вероятно, было бы побеждено в результате обычного обслуживания программного обеспечения. Любой троян, достаточно умный для распознавания большинства перефразирований, вероятно, будет гораздо больше, чем остальные компиляторы Си Вы никогда не получите это через ворота.

Проблема остановки тесно связана с двумя другими проблемами, которые были поставлены математиком Дэвидом Гильбертом в 1900 году. Есть ли формальное доказательство или опровержение для каждого математического утверждения? Есть ли алгоритм для поиска доказательств?

На первый вопрос отрицательно ответил Курт Гёдель в 1931 году. Доказательство Гёделя было сложным, но если вы согласитесь с неразрешимостью проблемы остановки, это можно доказать просто. Остановка конкретной программы – математическое утверждение. Фактически, многие математические теоремы уже являются частными случаями проблемы остановки, потому что вы можете написать программу для поиска контрпримеров и остановки, когда она найдет. Теорема эквивалентна утверждению, что программа никогда не останавливается.

Если бы всегда было формальное доказательство или опровержение утверждения о том, что программа останавливается, то вы можете просто сгенерировать все доказательства (более или менее, поскольку программа, описанная ранее, сгенерировала все программы), пока не найдете либо доказательство, либо опровержение. Это решило бы проблему остановки. Поскольку проблема остановки вообще неразрешима, должно быть по крайней мере одно математическое утверждение такого рода, которое неразрешимо, то есть оно не может быть формально доказано или опровергнуто.

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

Учитывая, что некоторые математические утверждения неразрешимы, существует ли программа, «программа разрешимости», которая может определить, является ли любое математическое утверждение разрешимым, даже не решая, является ли оно истинным или ложным? Как вы уже догадались из тона этой статьи, ответ опять нет. Если у вас есть программа разрешимости, вы можете взять любую программу и спросить, останавливается ли она. Затем примените программу разрешимости к этому вопросу. Если вопрос разрешимый, поиск всех доказательств докажет или опровергнет его. Если вопрос неразрешимый, программа никогда не останавливается; в противном случае вы можете доказать, что он останавливается, просто запустив его до полной остановки.

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

Эти аргументы не являются строгими в математическом смысле, потому что слишком много было опущено. Основная часть работ Тьюринга и Геделя заключалась в формализации понятий «вычисление» и «доказательство» до такой степени, что их аргументы будут приняты математиками.

Возможно, вы уже заметили одно молчаливое предположение, которое не соответствует действительности. Программы не ограничены ограничениями памяти. Если у программы действительно есть ограничение памяти, тогда проблема остановки может быть теоретически решена – но только программой с намного большей памятью.

Вот как это можно сделать. Программа с ограничением памяти имеет только конечное число состояний. Отладчик может пошагово выполнять его, отслеживая занятые состояния. Если он занимает одно и то же состояние дважды перед остановкой, он будет бесконечно повторять одну и ту же последовательность состояний и никогда не остановится.

Для этого отладчику требуется достаточно памяти, чтобы отслеживать, какие состояния заняла программа. Для каждого возможного состояния требуется только один бит, но количество возможных состояний даже для простой программы действительно ошеломляет. Каждая комбинация битов в памяти – это другое состояние. Следовательно, программа с только 1024 байтами памяти имеет как минимум 2(1024 x 8) состояния из-за одной только конфигурации памяти, не говоря уже о флагах и регистрах. Это количество триггеров не вписывается во всю известную вселенную. Поэтому можно сказать, что проблема остановки не имеет решения даже в этом случае.

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

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