Борис Бирюков - Жар холодных числ и пафос бесстрастной логики
Нет необходимости подробно доказывать, что машине доступна реализация оператора подстановки — ведь подстановка есть последовательное вычисление функций, то есть вычисление некоторой функции при значениях аргументов, которые найдены ранее как значения других функций. Если машина умеет вычислять внутренние и внешнюю функции, фигурирующие в подстановке, итоговое вычисление гарантированно.
Вычисление по схеме рекурсии тоже легко осуществляется на ЭВМ. Напомним (ср. с. 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).
Любое из утверждений такого рода может быть доказано вполне строго. Возникает вопрос: является ли ЭВМ-вычислимость более мощной, чем рекурсивная вычислимость, то есть может ли вычислительная машина сделать что-нибудь такое, чего нельзя сделать с помощью аппарата рекурсивных функций? Если строго рассмотреть этот вопрос, окажется, что он получает отрицательный ответ. ЭВМ-вычислимость эквивалентна рекурсивной вычислимости, а значит, эквивалентна также алгорифмической вычислимости (по Маркову) и вычислимости по Тьюрингу.
Как звучит соответствующий тезис? Очевидно, так: всякая конечная вычислительная (в частности, логическая, дедуктивная) процедура, характеризующаяся детерминированностью своего выполнения, может быть осуществлена на цифровой вычислительной машине с достаточно большой памятью за достаточно большое время.
Эквивалентность этого утверждения, которое можно назвать тезисом кибернетики, остальным рассмотренным нами тезисам является сильным аргументом в их пользу. Ведь «на мельницу» кибернетического тезиса ежедневно и ежечасно «льет воду» практика программирования и вычислительная работа на ЭВМ, а из-за эквивалентности всех четырех тезисов мы можем сказать, что вода попадает и на три остальные мельницы. За 20 с лишним лет широкого применения вычислительной техники в самых разнообразных областях науки, техники, медицины, планирования, управления, прогнозирования и т. д. не было ни одного случая, чтобы задача, четко сформулированная на естественном или формализованном языке, сформулированная с помощью таблиц, графиков, номограмм, схем — самыми разнообразными путями и методами и не выходящая за разумные рамки в смысле трудоемкости требующихся для ее решения операций, не смогла быть записана в виде машинной программы.
Другими словами, не было случая, чтобы к математику, умеющему ставить задачи и программировать их для ввода в ЭВМ, пришел представитель какой-либо нематематической профессии — администратор, экономист, инженер, деятель искусства, ученый и т. д.— попросил бы его осуществить на машине процесс полностью детерминированного на каждом этапе вычисления, логического вывода, выделения некоторого объекта из некоторого множества объектов, расчета вариантов, выбора одних гипотез и исключения других и т. д., то есть процесс решения ясно и четко поставленной задачи из какой-то области деятельности, и чтобы математик совершенно ясно понял проблему, но ответил заказчику, что ее в принципе нельзя решить на ЭВМ. В худшем случае математик может ответить так: программа, соответствующая вашей задаче, на данной машине не пройдет, поскольку у машины слишком мал объем памяти и она слишком медленно работает, чтобы получить результат за разумное время.
Перефразируя выражение А. А. Маркова, заметим, что это, как-никак, веский аргумент. Пусть практика работы на ЭВМ насчитывает не 4000, а лишь 20— 25 лет, но какая это практика! Чего только ни делали с помощью ЭВМ — и составляли планы отраслей хозяйства, и находили выгоднейшие варианты перевозок, и играли в различные игры, но ни единого раза проблема, если она была четко поставлена, не упиралась в тот барьер, что для нее в принципе невозможно написать программу. Можно ли, однако, сказать, что все четко поставленные, но не решенные до сих пор на ЭВМ проблемы (или такие проблемы, относительно которых имеется уверенность, что их со временем можно поставить четко) просто ждут своей очереди: того дня, когда быстродействие и память «компьютеров» станут достаточно большими?
В качестве примера рассмотрим программирование на ЭВМ шахматной игры. Шахматы часто справедливо сравнивают с искусством, и для этой древней игры придумали даже свою «музу» — Каиссу. Широко известны многочисленные попытки моделировать процесс шахматного мышления на машине; их пока нельзя признать успешными, поскольку самые удачные шахматные программы значительно уступают мышлению хороших шахматистов. Каковы, однако, перспективы «машинных шахмат»?
Тезис кибернетики утверждает, что всякий детерминированный процесс, сущность которого можно объяснить человеку, потенциально осуществим машиной, то есть будет фактически выполнен на ЭВМ, которой предоставлено неограниченное время и которая имеет неограниченную память[4]. Первое условие можно переформулировать как условие достаточного быстродействия, поэтому данный тезис можно выразить еще и так: процесс, о котором сказано выше, всегда можно фактически выполнить на машине с достаточно высоким быстродействием и обладающей достаточно емким запоминающим устройством. Если бы такая машина существовала, то «шахматная проблема» давно была бы решена.
Программа для ее решения не представляет трудности; идея такой программы была выдвинута одним из основателей кибернетики Клодом Шенноном больше двадцати лет назад[5]. Соответствующий метод называется «построением дерева игры», и смысл его заключается в следующем. Выписываются все варианты первого хода белых; для каждого из них выписываются все пары ходов, состоящие из текущего первого хода белых и возможного, допустимого правилами игры ответного хода черных (то есть с каждым возможным ходом белых сопоставляются по очереди все возможные ходы черных, включая нелепые); затем с каждым ходом черных сопоставляются по очереди все возможные ходы белых и так далее. Если изобразить это на диаграмме, возникает ветвящееся «дерево» (отсюда и название метода). Ветви будут обрываться на ходах, ведущих к поражению одной из сторон или ничейным ситуациям.
![Джон Макдональд - Оставшийся в живых [Меня оставили в живых]](/uploads/posts/books/248375/248375.jpg)
