Борис Бирюков - Жар холодных числ и пафос бесстрастной логики

f(0)= r

f(m') = h(m, f(m)).

где двуместная функция h уже «освоена» — программисты и ЭВМ умеют ее вычислять. Принцип пользования этой схемой заключается в следующем. Машине задается число r, входящее в первую строчку схемы, способ вычисления функции А, в память машины вводится число i и счетчик числа операций ставится в исходное положение (нулевое). Далее организуется следующий процесс: автомат вычисляет значение функции h при значениях ее аргументов 0 и r и вводит в счетчик единицу. Пусть h(0, r) = l. Далее машина сравнивает показание счетчика (число 1) с числом i(проверяя, равна ли нулю их разность) и, если они различны, вычисляет значение функции h при значениях аргументов 1 и l, то есть отыскивает h (1, l), после чего снова добавляет в счетчик единицу, и процедура повторяется. Когда показание счетчика станет равным i, процесс обрывается, и на выход идет значение f(i). Из описания процесса видно, что он является однообразным, «механическим» и легко поддающимся автоматизации.

Еще проще машинизировать мю-операцию, которая как бы специально создана для ЭВМ, хотя была введена в математику лет за двадцать до появления электронных автоматов. Ее смысл заключается в отыскании первого натурального числа х, удовлетворяющего условию вида g(х) = О, где g — общерекурсивная функция [3]. Если машина умеет вычислять значения g при любых значениях аргумента, реализация мю-оператора сводится к тому, чтобы автомат перебирал подряд натуральные числа (каждый раз увеличивая на единицу предыдущее число, то есть пользуясь функцией «следования за»), вычислял для каждого из них значение g и, как только это значение оказывалось равным нулю, отправлял соответствующее натуральное число на выход в качестве результата.

Из всего сказанного вытекает, что любой вычислительный процесс, потенциально осуществимый с помощью аппарата рекурсивных функций, потенциально осуществим также и на ЭВМ. Уточним, в каком смысле нужно поймать слово «потенциально» в применении к вычислительной машине.

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

Будем называть вычислимость такого рода ЭВМ-вычислимостью. Как мы убедились, ЭВМ-вычислимость включает в себя рекурсивную вычислимость. Конечно, аргументы, приводившиеся в пользу этого утверждения, носили описательный характер. Однако его можно превратить в серию аналогичных утверждений, в каждом из которых будет фигурировать не ЭВМ «вообще», а ЭВМ некоторого данного типа (или класс ЭВМ, программируемых с помощью конкретного алгоритмического языка, скажем, языка АЛГОЛ-68).

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

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

Эквивалентность этого утверждения, которое можно назвать тезисом кибернетики, остальным рассмотренным нами тезисам является сильным аргументом в их пользу. Ведь «на мельницу» кибернетического тезиса ежедневно и ежечасно «льет воду» практика программирования и вычислительная работа на ЭВМ, а из-за эквивалентности всех четырех тезисов мы можем сказать, что вода попадает и на три остальные мельницы. За 20 с лишним лет широкого применения вычислительной техники в самых разнообразных областях науки, техники, медицины, планирования, управления, прогнозирования и т. д. не было ни одного случая, чтобы задача, четко сформулированная на естественном или формализованном языке, сформулированная с помощью таблиц, графиков, номограмм, схем — самыми разнообразными путями и методами и не выходящая за разумные рамки в смысле трудоемкости требующихся для ее решения операций, не смогла быть записана в виде машинной программы.