Хавьер Фресан - Том. 22. Сон разума. Математическая логика и ее парадоксы

Читатель спросит, сможем ли мы, заменив первые n чисел на первые n квадратов, получить похожую формулу. Применив несколько более сложный метод, можно доказать, что

и что сумма первых n кубов рассчитывается по формуле

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

* * *

Первым успехом Тьюринга стало определение вычислимой функции. Далее всякий раз, когда мы будем говорить о функции, мы будем иметь в виду функцию, определенную на множестве натуральных чисел и принимающую натуральные значения. Напомним, что функция — это не более чем способ сопоставить каждому числу другое число, которое мы будем называть отображением первого. Чтобы лучше понять изложенное ниже, читатель может представить функцию как машину, которая придает форму закладываемому в нее материалу. Так, наша функция превращает число 3 в другое число, которое мы будем обозначать f(3), где f— первая буква латинского слова «функция». Процесс получения f( n ) по известному n может описываться последовательностью алгебраических операций или более сложной словесной формулировкой. Например, если эта функция сопоставляет каждому числу следующее за ним (как вы уже знаете из предыдущих глав, эта функция используется в аксиомах Пеано), то мы можем записать f( n ) = n + 1, и результатом будет f(3) = 3 + 1 = 4. Если же, напротив, функция определяет n -е простое число, то f(3) будет равно 3, а f(4) будет равно 7, так как первыми простыми числами являются 2, 3, 3, 7, 11. В этом случае функция задается словесным описанием, а не простой формулой, определяющей значение функции в каждой точке.

Образ машины может быть обманчивым, и читатель, возможно, поверит, что идеальная машина Тьюринга, о которой мы говорим, в состоянии вычислить значение любой функции, которую только можно себе представить. В действительности дело обстоит с точностью до наоборот: действия, скрытые между входным значением n и выходным значением f( n ), могут быть настолько сложными, что даже машина Тьюринга будет неспособна их выполнить. Чтобы читатель лучше понимал эту ситуацию, необходимо подробно объяснить, как работают машины, которые придумал Алан Тьюринг, когда ему было немногим больше двадцати лет.

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

После прочтения любого символа устройство чтения-записи может повести себя пятью различными способами: стереть ранее записанное число и записать 0, заменить записанный символ на 1, сместиться вправо, сместиться влево (чтобы эти две операции могли быть выполнены, крайне важно, чтобы бумажная лента не имела ни начала, ни конца) или просто остановиться, никак не реагируя на прочитанный символ. Последовательность действий контролируется конечной последовательностью инструкций, которые указывают, как машина должна реагировать в каждом возможном случае. Например, первая инструкция может звучать так: «Если считан символ 1, сместиться влево и перейти к третьей инструкции». Все инструкции следуют одной и той же схеме.

Принцип действия машины Тьюринга

(источник: «Complexity» Мелани Митчелл).