1. Они в принципе строго детерминированы, то есть каждый предыдущий этап полностью определяет последующий.
2. Они потенциально осуществимы — в том смысле, что при достаточно долгом протекании без внешних помех они приводят (могут приводить) к фактическому результату.
3. Они имеют «атомарное» строение — складываются из совокупности элементарных операций, которых имеется всего несколько видов.
4. Элементарные операции, сочетание которых порождает бесконечное разнообразие таких процессов, настолько хорошо обозримы, наглядны и соответствуют особенностям человеческого восприятия и мышления, что их нетрудно объяснить любому человеку.
А существуют ли в мире другие процессы?
Вопрос этот не случаен. В случае отрицательного ответа в сферу описанных процессов будут включены и явления. происходящие в нас самих, наша внутренняя жизнь. Эта возможность представляется оскорбительной, унижающей человеческое достоинство. Признать полную принципиальную детерминированность психических явлений - не значит ли это признать несвободу поведения человека? И разве можно какую-то заводящуюся ключом игрушку — машину Тьюринга — сопоставить с поведением вольной в своих поступках личности, например, с поведением и творческой работой Пушкина? Да не только Пушкин, разве любой из нас, самый скромный из нас, согласится признать, что его действия в каждую данную секунду, в каждую долю секунды, все его тончайшие помыслы, фантазии, мечты, стремления, эмоции могут быть описаны какими-то очень простыми рекурсивными функциями?
В этих возражениях проявляется естественная неприязнь человека к автоматизму, бездушию, слепому выполнению программы. Конечно, автоматизм в поведении человека отвратителен, и прожить, строго выполняя намеченную программу, просто невозможно. Конечно, все, даже фанатически преданные математике отшельники, не могли бы и дня просуществовать без неожиданных для самих себя поступков, без юмора — этого воплощения тяги к странности и непредвиденности. Все это так, но ведь речь идет не об этом. Вопрос ставится следующим образом: состоит ли грандиозно сложный процесс рождения, функционирования и умирания человека (как и любой другой процесс во Вселенной) из композиции гигантского числа рекурсивно описываемых процессов — подобно тому, как прекрасный цветок розы состоит (как физическое тело) из гигантского количества ничем не пахнущих и не имеющих цвета атомов?
В такой постановке проблема становится серьезной.
8. ВОЗМОЖНОСТИ ВЫЧИСЛИТЕЛЬНЫХ МАШИН И ЧЕЛОВЕК
Множественность типов вычислимости есть та основа, которая позволяет подвергнуть анализу запутанный клубок проблем, относящихся к вопросу: «Что может делать электронная вычислительная машина?». ЭВМ в первом приближении можно охарактеризовать как гигантский арифмометр, работающий с огромной скоростью. Однако это — только в первом приближении: по сравнению с арифмометром у ЭВМ имеются две принципиально важные конструктивные особенности.
Обычный арифмометр (например, марки «Феликс») после выполнения заданной ему операции сложения, умножения и т. д, прекращает работу и ждет дальнейших «распоряжений». Чтобы выполнить с помощью арифмометра действие над полученным результатом, нужно западе набрать последний на его клавиатуре и нажать на соответствующую кнопку, а если арифмометр не электрический, то покрутить ручку. Электронная вычислительная машина может повторять арифметическую операцию сколько угодно раз подряд, беря в качестве исходных данных числа, полученные ею на одном из предыдущих этапов. На арифмометре, например, легко можно прибавить к любому числу единицу, но чтобы после этого сделать еще что-то, требуется новое вмешательство человека.
ЭВМ же может быть введена в такой режим, когда она будет возвращаться к собственному результату без дальнейших распоряжений и станет осуществлять потенциально бесконечный процесс многократного применения функции «число, непосредственно следующее за...», то есть последовательного получения возрастающих натуральных чисел. Вторым отличием электронной вычислительной машины от обычного арифмометра является то, что она умеет выполнять простейший условный оператор — проверять, равно ли нулю некоторое число, и в зависимости от этого производить одно или другое действие. Таковы принципиальные отличия современного «супермозга» от арифмометра, а значит, и от счетов, а значит, и от десяти пальцев математиков каменного века. «Непринципиальное» отличие относится к скорости действия и объему памяти. Но количество здесь переходит в качество.
Знакомство с основными результатами современной математической логики, теории логического вывода и теории вычислимости (теории алгоритмов) позволяет понять почему «большой арифмометр», дополненный двумя упомянутыми усовершенствованиями, «может делать все».
Начнем с его способности проверять условия. Проверка элементарного условия x = 0 для электронного автомата несложна[1]. Предположим теперь, что число x получается как результат вычисления некоторой одноместной общерекурсивной[2] функции f. Отсюда сразу следует, что машина способна проверять истинность любого общерекурсивного предиката f(у) = 0. Но способна ли ЭВМ, хотя бы в принципе, вычислять значения любой общерекурсивной функции?
Функция «следования за», конечно, не представляет труда для «автоматического арифмометра». Еще легче выполнить ему вычисление функции, тождественно-равной нулю — вместо любого данного числа написать нуль. Так же легко осуществит автомат вычисление проектирующей функции, поскольку это есть не что иное, как выбор из данной группы чисел такого-то по порядковому номеру числа. Эту операцию можно реализовать на машине, например, так: в машинную память вводятся по одному числу из заданной группы в n чисел, причем при каждом введении числа предыдущее стирается из памяти; одновременно с вводом каждого такого числа некоторое (другое) число, хранящееся в определенной ячейке запоминающего устройства, увеличивается на единицу — как говорят в этом случае, работает счетчик числа операций. Когда разность между числом, накопившимся на счетчике, и данным числом i (нижним индексом проектирующей функции Iin) станет равной нулю, сработает условный оператор, и число, находящееся в этот момент в памяти, пойдет на выход.
Нет необходимости подробно доказывать, что машине доступна реализация оператора подстановки — ведь подстановка есть последовательное вычисление функций, то есть вычисление некоторой функции при значениях аргументов, которые найдены ранее как значения других функций. Если машина умеет вычислять внутренние и внешнюю функции, фигурирующие в подстановке, итоговое вычисление гарантированно.
Вычисление по схеме рекурсии тоже легко осуществляется на ЭВМ. Напомним (ср. с. 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 и, как только это значение оказывалось равным нулю, отправлял соответствующее натуральное число на выход в качестве результата.
138
1. Имеется в виду, что число x представлено в двоичной системе счисления и введено в память ЭВМ. В этом случае проверка условия x = 0 сводится к выяснению того, имеет ли хотя бы один элемент ячейки памяти, отведенной иод данное число, ненулевое значение, что, очевидно, технически нетрудно осуществить. Однако мы не останавливаемся здесь на устройстве ЭВМ и ее памяти, так как нас интересует логико-математическая сторона дела. О техническом аспекте действия ЭВМ и о физической реализации процесса запоминания см., например: Л. Н. Краснухин, П. В. Нестеров. Цифровые вычислительные машины. М. 1974.
139
2. Если функция f частично-рекурсивна, то при некоторых аргументах она может быть не определена, и процесс вычисления никогда не закончится. На первый взгляд рассмотрение в этом месте лишь общерекурсивных функций ограничивает общность рассуждений, однако, как мы увидим несколько ниже, это не так.
140
3. Заметим, что ЭВМ может вычислить или, по крайней мере, пытаться вычислить значение любой частично-рекурсивной функции (заранее не всегда известно, является ли интересующая нас функция общерекурсивной). Ибо, как показал С. К. Клини, каждую частично рекурсивную функцию можно представить в виде суперпозиции двух функций, первая из которых есть результат действия мю-оператора на некоторую примитивно рекурсивную функцию, а вторая — примитивно рекурсивная функция, вообще говоря, не совпадающая с упомянутой ранее.