Коллектив авторов - Теорема Геделя о неполноте [Фейк]

Пенроуз - один из самых строгих критиков собственных работ. Говоря о положительной программе, он то и дело подчеркивает: речь идет лишь о предположениях (5). Но ведь и предположения бывают разного качества. Например, книга "Что такое жизнь с точки зрения физики" Э. Шредингера сыграла большую роль не потому, что там объяснено, что такое жизнь, - этого еще никто не объяснил, хотя книга вышла 50 лет назад. Но эта книга стимулировала множество плодотворных идей. Точно так же и то, что нам предстоит узнать о физической основе сознания, наверняка будет сильно отличаться от первоначальных набросков, которые сделали Пенроуз и Хамерофф. Если Пенроуз прав, сам ответ будет сформулирован на языке, которого пока просто нет. И не очень рискованно предположить, что и этот ответ не будет окончательным.

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

Пределы доказуемости

Грегори Чейтин

?В мире науки? №6, 2006

Из идей сложности и случайности, впервые высказанных Готфридом Лейбницем в его ?Рассуждении о метафизике? (1686), и их подтверждения в современной теории информации следует, что невозможно создать ?самую общую теорию всего? в математике.

В 1956 году журнал Scientific American опубликовал статью Эрнста Нагеля (Ernest Nagel) и Джеймса Ньюмана (James R. Newman) ?Доказательство Гёделя?. Через два года ее авторы выпустили одноименную книгу, которая переиздается до сих пор. В те дни я был еще ребенком, но до сих пор помню трепет, который испытал, открыв ее в Нью-йоркской публичной библиотеке.

Меня поразило то, как Курт Гёдель (Kurt G?del) использовал математику, чтобы показать, что ее собственные возможности ограничены. Он опроверг высказанное около столетия назад Давидом Гильбертом утверждение о существовании полной теории математики, т.е. конечной совокупности принципов, из которых с помощью последовательного использования правил математической логики можно вывести все положения математики. Гёдель показал, что существуют истинные математические утверждения, которые не могут быть доказаны таким образом. Его выводы основаны на двух самоотносимых парадоксах: ?данное утверждение ложно? и ?данное утверждение недоказуемо?. (Более подробные сведения о теореме неполноты Гёделя можно найти на сайте Scientific American.)

Существование специфического строго определенного числа ?, которое невозможно вычислить с помощью конечной компьютерной программы, разбивает надежду на создание всеобъемлющей математической системы, в рамках которой можно строго доказать любое истинное утверждение (изображение: www.sciam.ru)

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

Сложность и законы науки

Готфрид Лейбниц, которому в Лейпциге поставлен памятник, еще 300 лет назад предвидел многие свойства алгоритмической информации (фото с сайта www.uni-leipzig.de)

В 1686 году было издано философское эссе Готфрида Лейбница (Gottfried W. Leibniz) ?Рассуждения о метафизике? (Discours de m?taphysique), в котором поставлен вопрос: как отличить факты, которые можно описать неким законом, от фактов, никаким законам не подчиняющихся? В четвертом разделе своего эссе Лейбниц высказал очень простую и глубокую мысль: теория должна быть проще данных, которые она объясняет, иначе она не объясняет ничего. Концепция научного закона становится бессмысленной, если допускает неограниченный уровень математической сложности, потому что в таком случае всегда можно сформулировать закон независимо от того, насколько случайны и беспорядочны факты. И наоборот, если единственный закон, объясняющий какие-то данные, оказывается слишком сложным, то рассматриваемые данные на самом деле не подчиняются никакому закону.

Современная математическая теория алгоритмической информации позволила дать точные количественные определения понятиям сложности и простоты. Обычная теория информации определяет объем информации числом битов, необходимых для ее кодирования. Например, для кодирования простого ответа ?да/нет? нужен один бит. В отличие от этого, объем алгоритмической информации определяется длиной компьютерной программы, необходимой для генерации данных. Минимальное число битов, необходимых для хранения программы, называется количеством алгоритмической информации данных. Например, бесконечный ряд натуральных чисел 1, 2, 3,... содержит очень мало алгоритмической информации: все числа ряда можно получить с помощью коротенькой компьютерной программы. Не имеет значения, сколько времени понадобится для выполнения вычислений и какой объем памяти придется использовать, важна лишь длина программы в битах. (Разумеется, точное значение количества алгоритмической информации зависит от выбранного языка программирования, однако для рассматриваемых в данной статье вопросов это несущественно.)