Проблемы в области искусственного интеллекта. Марвин Л. Минский. Массачусетский технологический институт, Кембридж, Массачусетс

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

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

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

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

Ниже мы рассмотрим некоторые из тех областей, где ощущается необходимость в математических формулировках и анализе. Многие другие серьезные проблемы, такие как распознавание образов, планирование, теория нейронных сетей, моделирование решения задач человеком, здесь не затрагиваются. Достаточно подробным введением во всю эту область могут служить статьи [13, 14]; там же приведена подробная библиография.

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

Однако наши знания в области построения вычислительных машин непрерывно возрастают, и сегодня уже кое-что известно о том, как заставить машины решать нетривиальные логические, математические и некоторые другие - менее формальные задачи. Совокупность таких методов решения называется эвристическим программированием. Эвристика в обычном понимании этого слова есть улучшение метода решения, позволяющее превзойти, в смысле некоторого критерия, методы перебора. (Если можно так сказать, эвристика с некоторой вероятностью приводит к неудаче при решении одних задач, зато обеспечивает неизменный успех в решении других.) Во многих специальных областях существуют систематические разрешающие процедуры, которые для нетривиальных задач дороги, и их надо упрощать с помощью эвристических методов. Иногда невыполнимый из-за большого объема перебора поиск может быть сделан вполне приемлемым за счет правильно выбранного порядка испытаний. В любом случае для разумного распределения усилий необходимо вводить некоторую структуру подзадач. Общий обзор проблем в этой области дан в статье [13], а в качестве примера дальнейшего развития этой темы можно указать работы [17, 18].

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

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

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

К сожалению, при таком программном описании мы не располагаем дедуктивными методами, сравнимыми с дедуктивными методами классической математики. Возможно, когда-то этот недостаток будет частично преодолен, и мы найдем мощные методы, которые дадут возможность делать выводы о результатах работы программ. Мак-Карти [9] указал некоторые направления, по которым могли бы пойти в будущем теории (нечисловых), вычислений. В любом случае используемое нами программное описание дает некоторую компенсацию за потерю замкнутых методов решения (которых иногда может и не быть). Программа вместе с соответствующими параметрами может быть введена в машину и реализована. Таким образом, исследователь может ответить на многие специальные вопросы о поведении системы, ограничившись лишь непротиворечивыми, обычно выполняющимися, предположениями. Конечно, это лишь вспомогательный эвристический метод для нахождения теорем, но для сложных систем интуиция без вспомогательных методов не очень хороша. Биолог может использовать такие вспомогательные методы (моделирование), для того чтобы проверить, насколько хорошо предложенное им описание соответствует поведению биологической системы, по крайней мере с его точки зрения. И значительно менее вероятно, что он сможет, взглянув на запутанную систему уравнений, оценить, насколько они соответствуют поведению его системы (за исключением весьма тривиальных случаев).

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

Проблема распределения усилий при эвристическом программировании. Решение трудных задач по определению не может быть найдено за один шаг. Любая такая задача сначала должна быть разбита на подзадачи или упрощена какими-либо иными способами. Полученные подзадачи в свою очередь тоже могут быть разбиты на подзадачи. В результате при решении сложной задачи мы должны строить сильно разветвленное дерево частных задач и целей, подзадач и подцелей. Некоторые из задач окажутся связанными условием "ИЛИ", т. е. для достижения цели достаточно решение любой задачи из этой группы. Некоторые образуют группу "И", т. е. должны быть решены все входящие в такую группу задачи. Оценки достаточности набора решенных задач при текущем накоплении данных могут быть и более сложными. В так называемых последовательных задачах могут быть введены ограничения на порядок решения задач, а решение одной задачи может влиять так или иначе на сложность другой.

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

Проблема распределения усилий порождает интересные вопросы, многие из которых допускают изучение, не связанное с той конкретной областью, из которой взята задача, возможно в форме теории функций статистических решений. Здесь сделано весьма мало, и большинство эвристических программ используют для выбора следующей подзадачи лишь простейшие схемы установления очередности. Естественно, что в группе "ИЛИ" надо первой пробовать решать ту из задач, которая кажется проще. Для группы "И" вопрос сложнее. Начинать ли с простейшей из задач на том основании, что в случае неудачи будет потеряно минимальное время? Или начинать с самой трудной на том основании, что она, скорей всего, и будет решающей, и если все задачи удастся решить, а ее нет, то все время будет потеряно напрасно? При решении последовательных задач приходится идти на компромисс между оценками трудности и налагаемыми ограничениями; в других случаях можно решать первой ту из задач, решение которой налагает наименьшие ограничения, оставляя наибольшую свободу действий для решения остальных.

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

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

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

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

