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

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

Экспериментальная математика

На стыке физики и математики возникла экспериментальная математика: открытие новых математических закономерностей путем компьютерной обработки большого числа примеров. Такой подход не столь убедителен, как короткое доказательство, но может быть убедительнее длинного, сложного доказательства и в некоторых случаях вполне приемлем. В прошлом данную концепцию отстаивали и Дьердь Пойа (George P?lya), и Лакатош, убежденные сторонники эвристических методов и квазиэмпирической природы математики. Он применяется и обосновывается в книге ?Новый вид науки? (A New Kind of Science) Стивена Вольфрама (Stephen Wolfram), вышедшей в 2002 году.

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

Рассмотренные вопросы чрезвычайно интересны, но далеки от решения. Со времени публикации статьи о доказательстве Гёделя прошло 50 лет, а сейчас, в 2006 году, мы все еще не знаем, насколько серьезна неполнота, и не следует ли из-за нее пересмотреть математические методы. Возможно, через 50 лет ответ будет найден.

Дополнительная литература:

* Главу о Лейбнице см. в книге: Men of Mathematics. E.T. Bell. Reissue. Touchstone, 1986.

* Более полные сведения о квазиэмпирическом взгляде на математику см.: New Directions in the Philosophy of Mathematics. Edited by Thomas Tymoczko. Princeton University Press, 1998.

* G?del?s Proof. Revised edition. E. Nagel, J.R. Newman and D.R. Hofstadter. New York University Press, 2002.

* Mathematics by Experiment: Plausible Reasoning in the 21st Century. J. Borwein and D. Bailey. A.K. Peters, 2004.

* О философии Гёделя и связи его работ с трудами Лейбница см.: Incompleteness: The Proof and Paradox of Kurt G?del. Rebecca Goldstein. W.W. Norton 2005.

* Meta Math!: The Quest for Omega. Gregory Chaitin. Pantheon Books, 2005.

* Краткие биографии математиков доступны на сайте Школы математики и статистики Университета Св. Эндрю (Шотландия).

* Домашняя станица Грегори Чейтина.

.

К проблеме "вычислимости" функции сознания Е.М.Иванов

Дополнительно рекомендуются:

КМ и психика или еще раз о Пенроузе Муравьев И.П.

1. Геделевский аргумент.

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

Заметим, что "геделевский аргумент"в настоящее время поддерживается рядом известных авторов (Дж. Лукас (1), Р. Пенроуз (2,3 ) и др.) и вызвал обширную научную дискуссию (см. (4 - 11)). Все это заставляет отнестись к данному аргументу серьезно и внимательно.

Прежде чем приступить к анализу собственно "геделевского аргумента", предварительно рассмотрим формулировку, способ доказательства и смысл самой теоремы К. Геделя о неполноте формальных систем. Формулировка теоремы такова: для достаточно выразительно "богатых" формальных систем (языков) - достаточно "богатых" для того, чтобы с их помощью можно было сформулировать любые утверждения формализованной арифметики Пеано - невозможно задать дедуктику (формализованную систему доказательств), которая одновременно обладала бы свойствами полноты (т.е. доказывала бы все содержательно истинные утверждения, которые можно сформулировать с помощью данного языка) и непротиворечивости (т.е. не доказывала бы некоторое суждение вместе с его отрицанием). Иными словами, теорема Геделя утверждает, что в такого рода "выразительных" формальных языках непременно найдутся истинные, но недоказуемые утверждения - причем этот результат не зависит от конкретного выбора дедуктики. Это означает, что множество "содержательных" истин всегда превосходит по объему множество истин, доказуемых с помощью любой сколь угодно сложной формализованной системы доказательств.

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

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

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

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