В замечательном произведении Аркадия и Бориса Стругацких «Понедельник начинается в субботу» есть такой диалог:
– Голубчики, – сказал Фёдор Симеонович озабоченно, разобравшись в почерках. – Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.
– Мы сами знаем, что она не имеет решения, – сказал Хунта, немедленно ощетиниваясь. – Мы хотим знать, как её решать.
– Как-то странно ты рассуждаешь, Кристо… Как же искать решение, когда его нет? Бессмыслица какая-то…
– Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица – искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен.
Решение неразрешимых задач – это не просто художественная метафора. Поспорить здесь можно лишь с тем, что этот вопрос принципиален не в меньшей степени и для практики. Как это ни парадоксально, вся область искусственного интеллекта посвящена, по сути, решению неразрешимых и плохо поставленных задач. Но что это за задачи?
Первые выводы о неразрешимости некоторых математических проблем были получены Гёделем в 1931 г. Наиболее известными являются две теоремы Гёделя о неполноте формальной арифметики. Их сущность в следующем. Если мы возьмем набор непротиворечивых аксиом, описывающих свойства чисел и арифметических операций над ними, то будут существовать некоторые утверждения о числах, которые не могут быть ни доказаны, ни опровергнуты на основе выбранных аксиом (такие утверждения называются невыводимыми). Более того, некоторые из этих утверждений являются вполне естественными истинными (с точки зрения человека) утверждениями. Чтобы «доказать» эти утверждения, приходится вводить новые аксиомы. Но какую бы мы формальную систему ни взяли, всегда найдутся утверждения об объектах системы, истинность которых не может быть установлена в рамках самой системы. Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат. Что должно это значить? Некоторые мыслители делают вывод о невозможности формализации , особенно его творческой составляющей. А поскольку машина Тьюринга – тоже формальная система, они полагают, будто невозможно реализовать на компьютере.
Действительно, некоторые задачи не имеют полного алгоритмического решения. Наиболее широко известной является проблема останова. Задача останова заключается в том, что необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается» (работает бесконечно долго). Проблема же заключается в том, что доказано отсутствие алгоритма, который бы мог решить задачу останова для любой программы. Иными словами, задача останова является алгоритмически неразрешимой. Важность проблемы останова связана с тем, что, как принято считать, некоторый алгоритм решил некоторую задачу, если он остановился, когда состояние ленты соответствует ответу. Если останова не происходит, то считается, что задача не решена, поскольку не понятно, в какой момент времени на ленте оказывается решение. Алгоритм, который решает задачу останова, тоже должен останавливаться, на чем и основывается доказательство неразрешимости проблемы останова. В этом доказательстве используется аналог парадокса лжеца. Парадокс возникает, если составить утверждение, отсылающее к самому себе. Например, является ли ложным следующее высказывание лжеца: «Я всегда лгу, даже сейчас»? Как ту же хитрость использовать для проблемы останова?..
Рассмотрим идею доказательства неразрешимости проблемы останова от противного. Пусть она разрешима, то есть существует алгоритм T, которому на вход можно подать некоторую программу, и он напечатает 0, если программа «зацикливается», и 1 – если останавливается. Рассмотрим такую программу P, которая просто вызывает алгоритм T, передавая на вход свое описание T(P), и, если алгоритм T вернул 0, алгоритм P останавливается, а если алгоритм T вернул 1, алгоритм P преднамеренно «зацикливается», запуская бесконечный цикл. Для любого алгоритма T несложно составить программу P, которая, очевидно, существует. Но что будет, если эту программу запустить? Зациклится ли она или остановится? Если программа P останавливается, тогда алгоритм T, предположительно решающий проблему останова для любой программы, при вызове T(P) должен вернуть 1, но тогда программа P должна зациклиться. Если программа P зацикливается, тогда алгоритм T(P) должен вернуть 0, но тогда программа P должна была бы остановиться. Пришли к противоречию, то есть исходное допущение о существовании алгоритма T неверно.
Существует множество и других алгоритмически неразрешимых задач. В частности, алгоритмически неразрешимой является десятая проблема Гильберта о диофантовых уравнениях, доказательство чего в 1970 году было завершено советским математиком Юрием Владимировичем Матиясевичем. Оказывается, при наличии решения, его можно получить за конечное (но неограниченное) число шагов, но если решения нет, в произвольном случае ни один алгоритм это установить не может.
Решения некоторых проблем до сих пор не найдены, и неизвестно, являются ли эти проблемы неразрешимыми. Иногда у них удивительно простые формулировки. К одной из старейших таких проблем является проблема Эйлера середины XVIII века: любое четное число не меньше четырех можно представить в виде суммы двух простых чисел (4 = 2+2,… 18 = 5+13, …). Эту проблему Эйлер сформулировал в ответ на гипотезу Гольдбаха, согласно которой любое нечетное число не меньше семи можно представить в виде суммы трех простых чисел. Гипотеза Гольдбаха была не так давно доказана, тогда как проблема Эйлера до сих пор не решена. Вероятно, это не относится к проблеме Эйлера, но некоторые математические утверждения могут быть истинные, но недоказуемые (невыводимые, алгоритмически неразрешимые) в рамках данной аксиоматики, о чем и говорит теорема Гёделя.
Неужели возможности алгоритмов настолько ограничены, и на основе компьютеров можно создать только неуниверсальный, слабый ИИ? Значит ли это, что действительно неалгоритмизуемо? Чтобы разобраться в этом, нужно учитывать ряд моментов.
Первый момент заключается в том, что алгоритмические проблемы обычно формулируются как массовые проблемы, то есть проблемы, в которых требуется найти единый алгоритм решения бесконечной серии однотипных задач. Алгоритмически неразрешимые проблемы являются «слишком массовыми», например, в проблеме останова требуется решить задачу для любого алгоритма и для любых исходных данных за конечное время. Очевидно, ни один человек не в состоянии решить задачу останова для любого алгоритма, иначе не было бы «зависающих» операционных систем и прочих программ (а ведь это еще относительно простые программы по сравнению с тем, какие невообразимо сложные программы находятся в множестве «всех алгоритмов»). Человек решает задачу останова, но делает это с ошибками, вероятность которых повышается с усложнением программ. Способность человека решать алгоритмически неразрешимые проблемы (как массовые проблемы) является крайне сомнительной. Его способность находить решения для отдельных частных случаев ничего не доказывает, ведь это под силу и компьютеру. А без этого пафосные заявления о принципиальной ограниченности компьютеров по сравнению с человеком становятся малосостоятельными.
Представьте себя в ситуации, аналогичной той, в которой оказывается программа T в нашем доказательстве. Пусть имеется автомат, который печатает 0, если вы говорите 1, и печатает 1, если вы говорите 0. И вас просят ответить на вопрос, что напечатает автомат. При этом вам разрешено сказать только 0 или 1. Естественно, автомат напечатает противоположное тому, что вы сказали, и вы об этом знаете, но ничего сделать не можете. Не кажется ли, что такая «задача» была бы просто издевательством над вами?
У такого эксперимента есть интересная практическая реализация: дело в том, что осознание многих решений происходит несколько позже (иногда более чем на полсекунды), чем это решение возникает в . Простейшие решения (выбор из двух альтернатив, скажем, поднятие правой или левой руки) можно детектировать в виде потенциала готовности еще до того, как они оказываются осознанными. В действительности, момент осознания соответствует не моменту принятия решения; он «откладывается» до момента совершения самого действия – именно поэтому мы не замечаем задержки в выполнении телом осознанных команд (у больных с нарушенным механизмом задержки может возникать впечатление, что ими управляют извне). Подобные эксперименты с использованием электромиографов, фиксирующих мышечные биотоки, а позднее – электроэнцефалографов, «считывающих» некоторую информацию прямо с , проводились, начиная с 1970-х гг. Интересно, что человека просят самого выбирать, какую руку и в какой момент поднимать, оставляя ему полную свободу воли. И, тем не менее, машина, получающая ЭЭГ-сигнал, узнает о решении испытуемого до него самого. Пусть одна рука человека означает 0, а другая – 1, и пусть машина печатает число, противоположное числу, выбранному человеком. Если испытуемому нужно будет угадать, что печатает машина, он никогда не сможет правильно выбрать ответ, хотя автомат машина будет показывать ответ почти за секунду до того, как выбор человека будет возникать в его сознании. Эта проблема «человечески неразрешима».
А ведь алгоритм T находится именно в такой ситуации: с него считывается информация о выборе, как и с в примере с человеком. Нельзя выбрать правильный ответ, когда правильность ответа меняется от самого выбора. Причем здесь мы требуем, чтобы алгоритм T обязательно напечатал 0 или 1, а в качестве входа у него выступала только программа P. Какой-нибудь другой алгоритм, «видя», что анализируемая программа сама его вызывает, мог бы напечатать и что-нибудь другое, скажем, 42. Даже если бы алгоритм T был сверхинтеллектуальным и полностью понимал ситуацию, он мог бы разве что описать экспериментаторам все, что о них думает, но правильный ответ о зацикливании программы P дать не смог бы. И дело тут вряд ли в ограниченности понятия алгоритма. Действительно, если предположить, что создано некоторое неалгоритмическое устройство, решающее проблему останова, к нему можно применить приведенные выше рассуждения, просто заменив термин «алгоритм» другим термином, например, «устройство неалгоритмического преобразования информации».
В действительности, такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. Это машины с оракулом. Под оракулом понимается некая сущность, способная «вычислять» невычислимые функции или решать алгоритмически неразрешимые проблемы. Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, который сам не сможет поднять?.. Поэтому даже если сверхтьюринговые вычисления физически реализуемы, для них также найдутся неразрешимые проблемы. Видимо, что-то не так с самой формой постановки этих проблем, неразрешимых ни алгоритмически, ни божественно.
Следует иметь в виду, что доказательство алгоритмической неразрешимости некоторой задачи зачастую заключается в сведении задачи к проблеме останова, которая неразрешима просто в силу того, что любой фиксированный алгоритм не может быть сложнее самого себя. И, тем не менее, факт существования «алгоритмически неразрешимых» проблем остается; вопрос лишь в том, как его интерпретировать.
Вторым существенным моментом является то, что выполняемые компьютерные программы, хотя и имеют форму алгоритмических процессов, не являются формальными алгоритмами. Есть важное отличие реального компьютера от машины Тьюринга – это его взаимодействие с внешним миром. В машине Тьюринга содержимое ленты фиксировано и меняется только самой машиной. В компьютер могут поступать новые данные и даже программы в процессе его работы. Как человек выходит за рамки формальных систем, например, откуда он знает, какие утверждения, невыводимые в формальной арифметике, считать истинными, а какие – ложными? Ответ прост – из опыта. Для человека «входная лента» – потенциально вся Вселенная (где на некотором языке «записаны» алгоритмы , которые , как универсальной машиной, лишь исполняются). Выбор аксиом в математике произволен, но интересные аксиомы выбираются так, чтобы описывать что-то в реальном мире. Дирак писал: «…те принципы, которые находит интересными математик, оказываются как раз теми, которые выбраны Природой». Но, по сути, математикам неоткуда брать свои аксиомы и принципы, кроме как из обобщения опыта. Более сложным является вопрос, каков алгоритм этого обобщения, и алгоритм ли это.
Искусственный интеллект, реализованный на компьютере, будет ограниченным только в том случае, если он будет полностью изолирован от мира. Тогда он действительно будет представлять собой формальную систему, к которой применим результат теоремы Гёделя, и уметь только то, что мы в него заложили. Если же для физически реализованного алгоритмического процесса «входной лентой» будет также вся Вселенная, то для него указанная постановка проблемы останова будет просто некорректной: на входной ленте у программной реализации алгоритма T кроме программы P будет еще и сам алгоритм T, и многое другое. Кроме того, программа P не сможет обратиться к работающей копии алгоритма T и только лишь вызовет другую его копию, тем самым парадокс будет снят! В этом случае выводы из неразрешимости проблемы останова, равно как выводы из теоремы Гёделя к такой программе будут просто неприменимы. Хотя это вовсе не доказывает алгоритмическую разрешимость проблемы останова, но устраняет разницу между компьютером и человеком, когда они поставлены в одинаковые условия.
Третий момент заключается в требовании к останову алгоритма. Конечно, требовать от алгоритмов остановки с выдачей результата вполне естественно для классических алгоритмов, однако нелепо требовать от искусственного интеллекта того, чтобы он спустя ограниченное время останавливался и выдавал какой-то конечный результат. Безостановочные алгоритмы обладают большей мощностью, чем классические алгоритмы и тоже могут быть вполне полезны. К примеру, такой «алгоритм» может выдать какой-то результат и продолжить работать. Многим ученым не нравится идея безостановочных алгоритмов, поскольку для них остается вопрос, когда считать, что ответ сформирован, поэтому свойства таких алгоритмов в математике исследованы меньше. Но для них можно ввести понятие «вычислимости в пределе»: если на каком-то шаге формируется ответ, который не меняется в процессе последующей работы безостановочной программы, то полагается, что задача решена. К сожалению, мало известен тот факт, что классическая проблема останова является разрешимой в пределе. Таким образом, безостановочность алгоритма потенциального искусственного интеллекта – это не плохое, а принципиально необходимое его свойство. Дело в том, что сложность безостановочных алгоритмов может неограниченно возрастать, в то время как алгоритмы, от которых требуется остановка за заранее определенное (в самом алгоритме или исходных данных) число шагов, действительно обладают ограниченными возможностями.
Итак, существование алгоритмически неразрешимых проблем и ограничения, накладываемые теоремой Гёделя на формальные системы, по-видимому, не являются бесспорным аргументом против возможности реализации сильного искусственного интеллекта как физической реализации некоторого алгоритмического процесса, но процесса безостановочного и открытого.
Имеются и другие «аргументы» против алгоритмизуемости . К примеру, часто говорится, что результат работы алгоритма полностью и однозначно определяется начальными данными, в то время как человек обладает «свободой воли». Однако детерминированность не является ключевым свойством алгоритма. Существуют вероятностные и недетерминированные машины Тьюринга, результат работы которых неоднозначен. Однако установлено, что они не расширяют понятия алгоритма в смысле алгоритмической разрешимости задач. И хотя некий источник хаоса может быть важен для реализации , идею алгоритмичности это не опровергает. Кроме того, существенной неопределенностью обладают данные, поступающие в программу из внешнего мира.
Интереснее другое: механическое применение известного алгоритма для нас не выглядит проявлением умственной деятельности. Если мы не знаем алгоритма умножения двух чисел «в столбик», то умножение каждой конкретной пары чисел для нас будет требовать интеллектуального напряжения. Но как только алгоритм известен, умножение любых двух чисел становится малоинтеллектуальной задачей. Может, – это процесс построения новых алгоритмов в случаях, когда способ решения некоторой массовой проблемы еще неизвестен?
Поиск алгоритма, решающего проблему останова и ряда других проблем в общем случае невыполним. Но это не мешает исследовать алгоритмы решения этих задач при некоторых естественных ограничениях. Зачастую поиск этих ограничений и составляет основную часть решения реальной «неразрешимой» задачи. Не зря говорят, что правильная постановка задачи составляет уже половину ее решения. Хотя пока не ясно, как реализовать приближенное решение алгоритмически неразрешимых задач, по крайней мере, теорема Гёделя не накладывает ограничений на возможность этого.
Автор: aideus