Весьма похоже, что между стимулами, часто появляющимися вместе, образуется какая-то связь со специальными компонентами внутреннего состояния. Теории таких явлений нет, хотя в ней и ощущается острая потребность. Каким разумным условиям должна удовлетворять группа стимулов, чтобы ее стоило опознавать как образ с помощью специального "распознающего устройства" или, быть может, образовать "клеточный ансамбль" в нейронной структуре? (См. [5].) Анализ "ассоциативных" типов обучения почти не проводился.

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

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

В случае дорогих испытаний приходится особенно много думать над каждым экспериментом, а обучение, по-видимому, должно принимать форму позитивного решения, основанного на результатах эксперимента, специально предназначенного для проверки уже сформулированной гипотезы. Элементарное обучение, состоящее в отборе и накоплении результатов хороших попыток из множества плохих, теперь должно быть заменено более продуманной стратегией. Есть основания считать, что, например, хороший игрок в шахматы может просматривать лишь некоторые из возможных позиций - порядка десятков или сотен. Он рассматривает лишь те ходы, которые позволяют достичь существенных результатов. Его обучение должно носить явно выраженный индуктивный характер, и каждая ситуация должна вести к каким-то обобщениям. Можно объяснять некоторые общие черты обучения игре и на основе оптимизации стратегии с помощью подбора коэффициентов, как это делается в работе [19] для игры в шахматы. Вопрос состоит в том, насколько далеко можно идти в этом направлении и где именно подбор коэффициентов при обучении должен уступить место более тонким методам анализа.

Поиск и извлечение необходимой информации из больших массивов. При усложнении эвристических программ нахождение необходимой информации становится серьезной проблемой. Доказательства гипотез и предложений приходится извлекать из больших массивов утверждений как относительно специальной области, к которой принадлежит рассматриваемая задача, так и общих методов, применяемых при решении. Основной проблемой является поиск утверждений, относящихся к поставленному вопросу. Далее, необходимо извлекать утверждения группами, из которых предстоит делать выводы, так как непосредственно применимые утверждения не могут быть запасены на все случаи жизни (см. [7]). При большой библиотеке данных даже простой поиск становится весьма трудным делом, и при последовательном просмотре нет надежды охватить какую-либо заметную часть всех разделов. Хотя в некоторых специальных областях возможности эвристических программ уже приближаются к способностям человека, при работе с большими массивами данных, по-видимому, нет аналогичных достижений. Люди же хорошо справляются с такими задачами, и было бы весьма ценно выяснить, какие механизмы при этом ими используются. Несомненно, что это какие-то формы параллельного поиска в активной системе памяти с большим числом связей. Однако возможно, что и последовательная система с подходящей индексацией и использованием эвристических методов поиска позволит добиться неплохих результатов.

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

Такие задачи требуют применения методов, связанных с оценкой правдоподобия. При этом даже в случае небольших обобщений необходимо использовать эвристические методы. Кроме того, необходимо уметь определять, в какой степени уменьшается достоверность, если при дедукции сделаны неверные шаги. Для всего этого нужны новые идеи относительно неформального семантического дедуктивного анализа. Быть может, начинания Пойа в области исчисления правдоподобия можно будет развить в систему, пригодную для вычислительных машин (см., например, [4]), которые выдают ответы на некоторые вопросы (заданные в словесной форме) относительно хорошо организованных массивов данных. Эти программы являются шагами к нахождению информации по семантическим признакам, но они порождают больше вопросов, чем дают ответов. Несомненно, что даже и без формальных теорий мы будем прогрессировать в этом направлении, однако хорошее математическое обоснование позволило бы значительно ускорить это движение вперед.

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

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

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

Мы ничего не можем предложить для этой цели, кроме "бритвы Оккама"^* в той или иной форме. При прочих равных условиях генератор должен выдавать гипотезы в порядке их простоты. Однако понятие простоты влечет за собой некоторые эвристические заключения об области, к которой относится задача. Естественно спросить, существуют ли достаточно общие эвристики такого рода. Окончательной оценкой эвристической индукции может быть лишь предсказанная оценка ее пригодности для некоторого множества возможных областей, а это уже предполагает определенные заключения о классе задач, которые будет успешно решать машина. Здесь возможно несколько различных подходов; приводимые ниже соображения основаны в значительной мере на идеях Соломонова [20].

