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

Для того, чтобы записать программу для машины Тьюринга, необходимо задать:

1. Внешний алфавит а1..........аn - набор символов, которые могут быть записаны в ячейках ленты.

2. Внутренний алфавит р1...........рm - символы, которые обозначают "внутренние состояния" логического блока.

Программа для машины Тьюринга записывается в виде "функциональной таблицы":

р1

р2

р3

.................................pn

а1

.......

.......

.........

а2

axdypz

а3

.

аn

В строках таблицы располагаются тройки axdypz, где аx - символ, который машина записывает вместо а2 в ячейку, напротив которой в данный момент расположена головка, dy = d-1, d+1, d0 - предписывают движение ленты относительно головки соответственно влево, вправо или предписывают головке оставаться на месте, рz - состояние, в которое переходит логический блок после осуществления предшествующих двух операций.

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

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

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

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

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

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

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

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

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

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