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

3. Окончить процесс.

4. Перейти к п. 4.

Этот алгоритм останавливается, если рассматриваемый в качестве входа алгоритм несамоприменим, и не останавливается (зацикливает на п. 4) в противном случае.

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

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

Тогда можно построить алгоритм Н:

1. Применить Р. Перейти к п. 2.

2. Если Р дал ответ "да", перейти к п. 3, иначе - к п. 4.

3. Выполнить алгоритм Е. Конец.

4. Перейти к п. 4.

Алгоритм Н является алгоритмом, распознающим самоприменимость произвольных алгоритмов. Следовательно, он не возможен, а значит не возможен и алгоритм Е.

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

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

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

Итак, мы выяснили суть геделевского аргумента. Впервые данный аргумент был, видимо сформулирован Дж. Лукасом в 1961 году в статье (1).

В последнее время подобные идеи активно отстаивает Р. Пенроуз (2, 3, 11). Пенроуз, в частности, использует геделевский аргумент для обоснования тезиса о квантовой природе человеческого сознания. (Этот вопрос мы более подробно рассмотрим ниже). Рассмотрим вкратце ту форму, которую Пенроуз придает геделевскому аргументу.

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

Предположим, что математические способности некоторого математика (например, самого Пенроуза) полностью описываются некоторой формальной системой F. Это означает, что любое математическое утверждение, которое Пенроуз признает "неоспоримо верным", является теоремой, доказываемой в F, и наоборот. Предположим, также, что Пенроуз знает, что F описывает его математические способности. Пенроуз, также, полагает, что тот факт, что F описывает его математические способности, - эквивалентен вере в непротиворечивость и непогрешимость F. (В противном случае мы должны были бы поставить под сомнение истины, которые представляются нам "неоспоримо истинными").

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