2

2

Двадцать лет назад в издательстве «Simon and Schuster» вышла «THE ENCYCLOPEDIA OF IGNORANCE» — энциклопедия, которая содержит в себе описание проблем от космологическо-космогонических до биологических и психологических, составляющих НЕИЗВЕСТНОЕ, причем некоторые из этих неизвестных феноменов могут навсегда остаться неразрешенными. К таким проблемам, которые могли бы стать областью непреодолимого в познании неведения, принадлежал также предел вычислительной мощности всех компьютеров от машины Тьюринга вплоть до чисто абстрактного компьютера, который мог бы быть сконструирован ИЗ ВСЕЙ МАТЕРИИ ВСЕЛЕННОЙ. Математик и биофизик из Беркли (Калифорния) Х.Дж. Бремерманн в работе «Комплексность и сверхвычислимость» («Complexity and transcomputability») занялся именно поиском границы производительности, то есть вычислительной мощности компьютера, который из-за того, что приближается к непоколебимым законам или запретам физики, «дальше» пойти в своей калькуляционной работоспособности уже не может. Бремерманн как-то обошелся без многочленов; он попросту взял за основу ряд основных данных физики, такие как скорость света (согласно открытому Эйнштейном предельному явлению скорости фотонов, быстрее, чем световой сигнал, никакой сигнал идти не может), как постоянная Планка и т. п. Однако я не намерен здесь излагать основы физики; у Бремерманна, согласно очень простым вычислениям, быстро «получилось», что движение сигналов в битах на секунду в компьютере в конечном счете ограничено соотношением E/h, где Е — энергия, доставляющая сигналы, а h — постоянная Планка. Предельный, согласно Бремерманну, компьютер — это куб с трехсантиметровым ребром, элементарная операция в котором выполняется 10^–10 секунды. Затем Бремерманн ввел понятие «вычислительной стоимости» произвольного алгоритма, который должен решить арифметическую задачу, содержащую n элементов. Оказывается, что эта «вычислительная стоимость» растет как факториал от n (n!). Компьютеры того времени, когда писал Бремерманн, достигли скорости 100 миллионов операций в секунду (в настоящее время эта величина подверглась уже по меньшей мере удвоению). Затем Бремерманн вводит уже известную нам (из предыдущего эссе о вычислительной мощности жизни) проблему коммивояжера, который должен посетить целый ряд населенных пунктов так, чтобы в каждом побывать только раз, то есть найти кратчайшую дорогу для своего путешествия. И здесь проблема разрешается в соответствии с факториалом: для n = 4 имеем 1 ? 2 ? 3 ? 4 = 24. Но n как факториал начинает по мере увеличения расти быстрее, чем показатель: для n, равного десяти, компьютеру требуется 5 секунд, а для n = 20 время работы компьютера составило бы 100 000 лет! Именно это и привело к тому, что Бремерманн посчитал проблемы подобной «твердости» или «алгоритмической стоимости» СВЕРХВЫЧИСЛИМЫМИ («transcomputable»). Это должно было стать непреодолимой «стеной» на пути функционального совершенствования компьютеров, чем-то вроде их предельной работоспособности наподобие непреодолимой скорости света. Действительно, для классических алгоритмов дело, по сути, обстоит именно таким образом. Однако в настоящее время появились тактики обхода этой якобы «непреодолимой» сверхвычислимости, которые сейчас уже довольно широко применяются в областях гораздо более практических, чем искусственно приведенная проблема путешествующего коммивояжера. Особенно много таких проблем в большом бизнесе (в одном из предыдущих эссе я упоминал о задаче поиска оптимального минимума самолетов на случай неожиданной аварии, или забастовки, или другого инцидента, срывающих планируемый расписанием полетов вылет, ожидаемый пассажирами: затраты могут составлять миллионы долларов).