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

Нет необходимости подробно доказывать, что машине доступна реализация оператора подстановки — ведь подстановка есть последовательное вычисление функций, то есть вычисление некоторой функции при значениях аргументов, которые найдены ранее как значения других функций. Если машина умеет вычислять внутренние и внешнюю функции, фигурирующие в подстановке, итоговое вычисление гарантированно.

Вычисление по схеме рекурсии тоже легко осуществляется на ЭВМ. Напомним (ср. с. 137—138), что вычисление значения некоторой функции / (для простоты объяснения ограничимся одноместной функцией) при некотором значении аргумента ( по рекурсии производится по схеме

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).

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