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

Знакомство с основными результатами современной математической логики, теории логического вывода и теории вычислимости (теории алгоритмов) позволяет понять почему «большой арифмометр», дополненный двумя упомянутыми усовершенствованиями, «может делать все».

Начнем с его способности проверять условия. Проверка элементарного условия x = 0 для электронного автомата несложна[1]. Предположим теперь, что число x получается как результат вычисления некоторой одноместной общерекурсивной[2] функции f. Отсюда сразу следует, что машина способна проверять истинность любого общерекурсивного предиката f(у) = 0. Но способна ли ЭВМ, хотя бы в принципе, вычислять значения любой общерекурсивной функции?

Функция «следования за», конечно, не представляет труда для «автоматического арифмометра». Еще легче выполнить ему вычисление функции, тождественно-равной нулю — вместо любого данного числа написать нуль. Так же легко осуществит автомат вычисление проектирующей функции, поскольку это есть не что иное, как выбор из данной группы чисел такого-то по порядковому номеру числа. Эту операцию можно реализовать на машине, например, так: в машинную память вводятся по одному числу из заданной группы в n чисел, причем при каждом введении числа предыдущее стирается из памяти; одновременно с вводом каждого такого числа некоторое (другое) число, хранящееся в определенной ячейке запоминающего устройства, увеличивается на единицу — как говорят в этом случае, работает счетчик числа операций. Когда разность между числом, накопившимся на счетчике, и данным числом i (нижним индексом проектирующей функции I_iⁿ) станет равной нулю, сработает условный оператор, и число, находящееся в этот момент в памяти, пойдет на выход.

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

Вычисление по схеме рекурсии тоже легко осуществляется на ЭВМ. Напомним (ср. с. 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 и, как только это значение оказывалось равным нулю, отправлял соответствующее натуральное число на выход в качестве результата.

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