Тьюринг. Компьютерное исчисление. Размышления о думающих машинах - [5]
А = [2+3=5] => [А истинно]
С другой стороны, если кто-то предложит утверждение «2∙3 = 8», мы скажем, что это утверждение ложно:
В = [2∙3=8]=> [В ложно]
Однако существуют утверждения, при установлении истинности или ложности которых мы сталкиваемся с парадоксом: утверждение начинает противоречить самому себе. Например, великий философ Сократ, говоря: «Я знаю, что ничего не знаю», противоречил сам себе, так как если Сократ знает, что «ничего не знает», значит, он «уже что-то знает». Классический пример, переводящий ситуацию из математической области в лингвистическую, называется парадоксом лжеца.
Гедель перенес этот парадокс из языка в математику, в частности в сферу логики, доказав в 1931 году теорему о неполноте, описывающую неполные системы, истинность или ложность утверждений которых мы не можем установить. Невероятно захватывающим представляется вопрос о том, как эти философские рассуждения, па первый взгляд далекие от реального мира, заставили поколебаться основы математики.
Представьте, что мы выражаем на математическом языке следующее утверждение G:
G = [это утверждение не истинно].
Если мы установим, что утверждение G истинно, мы подтвердим, что оно ложно. И наоборот, если мы решим, что G ложно, это будет означать, что G истинно. Этот парадокс имеет место в самореферентных системах, к которым принадлежит и фраза в описанном примере, и такой ее вариант, как «Я лгу». В результате мы получаем странную петлю. Независимо от того, как мы будем рассуждать, мы всегда приходим в ту же точку, откуда начали. Другими примерами самореферентности являются рука, рисующая руку, на знаменитой картине Эшера, синтез белков и ДНК клетки или «микрофон, слушающий колонку», представленный в книге Дугласа Хофштадтера «Я странная петля»(I am a strange loop).
«Рисующие руки» (1948), Мауриц Корнелис Эшер.
В тот период некоторые ученые сформулировали следующий вопрос: может ли математическая интуиция быть кодифицирована в свод правил, или (па современном языке) в компьютерную программу? Необходимо было понять, возможно ли создание механического разума, сегодня именуемого компьютером, с помощью которого мы сможем автоматически исследовать или доказать без вмешательства человека истинность или ложность какого-либо математического доказательства или утверждения. Например, для того, что мы сегодня называем искусственнглм интеллектом, не существует системы правил для вычисления или вывода, которая позволила бы определить с помощью программы свойства натуральных чисел. Натуральные числа N = [1, 2, 3, 4, ...], которые мы используем для счета элементов целой величины, например количества яблок, имеют определенные свойства.
Пусть a, b и с будут числом яблок, равным 2, 3 и 5 соответственно. Свойство ассоциативности устанавливает, что (а + 6) + с = а + (b + с), в то время как согласно свойству дистрибутивности а • (b + с) = а • b + а • с. Если мы представим эти два свойства натуральных чисел в виде утверждений, назвав ассоциативность утверждением H, а дистрибутивность — утверждением /, и заменим а, b и с их числовыми выражениями
Н = [(2 + 3) + 5 = 2 +(3 + 5)] => [Н является...],
I = [2 • (3 + 5) = 2 *3 + 2 • 5] => [I является...],
станет очевидно, что не существует программы для компьютера или какой-либо другой машины, которая могла бы автоматически доказать или опровергнуть этот тип утверждений. Как это ни удивительно, но написать программу для компьютера, которая доказала бы то, что очевидно даже ребенку школьного возраста, а именно (2 + 3) + 5 = 2 + (3 + 5), невозможно, поэтому в математике существуют «истинные утверждения» о числах, которые не могут быть доказаны с помощью правил дедукции. Как можно себе представить, теорема Геделя заставила пошатнуться казавшиеся непоколебимыми идеи Бертрана Рассела и сами столпы формальной математической науки, которыми так гордятся ученые.
Один из самых влиятельных математиков XIX — начала XX века, немец Давид Гильберт сказал, что вся эта дискуссия сводится к проблеме определения, то есть возможности установить последовательность или непоследовательность формальной системы. Это означает, что до сих пор математики делали свою науку, используя правила вывода и аксиомы, то есть идеи или утверждения, считающиеся очевидными и не требующие доказательств. В этой ситуации Гильберт поставил перед научным сообществом задачу создать механический процесс (на современном языке — «информатизированный процесс»), с помощью которого можно было бы принять решение об истинности или ложности математического утверждения. Необходимо было оставить теоретическую дискуссию, начатую Геделем, и найти реальное решение проблемы, так как на кону стояла честь математики как науки. Алан Тьюринг принял этот вызов и начал работать над решением проблемы, поставленной Гильбертом и ставшей, в свою очередь, ответом на теорему Геделя. Так Тьюринг создал абстрактный исполнитель, не имеющий реального прототипа, — а-машину (automatic machine). Это устройство, известное нам как машина Тьюринга, обязано своим происхождением дискуссии между философами и математиками на самом высоком уровне. Сегодня считается, что это теоретическая модель первого в истории науки компьютера. Однако, несмотря на гениальность идей, возникших у Тьюринга в 1937 году, они не могли получить материального воплощения. К сожалению, потребовался глобальный военный конфликт (Вторая мировая война) для того, чтобы математики и инженеры объединили свои усилия для разработки и создания удивительной машины — компьютера.