^* ("Бритва Оккама" - известный афоризм Оккама (английский схоласт XIV в.): "Сущности не преумножаются без нужды" (entia non sunt multiplicanda praeter necessitatem - лат.).- Прим. ред.)

1. Простота и упорядочивание. Хотя даже при окончательном анализе упорядочивание по простоте должно проводиться для каждого случая отдельно, в практически интересных случаях обычно появляются некоторые закономерности. Зачастую для рекурсивно определенного набора правильно сформулированных выражений находятся "естественные" способы упорядочивания, основанные на длине выражений, их глубине, определенной по вхождениям связок или композиций, и аналогичных характеристиках. Иногда могут быть построены и более сложные иерархические структуры, основанные, например, на сложности вычисления функций, относительной легкости их упрощения и сходимости. В теории рекурсивных функций уже много известно об иерархиях, связанных с относительной неразрешимостью и выводимостью, однако трудно усмотреть эвристические приложения этих теорий. Если для вычислимых функций могут быть построены такие структуры, то это указывает на их несомненную ценность.

Философская литература изобилует частично формализованными теориями установления критериев простоты, и возможно, что некоторые из них можно было бы превратить в полезные эвристические генераторы гипотез и фильтры.

2. "Синтаксическая", или "грамматическая", индукция и обобщение. Пусть некоторая формальная система содержит два подмножества "хорошо сформулированных" выражений. Одно подмножество содержит только истинные, или "полезные", утверждения, а другое - лишь ложные, или "бесполезные".

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

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

3. Индукция с помощью эффективного кодирования. Рассмотрим несколько отличную форму проблем индуктивного вывода. Предположим, что нам дана достаточно длинная последовательность символов и что задача состоит в предсказании последующих символов этой последовательности. Это обычная задача для тех случаев, где требуется оценивать вероятности по индукции. Задача эта несколько освежена введением современного понятия универсальной вычислительной машины и составленного для нее языка программирования. Программа называется допустимой, если, получив ее, машина печатает последовательность, пусть даже бесконечную, которая начинается с заданной конечной последовательности символов. Таким образом, каждая допустимая программа осуществляет предсказание. С помощью "бритвы Оккама" можно выбрать простейшую из таких последовательностей символов и обосновать предсказание. (В более общем случае можно оценить различные предсказания по простоте реализующих их команд. При этом оценка может осуществляться с помощью весовых функций.) Если в качестве функции простоты выбрана длина команды, то отыскивается минимальное описание, т. е. оптимально эффективный способ кодирования анализируемой последовательности символов.

Этот метод индукции будет представлять интерес только в том случае, если удастся показать его инвариантность по отношению к выбору определения универсальной машины. Такой инвариантности нет даже по отношению к любой фиксированной паре последовательностей символов, поскольку можно указать машину, которая выдаст весь первый набор при очень короткой программе, а второй - лишь при очень длинной. Однако представляется оптимистичным тот факт, что структуры, порождаемые в пространстве последовательностей символов, обладают инвариантностью в смысле "почти всюду" или в "достаточно большой области". Структуры, порождаемые двумя различными универсальными машинами, не могут очень сильно отличаться друг от друга. Обратимся к "теореме перевода", согласно которой произвольная программа для одной машины может быть преобразована в эквивалентную программу для другой машины с помощью некоторого стандартного "текста". Этот текст-транслятор заставляет вторую машину моделировать поведение первой при работе с остальной частью вводимой в нее информации. Тогда для последовательностей символов, значительно более длинных, чем этот текст-транслятор (а также транслятор для обратного перевода), выбор между двумя машинами не может сильно повлиять на порождаемую структуру. Было бы интересно узнать, можно ли формализовать эти интуитивные представления.

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

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

Теория автоматов. Теория машин с конечным числом состояний достаточно хорошо разработана, и исследователи, работающие в области создания искусственного интеллекта, зачастую интересуются этой теорией. Непосредственные приложения к конструированию и программированию вычислительных машин имеют работы по теории контактных сетей, а также работы по описанию поведения конечных автоматов (см. [12, 6]).

Трудно обосновать приложимость этих результатов, вытекающих из конечности числа состояний, к проблеме искусственного интеллекта. Число состояний современных вычислительных машин несравнимо больше числа состояний, используемых при любом реальном вычислении. (Для больших вычислительных машин число состояний по порядку величины равно 2²²⁰.) Вполне возможно, что для такой машины можно составить программу, с помощью которой машина достигнет в интеллектуальной области лучших результатов, чем человек; сейчас, однако, нельзя оценить правдоподобность этого утверждения.

