Универсальный алгоритм Г. Лейбница и 18-я проблема С. Смейла
Новиков Н.Б.
Аспирант Института психологии РАН
Россия, г. Москва
Аннотация
В 1666 г. немецкий математик Готфрид Вильгельм Лейбниц опубликовал «Диссертацию о комбинаторном искусстве», которая стала началом его работы над проектом универсальной характеристики (универсального алгоритма). Эту характеристику он рассматривал как логику открытия, т.е. убедительный, бесспорный метод находить непреложные (вечные) истины. По мысли Лейбница, такой метод должен был заменить содержательные рассуждения исчислением на основе арифметики и алгебры, сведя поиск нового знания к формальному использованию конечного числа математических символов. Анализ причин, почему оказался недостижимым проект универсальной характеристики (универсального алгоритма) Лейбница, неожиданно приводит к 18-ой проблеме С.Смейла, сформулированной известным американским математиком в 1997 г. при изложении списка важных математических проблем.
Ключевые слова: универсальная характеристика, универсальный алгоритм, теорема Геделя о неполноте, неразрешимость проблемы остановки, история математических открытий, правдоподобные рассуждения, искусственный интеллект, 18-я проблема С.Смейла.
Abstract
In 1666, the German mathematician Gottfried Wilhelm Leibniz published his dissertation ”On Combinatorial Art”, which was the beginning of his work on the project of a universal characteristic (universal algorithm). He considered this characteristic as the logic of discovery, i.e. a convincing, indisputable method of finding immutable (eternal) truths. According to Leibniz, such a method should replace substantive reasoning with calculus based on arithmetic and algebra, reducing the search for new knowledge to the formal use of a finite number of mathematical symbols. An analysis of the reasons why the Leibniz project of a universal characteristic (universal algorithm) turned out to be unattainable unexpectedly leads to the 18th problem of S.Smale, formulated by a famous American mathematician in 1997 when setting out a list of important mathematical problems.
Key words:universal characteristic, universal algorithm, Godel's incompleteness theorem, the unsolvability of the stopping problem, the history of mathematical discoveries, plausible reasoning, artificial intelligence, the 18th problem of S.Smale.
1. Универсальный алгоритм Г.Лейбница
Столь грандиозный проект, каким является проект Г.Лейбница по разработке универсальной характеристики (универсального метода познания), не мог возникнуть на пустом месте. Великий математик имел предшественников («вдохновителей»), одним из которых был испанский изобретатель Раймунд Луллий (1235-1315), которого некоторые специалисты считают - и, скорее всего, не без оснований, - провозвестником теории искусственного интеллекта.
Р.Луллий исходил из убеждения, что в каждой области науки имеется небольшое число исходных понятий, с помощью которых выражаются бесспорные, самоочевидные положения, не нуждающиеся в аргументации и доказательствах. Из сочетания этих понятий и сформулированных с их помощью истин и возникает знание. Как же осуществить все возможные сочетания понятий, с помощью которых можно овладеть всем доступным для смертного знанием?
Р.Луллий сконструировал машину, состоявшую из системы кругов, имевших возможность вращаться. Каждый круг был поделен на секторы, окрашенные в разные цвета и помеченные латинскими буквами. Круги соединялись друг с другом, и, приводя их во вращение, можно было получить различные сочетания символов и цветов - так называемую формулу истины. Машины Р.Луллия могли работать в различных предметных областях и давать ответы на всевозможные вопросы, составлять гороскопы, ставить диагнозы болезней, делать прогнозы на урожай. В наиболее позднем варианте машина Р.Луллия состояла из 14 кругов, размеченных буквами и раскрашенных в различные цвета, которые символизировали различные понятия, элементы, стихии, субъекты и объекты знания. Круги приводились в движение системой рычагов. Поворачиваясь, они могли образовывать около 18 квадриллионов (18 х 1015) разнообразных сочетаний буквенных и цветовых «истин». Запросы в машину вводились с помощью поворота внутреннего круга, на котором были начертаны вопросы типа: Что? Почему? Из чего? и т.д. Свой метод поиска нового знания Р.Луллий назвал «Великим Искусством» («Ars Magna»).
Выражаясь современным языком, машина Р.Луллия, по существу, представляла собой механическую экспертную систему, наделенную базой знаний, устройствами ввода и вывода, естественным языком общения.
Другой предшественник Г.Лейбница - французский математик и философ Рене Декарт (1596-1650). В трактате «Правила для руководства ума» (1628) он изложил совокупность принципов, использование которых должно давать достоверное знание о природе. Р.Декарт скептически относился к наблюдению и эксперименту, отдавая предпочтение прямому усмотрению простых (самоочевидных) истин и дедукции, позволяющей выводить из этих истин новые утверждения.
Именно идеи Р.Луллия и Р.Декарта вдохновили молодого Г.Лейбница на выдвижение проекта универсальной характеристики (универсального метода), с помощью которого всё человеческое знание, включая мораль и философские истины, может получаться автоматически (Г.Лейбниц прямо указывал на связь своего проекта с замыслом Р.Луллия).
Рассматривая свою универсальную характеристику как средство для коренного преобразования всего человеческого знания, Г.Лейбниц считал, что это средство должно состоять из двух инструментов: искусственного языка науки (его-то, собственно, он и называет characteristica universalis) и исчисления умозаключений (calculus rationator). Искусственный язык науки должен быть универсальным и совершенным в следующем смысле: он должен служить средством выражения любых мыслей, должен устранять барьеры разноязычной речи, способствуя тем самым распространению научных идей, а также должен стать орудием логического анализа любых проблем. Выражения естественного языка в универсальном языке науки должны быть заменены компактными, наглядными, хорошо обозримыми и однозначно понимаемыми знаками.
Г.Лейбниц имел совершенно ясный план проведения задуманного в жизнь: нужно было свести все понятия к некоторым элементарным понятиям, образующим как бы алфавит, азбуку человеческих мыслей. Когда это удастся сделать, полагал Г.Лейбниц, станет возможным заменить обычные рассуждения оперированием со знаками. Правила такого оперирования должны быть даны во второй части «сверхнауки» - в исчислении умозаключений. Они должны однозначным образом определять последовательность выполнения действий над данными знаками и сами эти действия, так что при правильном их применении ни для каких разногласий не остается места. Эта сокровенная цель всего замысла Г.Лейбница провозглашена им в широко известном тезисе: «Единственное средство улучшить наши умозаключения состоит в том, чтобы сделать их столь же наглядными, как и у математиков, - такими, что их ошибочность можно было бы увидеть глазами, и, если между людьми возникают разногласия, достаточно было бы только сказать «Вычислим!», чтобы без дальнейших околичностей стало ясно, кто прав» [1, с.37].
Г.Лейбниц придавал важное значение представлению логических действий в виде действий над числами, то есть арифметизации логики. Ему принадлежат следующие слова: «Я заметил, что причина того, почему мы за пределами математики так легко ошибаемся, а геометры столь счастливы в своих умозаключениях, состоит лишь в том, что в геометрии и других частях абстрактной математики можно проводить проверку или последовательные доказательства, сводя всё к числам...» [1, с.38].
К настоящему времени отдельные части проекта Г.Лейбница реализованы. Как отмечает Е.М.Вечтомов [2], «заманчивая и великая мечта Лейбница во многом претворена в жизнь - осуществлена настолько, насколько это возможно. Созданы и развиваются математическая логика, теория алгоритмов, искусственные языки программирования, современные компьютеры, компьютерная математика. Продуктивен подход к исследованию разума с помощью структур программирования, что находит практическое воплощение при развитии интеллекта учащихся в рамках когнитивной информатики. Говорят даже о «перевороте в сознании», состоящем в том, что открывается новый способ изучения мышления человека, по типу компьютерного программирования» [2, с. 129].
Однако «универсальная характеристика», т. е. некая стратегия научного исследования, позволяющая автоматически открывать новые истины, так и не была найдена. Другими словами, существенная (главная) часть проекта Г.Лейбница оказалась неосуществимой, и в настоящее время не видно путей для достижения этой цели. В чем причина этого? Почему не удалось создать общий алгоритм, позволяющий постигать законы природы путем механического манипулирования символами определенного, наперед заданного алфавита? Почему истины природы нельзя выводить так же, как, например, некоторые теоремы посредством дедукции выводятся из первичных аксиом?
2. Причины неосуществимости замысла Г.Лейбница
Первое препятствие на пути воплощения мечты Г.Лейбница появилось в 1931 г., когда Курт Гедель доказал теорему о неполноте. Используя формальный математический язык Ь, т.е. некоторый конечный алфавит и правила образования последовательностей букв этого алфавита, пронумеровав все высказывания (формулы) языка Ь, К.Гедель нашел среди них высказывания, недоказуемые в рамках избранного формального языка. Поскольку этот язык относился к арифметике натуральных чисел, полученный результат свидетельствовал о существовании недоказуемых утверждений в этой арифметике. К.Гедель установил: какую бы формализацию понятия доказательства ни предъявить, всегда найдется такое утверждение, что ни оно само, ни его отрицание не может быть доказано в рамках предъявленной формализации [3].
Крупный отечественный математик Ю.И.Манин [4] оценил результат Геделя следующим образом: «Успехи математики и математизированных областей знания приводили многих глубоких мыслителей к надежде на существование нескольких универсальных законов, из которых все остальные истины могут быть выведены чисто теоретически. В европейской традиции эти надежды связаны с именами Лейбница и Декарта. До сих пор их продолжают высказывать некоторые физики, задумывающиеся над структурой наших знаний о природе. После работы Геделя, однако, мы можем быть уверенными в беспочвенности этих надежд. Если даже оставить в стороне вопрос, насколько сложен мир, мы знаем, что метод дедуктивных выводов недостаточно мощен. Его не хватает даже на то, чтобы вывести из конечного числа принципов все истинные утверждения о целых числах, формулируемые на языке школьной алгебры: таков смысл теоремы Геделя» [4, с.80].
Второе препятствие заключалось в теореме, доказанной в 1936 г. Аланом Тьюрингом. Разработав модель машины (позже названной универсальной машиной Тьюринга) и взяв на вооружение метод доказательства, примененный К.Геделем при обосновании теоремы о неполноте, А.Тьюринг приступил к решению весьма непростой задачи. Требовалось решить проблему, относящуюся к основаниям математики и сформулированную Д.Гильбертом в 1928 г.: найти алгоритм, который бы принимал в качестве входных данных описание произвольной математической проблемы и после конечного числа шагов останавливался бы и выдавал один из двух ответов: «Истина!» или «Ложь!». Другая формулировка проблемы: можно ли определить, останавливается ли некоторая машинная программа при любых исходных данных, или в некоторых случаях программа «зацикливается» (работает бесконечно долго)? А.Тьюринг - и независимо от него Алонзо Черч - доказал отсутствие алгоритма, который мог бы решить задачу остановки машины для любой программы. Поскольку остановка машины Тьюринга означает решение задачи и получение ответа, а продолжение ее работы - отсутствие ответа (отсутствие решения задачи), результат А.Тьюринга был назван «неразрешимостью проблемы остановки».
Третье препятствие вытекает из предварительных оценок вычислительных ресурсов, которыми нужно обладать, чтобы иметь в своем распоряжении универсальный алгоритм Г.Лейбница. Если мы хотим, чтобы он давал все знания о Вселенной, он должен заранее владеть этими знаниями, т.е. миллиардами миллиардов аксиом, из которых можно выводить те или иные утверждения. Предположим, что мы намерены чисто теоретически рассчитать полную картину движения некоторого набора частиц, взаимодействующих между собой. Возникает вопрос, сколько времени и сколько бумаги (или машинной памяти) нужно израсходовать для такого расчета? Материальные затраты на расчет тем больше, чем больше частиц в наборе.
По современным данным в видимой части Вселенной содержится не более 1090 атомов, а время существования Вселенной в той форме, в которой мы ее наблюдаем, равно 1018 секунд. Таким образом, если даже всю Вселенную превратить в электронно-вычислительную машину (создать «вселенский компьютер»), делающую 1 операцию за 10-17 секунд (столько времени требуется электрическому току, чтобы преодолеть расстояние, равное диаметру атома), то машина сделает за всё время существования Вселенной не более 10125 операций, или будет иметь не более 10125 ячеек памяти. Но такой памяти не хватит уже на то, чтобы записать с приемлемой точностью квантово-механическую волновую функцию системы, состоящей из 1000 частиц. Правда, можно с самого начала не пытаться решать абсолютно точно уравнение Шредингера, а перейти к менее детализированному описанию. Однако и здесь при числе частиц больше 10 000 число уравнений становится больше числа атомов во Вселенной [5].
3. Р.Пенроуз и его аргументы относительно перспектив формального описания интеллекта
Английский математик и физик Р.Пенроуз не стал анализировать вычислительную сложность гипотетического универсального алгоритма, владеющего триллионом аксиом. Он просто рассмотрел два описанных выше результата - теорему Геделя о неполноте и теорему Тьюринга о неразрешимости проблемы остановки и увидел в них то, что налагает определенные ограничения на перспективы формального описания человеческого разума и искусственного интеллекта. В книге [6] Р.Пенроуз отметил, что попытки представить работу человеческого мозга как реализацию неких строгих (детерминированных) алгоритмов, а также попытки создать системы искусственного интеллекта, успешно функционирующие на основе тех же строгих алгоритмов, совершенно беспочвенны. На самых первых страницах своей монографии английский математик и физик подчеркивает: «...В нашей способности познавать - а, следовательно, - и в нашей сознательной деятельности в целом - есть нечто, выходящее за пределы чисто алгоритмических действий.» [6, с.14].