Вариация Гольдбаха
В книге «Гёдель, Эшер, Бах: эта бесконечная гирлянда» Дуглас Хофштадтер предлагает рассмотреть следующую вариацию гипотезы Гольдбаха: можно ли представить любое четное число в виде разности двух простых чисел? Интересно, нельзя ли назвать эту гипотезу «вариацией Гольдбаха – Гольдберга»?
Начнем с начала: 2 = 5 – 3, 4 = 7 – 3, 6 = 11 – 5, 8 = 11 – 3. Разумеется, для некоторых чисел существует несколько вариантов: 10 = (41 – 31) = = (29 – 19) = (23 – 13) = (17 – 7) = (13 – 3).
Несмотря на ярко выраженное сходство этих двух задач, между ними есть фундаментальное различие. Рассматривая исходный вариант гипотезы Гольдбаха, мы можем запустить для любого четного числа компьютерную программу, которая проверит, дает ли это значение сумма двух простых чисел, причем сделает это за конечное время. Даже если такое число очень велико, мы можем быть уверены, что к какому-то моменту программа завершит работу – даже если мы сами до этого момента и не доживем. Во втором же варианте нет никакой гарантии, что компьютер когда-либо закончит свои вычисления. Возьмем произвольное число – скажем, 2010. Абсолютно невозможно определить заранее, когда компьютер закончит вычисления (и закончит ли их когда-либо), потому что, даже если мы проверим все до единого простые числа, скажем, до 12 345 678 910 и не найдем пары простых чисел, разность которых равна 2010, это не значит, что мы не найдем такой пары в будущем. Я использовал здесь число 2010 только для иллюстрации этой идеи. На самом деле компьютеру не составит особого труда выяснить, что число 2010 может быть выражено в виде разности двух простых чисел, например 2017 – 7, 2029 – 19, 2039 – 29 и других. Во всяком случае, эта задача радикально отличается от проверки возможности выражения числа 2010 в виде суммы двух простых чисел (что, как вы уже знаете, возможно: самый простой из нескольких существующих вариантов – 2003 + 7).
Различие состоит в следующем: при поиске ответа в отношении суммы существует конечное число возможностей: нужно лишь проверить все простые числа, меньшие самого искомого числа. В случае 2010 необходимо исследовать только лишь все простые числа до 2007 (самого большого простого числа до 2010). Даже если бы мы взяли не 2010, а 2010! это число все равно было бы конечным, и программа в конце концов пришла бы к тому или иному выводу, проработав в течение конечного времени (более долгого, чем кажется, но тем не менее конечного).