Еще ближе к рассматриваемой проблеме результаты по минимизации функциональных схем. Эти результаты имеют отношение как к расчету надежности и эффективному конструированию машин, так и к проблемам индукции. Особый интерес представляют работы Шеннона, который показал, что функции, имеющие относительно компактное представление, должны встречаться очень редко (не из-за этого ли они и интересны?). Теория создания надежных схем из ненадежных элементов была заложена фон Нейманом [21] и продолжена в работах Мура и Шеннона [16] и Мак-Каллока [11]; она основана на замещении отдельных элементов схем целыми комплексами элементов, обладающими большей надежностью. Позднее Коуэн [2] продолжил эти работы и рассмотрел функцию переходов между состояниями как целое, что еще более интересно для целей индукции.

Теория самовоспроизводящихся машин была разработана вслед за неопубликованной работой фон Неймана, главным образом Берксом [1] и Муром [15]. Автор данной работы полагает, что их результаты имеют мало отношения к проблеме искусственного интеллекта. Это объясняется главным образом затруднениями, возникающими при описании различия между воспроизведением в обычном смысле слова и формальным определением термина "воспроизведение"; хотя, возможно, здесь различие только количественное.

Машины Тьюринга и растущие автоматы. Поскольку на практике требование конечности числа состояний не является существенным, теории вычислимости с помощью машин Тьюринга и других вычислительных устройств, не ограниченных физическими габаритами, могут оказаться более перспективными, при условии, если будут известны быстродействие и объем памяти таких устройств. Идея о применимости интерпретирующей машины для моделирования поведения другой машины, как это имеет место для универсальных машин Тьюринга, лежит сейчас в основе обычных методов программирования. К этой идее непосредственно примыкают работы по перечислению методов решений, а также проблемы, связанные с описанием разрешимых задач принятия решения. Известные нам результаты относительно неразрешимости некоторых задач оказались весьма ценными, так как здесь наша интуиция обычно беспомощна. Но для нас более ценными могут оказаться теории эффективности алгоритмов, основанные, быть может, на соотношении между необходимым временем и объемом памяти, с одной стороны, и числом аргументов вычисляемой функции - с другой. Эти теории, несомненно, заменят машины Тьюринга, используемые сейчас для практического анализа разрешимости. Здесь стоит отметить работу Мак-Карти [8] по теории рекурсивных функций символических выражений, а также некоторые другие формализмы, описанные им же в статье [9]. Эти первые работы по формальной теории вычислений открыли широкую область для математических исследований, которая, несомненно, приобретет важное значение в ближайшие годы.

Рекурсивная неразрешимость. Вопрос о соотношении между результатами о неразрешимости, например теоремой Гёделя или проблемой остановки для машин Тьюринга, и возможностями машин решать задачи был достаточно запутан как в литературе, так и в умах многих исследователей. Никем не было показано, что мозг имеет преимущество перед машинами, так как он может использовать теорему Гёделя для доказательства справедливости некоторых недоказуемых высказываний. Доводы в пользу такого утверждения опирались либо на неявное предположение, что мозг может решать задачи, не являющиеся эффективно разрешимыми, либо на неявное предположение, что "здравому смыслу" соответствует некоторая непротиворечивая метасистема (довольно рискованное утверждение). Однако нет причин, мешающих машине воспроизвести эти же самые доводы, пользуясь вышеупомянутой якобы непротиворечивой метасистемой; в этом нет ничего такого, что выходило бы за рамки обычных стереотипных доказательств.

Упомянутые работы создают впечатление, что необходимая степень сложности формальной системы, обеспечивающая ее достаточную выразительность (и вместе с тем создающая опасность ее неполноты и противоречивости), удивительно мала. Сколь же серьезна опасность парадоксов в такой системе? Кажется, что для эвристических целей вполне пригодны и противоречивая логика и противоречивый язык, при условии, что по отношению к подозрительным выражениям широко используются эмпирические правила. Математики пользуются интуицией и при этом избегают классических парадоксов, относясь с особым вниманием и подозрительностью к описанию классов и определениям с порочным кругом; таким образом, мы умеем обращаться с локально непротиворечивой логикой, применяя для каждого случая специальные ограничения. Быть может, удастся делать то же самое при помощи эвристических программ. Так, Гелернтером [3] составлена программа, доказывающая теоремы планиметрии с помощью методов Евклида. (Ложные доказательства, которые могли бы возникать при нарушении топологических аксиом Гильберта, здесь не появляются, так как программа эмпирически проверяет утверждение, производя измерения расстояний по чертежу.)

