Жар холодных числ и пафос бесстрастной логики
Шрифт:
Так к началу 50-х годов нашего века, то есть к моменту выхода на сцену электронных вычислительных машин, как итог развития всей предшествующей математики и логики и как непосредственный результат работ Чёрча, Тьюринга и Маркова, стал вырисовываться обширный комплекс процессов, обладающих следующими особенностями.
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). Из описания процесса видно, что он является однообразным, «механическим» и легко поддающимся автоматизации.