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

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

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

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

На этот раз, добравшись до числа 7, мы находим, что в виде суммы квадратов четырех чисел его представить вполне возможно: 7 = 1² + 1² + 1² + 2², поэтому мы переходим к числу 8 (сумма 8 = 0² + 0² + 2² + 2²), далее — 9 (сумма 9 = 0² + 0² + 0² + 3²) и 10 (10 = 0² + 0² + 1² + 3²) и т.д. Вычисления все продолжаются и продолжаются (… 23 = 1² + 2² + 3² + 3², 24 = 0² + 2² + 2² + 4², …, 359 = 1² + 3² + 5² + 18², …) и завершаться, похоже, не собираются. Мы предполагаем, что искомое число, должно быть, невообразимо велико, и для его вычисления нашему компьютеру потребуется чрезвычайно большой промежуток времени и огромный объем памяти. Более того, мы уже начинаем сомневаться, существует ли оно вообще, это самое число. Вычисления все продолжаются и продолжаются, и конца им не видно. Вообще говоря, так оно и есть: описанная вычислительная процедура завершиться в принципе не может. Известна теорема, впервые доказанная в 1770 году великим французским (и отчасти итальянским) математиком Жозефом Луи Лагранжем, согласно которой в виде суммы квадратов четырех чисел можно представить любое число. Теорема эта, кстати, весьма непроста (доказать ее как-то пытался великий современник Лагранжа, швейцарский математик Леонард Эйлер, человек, отличавшийся удивительной математической интуицией, оригинальностью и продуктивностью, однако его постигла неудача).

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

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

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

0, 2, 4, 6, 8, 10, 12, 14, 16, …,

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

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

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

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

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

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

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