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

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

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

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

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

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

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

0,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 году и до сих пор недоказан­ной.

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

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

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

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

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

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

0,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 году и до сих пор недоказан­ной.