2.2. Вычисления

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

(А) Найти число, не являющееся суммой квадратов трех чисел.

Под "числом" в данном случае я подразумеваю "натуральное число", т. е. число из ряда

0,1,2,3,4,5,6,7,8,9,10,11,12,....

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

0,1,4,9,16,25,36,...;

2.2. Вычисления 115

представленные в этом ряду числа получены следующим образом:

ОхО = 02, 1х1 = 12, 2х2 = 22, ЗхЗ = 32, 4х4 = 42, 5х5 = 52, 6x6 = б2,....

Такие числа называются "квадратами", поскольку их можно представить в виде квадратных матриц (пустой матрицей в начале строки обозначен 0):

С учетом вышесказанного решение задачи (А) может происходить следующим образом. Мы поочередно проверяем каждое натуральное число, начиная с 0, на предмет того, не является ли оно суммой трех квадратов. При этом, разумеется, рассматриваются только те квадраты, величина которых не превышает самого числа. Таким образом, для каждого натурального числа необходимо проверить некоторое конечное количество квадратов. Отыскав тройку квадратов, составляющих в сумме данное число, переходим к следующему натуральному числу и снова ищем среди квадратов (не превышающих по величине рассматриваемое число) такие три, которые дают в сумме это самое число. Вычисление завершается лишь тогда, когда мы находим натуральное число, которое невозможно получить путем сложения любых трех квадратов. Попробуем применить описанную процедуру на практике и начнем наше вычисление с нуля. Нуль равен О2+02 +02, что, безусловно, является суммой трех квадратов. Далее рассматриваем единицу и находим, что она не равна О2 + + О2 + О2, однако равна О2 + О2 + I2. Переходим к числу 2 и выясняем, что оно не равно ни О2 + О2 + О2, ни О2 + О2 + I2, но равно02 + 12 + 12. Затем следует число 3 и сумма 3 = 12 + 12 + 12; далее - число 4 и сумма 4 = О2 + О2 + 22; после 5 = О2 + I2 + 22 иб = 12+12+22переходимк7,итутобнаруживается,чтониодна из троек квадратов (всех возможных троек квадратов, каждый из которых не превышает 7)

02+02+02 02+02+12 02+02+22 02+12+12 02+12+22 02+22+22 12+12+12 12+12+22 12+22+12 22+22+22

116 Глава 2

не дает в сумме 7. На этом этапе вычисление завершается, а мы делаем вывод: 7 есть одно из искомых чисел, так как оно не является суммой квадратов трех чисел.

2.3. Незавершающиеся вычисления

Будем считать, что с задачей (А) нам просто повезло. Попробуем решить еще одну:

(B) Найти число, не являющееся суммой квадратов четырех чи

сел.

На этот раз, добравшись до числа 7, мы находим, что в виде суммы квадратов четырех чисел его представить вполне возможно: 7 = I2 + I2 + I2 + 22, поэтому мы переходим к числу 8 (сумма 8 - О2 + О2 + 22 + 22), далее - 9 (сумма 9 = О2 + О2 + + О2 + З2) и 10 (10 = О2 + О2 + I2 + З2) и т.д. Вычисления все продолжаются и продолжаются (... 23 = I2 + 22 + З2 + + З2, 24 = О2 + 22 + 22 + 42, ..., 359 = I2 + З2 + 52 + 182, ...) и завершаться, похоже, не собираются. Мы предполагаем, что искомое число, должно быть, невообразимо велико, и для его вычисления нашему компьютеру потребуется чрезвычайно большой промежуток времени и огромный объем памяти. Более того, мы уже начинаем сомневаться, существует ли оно вообще, это самое число. Вычисления все продолжаются и продолжаются, и конца им не видно. Вообще говоря, так оно и есть: описанная вычислительная процедура завершиться в принципе не может. Известна теорема, впервые доказанная в 1770 году великим французским (и отчасти итальянским) математиком Жозефом Луи Лагранжем, согласно которой в виде суммы квадратов четырех чисел можно представить любое число. Теорема эта, кстати, весьма непроста (доказать ее как-то пытался великий современник Лагранжа, швейцарский математик Леонард Эйлер, человек, отличавшийся удивительной математической интуицией, оригинальностью и продуктивностью, однако его постигла неудача).

Я, разумеется, не собираюсь докучать читателю подробностями доказательства Лагранжа, вместо этого рассмотрим одну не в пример более простую задачу:

(C) Найти нечетное число, являющееся суммой двух четных чи

сел.

2.4. Как убедиться в незавершаемости вычислений? 117

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

О, 2, 4, 6, 8, 10, 12, 14, 16, ...,

всегда получаются четные же числа; иными словами, никакая пара четных чисел не может дать в сумме нечетное число, т. е. число вида

1,3,5,7,9, 11, 13, 15, 17, ....

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

(D) Найти четное число, большее 2, не являющееся суммой двух простых чисел.

Вспомним, что простым называется натуральное число (отличное от 0 и 1), которое делится без остатка лишь само на себя и на единицу; иными словами, простые числа составляют следующий ряд:

2, 3, 5, 7, 11, 13, 17, 19, 23, ....

Существует довольно высокая вероятность того, что отыскание решения задачи (D) также потребует незавершающейся вычислительной процедуры, однако полной уверенности пока нет. Для получения такой уверенности необходимо прежде доказать истинность знаменитой "гипотезы Гольдбаха", выдвинутой Гольдбахом в письме к Эйлеру еще в 1742 году и до сих пор недоказанной.

2.4. Как убедиться в невозможности завершить

вычисление?

Мы установили, что вычисления могут как успешно завершаться, так и вообще не иметь конца. Более того, в тех случаях, когда вычисление завершиться в принципе не может, это его свойство иногда оказывается очевидным, иногда не совсем

118 Глава 2

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

1,7,19,37,61,91,127,...,

иными словами, числа, из которых можно строить шестиугольные матрицы (пустую матрицу на этот раз мы не включаем):

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

6, 12, 18, 24, 30, 36, ....

Это легко объяснимо, если обратить внимание на то, что каждое новое шестиугольное число получается путем окружения предыдущего числа шестиугольным кольцом

2.4. Как убедиться в незаверишемости вы числений? 119

причем число горошин в этом кольце обязательно будет кратно 6, а множитель при каждом увеличении шестиугольника на одно кольцо будет возрастать ровно на единицу.

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

1 = 1, 1 + 7 = 8, 1 + 7+19 = 27,

1 + 7 + 19 + 37 = 64, 1 + 7 + 19 + 37 + 61 = 125.

Что же особенного в числах I, 8, 27, 64, 125? Все они являются кубами. Кубом называют число, умноженное само на себя трижды:

1 = 13 =1x1x1, 8 = 23 = 2x2x2, 27 = 33 = 3x3x3,

64 = 43 = 4 х 4 х 4, 125 = 53 = 5 х 5 х 5, ....

Присуще ли это свойство всем шестиугольным числам? Попробуем следующее число. В самом деле,

1 + 7 + 19 + 37 + 61 + 91 = 216 = 6 х 6 х 6 = б3.

Всегда ли выполняется это правило? Если да, то никогда не завершится вычисление, необходимое для решения следующей задачи:

( Е) Найти последовательную сумму шестиугольных чисел, начиная с единицы, не являющуюся кубом.

Думается, я сумею убедить вас в том, что это вычисление и в самом деле можно выполнять вечно, но так и не получить искомого ответа.

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

120