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

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

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

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

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

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

Машина Тьюринга - это воображаемое вычислительное устройство (машина) способная с помощью простейших операций перерабатывать некоторые последовательности символов в другие последовательности. Машина Тьюринга состоит из трех частей: 1. Бесконечной в обе стороны ленты, разделенной на ячейки; 2."Головки", которая способна выполнять следующие три операции: считывать символ, записанный в ячейке ленты, записывать символ в ячейку и перемещаться вдоль ленты на одну ячейку влево или вправо; 3.Логического блока - который управляет действиями "головки" в соответствие с некоторой "программой".

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

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 - состояние, в которое переходит логический блок после осуществления предшествующих двух операций.