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

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

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

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

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

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

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

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

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