Недавно появилась область исследований, связанная с систематическим доказательством теорем с помощью метода полных или частичных решений; Ван Хао [22, 23] назвал ее "машинной математикой". Будущее определит сравнительную ценность таких и более прямых методов. Успех доказательства по-настоящему трудных теорем в математике в сильной степени зависит от плана доказательства, от конструкции лемм и изящности использования ранее полученных строгих результатов. Изучаемые сейчас систематические алгоритмы доказательства рассматриваемого типа не обладают этими качествами, и мы опасаемся, что они безнадежно затеряются среди бесконечных ветвей неудержно разрастающихся деревьев логического поиска, прежде чем принесут математике ощутимые плоды.

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

Литература

1. Burks A. W., Computation, behavior, and structure; Self-organizing systems, Pergamon, New York, 1960, стр. 282-311.
2. Cowan J., Towards a proper logic for parallel computation in the presence of noise; Symposium on BIONICS, U. S. Air Force Air Res. and Dev. Command, 1961.
3. Gelernter H., Empirical exploration of the geometry theorem machine; Proc. WJCC, 3-5 мая 1960, стр. 143-146.
4. Green B. F., Baseball: an automatic question-answerer; Proc. WJCC, май 1961.
5. Hebb D. O., The organization of behavior, New York, 1949.
6. Kleene S. C., Representation of events in nerve nets and finite automata, Ann. Math. Stud., 34 (1956), 3-41. (Русский перевод: Клини С. К., Представление событий в нервных сетях и конечных автоматах, сб. Автоматы, ИЛ, М., 1956.)
7. McCarthy J., Programs with common sense; Proc. symp. on mechanisation of thought processes, Nat. Phys. Lab., Teddington, England, Her Majesty's Stationary Office, London, 2 тома, 1959.
8. McCarthy J., Recursive functions of symbolic expressions, Comm. ACM, 3 (I960), 184-195.
9. McCarthy J., A basis for a mathematical theory of computation; Proc. WJCC, май 1961.
10. McCarthy J., Computer programs for checking mathematical proofs; Recursive function theory, Proc. Symp. Pure Math., т. 5, 1962, стр. 219-226.
11. McCulloch W. S., The reliability of biological systems; Self-organizing systems, Pergamon, New York, 1960.
12. McNaughton R., Survey of automata theory; Advances in computers, 1961.
13. Minsky M. L., Steps toward artificial intelligence; Special Computer Issue, Proc. IRE, 49, № 1 (1961), 8-30.
14. Minsky M. L., A selected descriptor-indexed bibliography to the literature on artificial intelligence, IRE Trans. Professional Group HFE, 2, № 1 (1961).
15. Мур Э. Ф., Математические модели самовоспроизведения; наст, сборник, стр. 36-62.
16. Moore E. F., Shannon С. Е., Reliable circuits using less reliable relays, J. Franklin Inst., 262 (1956), № 3, 191-208; № 4, 281-297. (Русский перевод: Мур Э. Ф., Шеннон К. Э., Надежные схемы из ненадежных реле, Кибернетический сборник, вып. 1, ИЛ, М., 1960.)
17. Newell A., Shaw J. С., Simon H. A., Report on a general problem-solving program; Proc. Internal. Conf. on Information Processing, UNESCO House, Paris, 1959,
18. Newell A., Shaw J. C, Simon H. A., A variety of intelligent learning in a general problem solver; Self-organizing systems, Pergamon, New York, 1960.
19. Samuel A L., Some studies in machine learning using the game of checkers, IBM J. Res. Develop., 3, № 3 (1959), 210-229.
20. Solomonoff R. J., A preliminary report on a general theory of inductive inference; Zator Tech. Bull., V-131 (1960).
21. von Neumann J., Probabilistic logics and the synthesis of reliable organisms from unreliable components, Ann. Math. Stud., 34 (1956), 43-98. (Русский перевод: Нейман Дж., Вероятностная логика и синтез надежных организмов из ненадежных компонент, сб. Автоматы, ИЛ, М., 1956.)
22. Wang Hao, Toward mechanical mathematics, IBM J. Res. Develop., 4, № 1 (I960), 2-22. (Русский перевод: Ван X а о, На пути к механической математике, Кибернетический сборник, вып. 5, ИЛ, М., 1962.)
23. Wang Hao, Proving theorems by pattern recognition, I, Comm. ACM, 3 (1960), 220-231