Борис Бирюков - Жар холодных числ и пафос бесстрастной логики
Не так ли обстоит дело и в отношении основной гипотезы-теории алгоритмов в ее различных спецификациях— тезисов Чёрча, Тьюринга, Маркова? Вот что, например, говорит о своем тезисе сам автор «принципа нормализации:
«На чем же может быть основана уверенность в справедливости принципа нормализации алгорифмов, то есть в справедливости тех предсказаний, которые делаются на его основании? В основном на том же самом, на чем основана наша уверенность в правильности известных нам физических законов, на опыте.
А опыт, подтверждающий принцип нормализации, огромен. Ведь математикой люди занимаются довольно долго — не менее 4000 лет. За это время было придумано немало различных алгорифмов. И среди них не известно ни одного ненормализуемого. Как-никак, а это веский довод в пользу принципа нормализации. Не менее веский, чем, скажем, опытное подтверждение закона сохранения энергии»[20].
Наличие нескольких, а не одного, тезисов, причем тезисов между собой эквивалентных (несмотря на их большие внешние различия), имеет важное значение для осмысления процесса познания. Аппарат рекурсивных функций наиболее «архаичен», он ближе всего к классической математике, он связан с числами и только с числами. Машины Тьюринга уже отстоят значительно дальше от тех понятий, которые по традиционному мнению должны интересовать математиков. Но «механичность» мышления Тьюринга имеет те же корни, что и мышление великого Лейбница, мечтавшего построить машину, «делающую все». В лице Тьюринга математика вновь повернулась к своему первоисточнику — материальным процессам, теперь уже будучи в состоянии промоделировать значительную их часть своими элементарными знаковыми операциями. Наконец, алгорифмы Маркова на первый взгляд могут показаться даже вообще не имеющей отношения к математике «игрой в слова». Но как раз в этом резком расширении круга рассматриваемых структур и процессов и сказалась логическая зрелость математики и ее характернейшая тенденция.
Так к началу 50-х годов нашего века, то есть к моменту выхода на сцену электронных вычислительных машин, как итог развития всей предшествующей математики и логики и как непосредственный результат работ Чёрча, Тьюринга и Маркова, стал вырисовываться обширный комплекс процессов, обладающих следующими особенностями.
1. Они в принципе строго детерминированы, то есть каждый предыдущий этап полностью определяет последующий.
2. Они потенциально осуществимы — в том смысле, что при достаточно долгом протекании без внешних помех они приводят (могут приводить) к фактическому результату.
3. Они имеют «атомарное» строение — складываются из совокупности элементарных операций, которых имеется всего несколько видов.
4. Элементарные операции, сочетание которых порождает бесконечное разнообразие таких процессов, настолько хорошо обозримы, наглядны и соответствуют особенностям человеческого восприятия и мышления, что их нетрудно объяснить любому человеку.
А существуют ли в мире другие процессы?
Вопрос этот не случаен. В случае отрицательного ответа в сферу описанных процессов будут включены и явления. происходящие в нас самих, наша внутренняя жизнь. Эта возможность представляется оскорбительной, унижающей человеческое достоинство. Признать полную принципиальную детерминированность психических явлений - не значит ли это признать несвободу поведения человека? И разве можно какую-то заводящуюся ключом игрушку — машину Тьюринга — сопоставить с поведением вольной в своих поступках личности, например, с поведением и творческой работой Пушкина? Да не только Пушкин, разве любой из нас, самый скромный из нас, согласится признать, что его действия в каждую данную секунду, в каждую долю секунды, все его тончайшие помыслы, фантазии, мечты, стремления, эмоции могут быть описаны какими-то очень простыми рекурсивными функциями?
В этих возражениях проявляется естественная неприязнь человека к автоматизму, бездушию, слепому выполнению программы. Конечно, автоматизм в поведении человека отвратителен, и прожить, строго выполняя намеченную программу, просто невозможно. Конечно, все, даже фанатически преданные математике отшельники, не могли бы и дня просуществовать без неожиданных для самих себя поступков, без юмора — этого воплощения тяги к странности и непредвиденности. Все это так, но ведь речь идет не об этом. Вопрос ставится следующим образом: состоит ли грандиозно сложный процесс рождения, функционирования и умирания человека (как и любой другой процесс во Вселенной) из композиции гигантского числа рекурсивно описываемых процессов — подобно тому, как прекрасный цветок розы состоит (как физическое тело) из гигантского количества ничем не пахнущих и не имеющих цвета атомов?
В такой постановке проблема становится серьезной.
8. ВОЗМОЖНОСТИ ВЫЧИСЛИТЕЛЬНЫХ МАШИН И ЧЕЛОВЕК
Множественность типов вычислимости есть та основа, которая позволяет подвергнуть анализу запутанный клубок проблем, относящихся к вопросу: «Что может делать электронная вычислительная машина?». ЭВМ в первом приближении можно охарактеризовать как гигантский арифмометр, работающий с огромной скоростью. Однако это — только в первом приближении: по сравнению с арифмометром у ЭВМ имеются две принципиально важные конструктивные особенности.
Обычный арифмометр (например, марки «Феликс») после выполнения заданной ему операции сложения, умножения и т. д, прекращает работу и ждет дальнейших «распоряжений». Чтобы выполнить с помощью арифмометра действие над полученным результатом, нужно западе набрать последний на его клавиатуре и нажать на соответствующую кнопку, а если арифмометр не электрический, то покрутить ручку. Электронная вычислительная машина может повторять арифметическую операцию сколько угодно раз подряд, беря в качестве исходных данных числа, полученные ею на одном из предыдущих этапов. На арифмометре, например, легко можно прибавить к любому числу единицу, но чтобы после этого сделать еще что-то, требуется новое вмешательство человека.
ЭВМ же может быть введена в такой режим, когда она будет возвращаться к собственному результату без дальнейших распоряжений и станет осуществлять потенциально бесконечный процесс многократного применения функции «число, непосредственно следующее за...», то есть последовательного получения возрастающих натуральных чисел. Вторым отличием электронной вычислительной машины от обычного арифмометра является то, что она умеет выполнять простейший условный оператор — проверять, равно ли нулю некоторое число, и в зависимости от этого производить одно или другое действие. Таковы принципиальные отличия современного «супермозга» от арифмометра, а значит, и от счетов, а значит, и от десяти пальцев математиков каменного века. «Непринципиальное» отличие относится к скорости действия и объему памяти. Но количество здесь переходит в качество.
Знакомство с основными результатами современной математической логики, теории логического вывода и теории вычислимости (теории алгоритмов) позволяет понять почему «большой арифмометр», дополненный двумя упомянутыми усовершенствованиями, «может делать все».
Начнем с его способности проверять условия. Проверка элементарного условия x = 0 для электронного автомата несложна[1]. Предположим теперь, что число x получается как результат вычисления некоторой одноместной общерекурсивной[2] функции f. Отсюда сразу следует, что машина способна проверять истинность любого общерекурсивного предиката f(у) = 0. Но способна ли ЭВМ, хотя бы в принципе, вычислять значения любой общерекурсивной функции?
Функция «следования за», конечно, не представляет труда для «автоматического арифмометра». Еще легче выполнить ему вычисление функции, тождественно-равной нулю — вместо любого данного числа написать нуль. Так же легко осуществит автомат вычисление проектирующей функции, поскольку это есть не что иное, как выбор из данной группы чисел такого-то по порядковому номеру числа. Эту операцию можно реализовать на машине, например, так: в машинную память вводятся по одному числу из заданной группы в n чисел, причем при каждом введении числа предыдущее стирается из памяти; одновременно с вводом каждого такого числа некоторое (другое) число, хранящееся в определенной ячейке запоминающего устройства, увеличивается на единицу — как говорят в этом случае, работает счетчик числа операций. Когда разность между числом, накопившимся на счетчике, и данным числом i (нижним индексом проектирующей функции Iin) станет равной нулю, сработает условный оператор, и число, находящееся в этот момент в памяти, пойдет на выход.
Нет необходимости подробно доказывать, что машине доступна реализация оператора подстановки — ведь подстановка есть последовательное вычисление функций, то есть вычисление некоторой функции при значениях аргументов, которые найдены ранее как значения других функций. Если машина умеет вычислять внутренние и внешнюю функции, фигурирующие в подстановке, итоговое вычисление гарантированно.
![Джон Макдональд - Оставшийся в живых [Меня оставили в живых]](/uploads/posts/books/248375/248375.jpg)
