Борис Бирюков - Жар холодных числ и пафос бесстрастной логики Страница 32

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

По мере углубления в проблему выяснялось, что все «обиходные» функции, принятые в анализе, выражаются через рекурсивные функции, так что в этом плане обеднения не происходит. Учитывая этот факт, А. Чёрч в 1936 году выдвинул гипотезу, получившую название тезиса Чёрча, которая может быть сформулирована следующим образом: вычислимы те, и только те, математические объекты, которые могут быть получены с помощью общерекурсивиых функций. Другими словами, Чёрч предположил, что общерекурсивных функций достаточно для реализации любой строгой и однозначно определяемой вычислительной процедуры.

В том же 1936 году С. К. Клини ввел понятие частично рекурсивной функции, с которым естественно связывается аналогичная гипотеза относительно частично рекурсивных функций (случаю, когда рекурсивная функция для некоторого набора аргументов не определена, здесь соответствует ситуация вычислительного процесса, продолжающегося неограниченно долго). Эту более общую гипотезу также нередко называют тезисом Чёрча[5].

Иногда шутят: в математике тезисы хороши тем, что их не не нужно доказывать. Действительно, тезис Чёрча (как и два других тезиса, о которых речь пойдет ниже) недоказуем математически. Об этом очень ясно сказал Ласло Кальмар[6]. «В своем знаменитом исследовании неразрешимых арифметических проблем Чёрч[7] использовал рабочую гипотезу о тождественности понятия эффективно вычислимой функции понятию общерекурсивной функции... Эта рабочая гипотеза известна под названием тезиса Чёрча. Она имеет несколько эквивалентных форм... В настоящей статье я не буду опровергать тезис Чёрча. Этот тезис не есть математическая теорема, которая может быть доказана или опровергнута в строго математическом смысле, поскольку он устанавливает тождество двух понятий, из которых только одно определено математически, в то время как другое употребляется математиками без точного определения. Конечно, тезис Чёрча можно замаскировать под определение: мы называем арифметическую функцию эффективно вычислимой тогда, и только тогда, когда она является общерекурсивной; однако в этом случае появляется опасность, что в будущем кто-нибудь построит функцию, которая, с одной стороны, не будет эффективно вычислимой в установленном таким образом смысле, а с другой стороны, ее значения будут очевидно эффективно вычислимыми для любых заданных аргументов.

Точно так же, если установить по определению, что проблема, содержащая параметр, пробегающий натуральные числа, разрешима тогда, и только тогда, когда ее характеристическая функция[8] общерекурсивна, возникает опасность, что кто-нибудь в будущем решит проблему, не разрешимую в смысле данного определения. Поэтому мне кажется более целесообразным смотреть на такие утверждения, как тезис Чёрча или отождествление разрешимых проблем с проблемами, обладающими общерекурсивными характеристическими функциями, не как на определения, а скорее как на суждения, правда, суждения не математические, а пред-математические. То обстоятельство, что более двух страниц статьи Чёрча наполнены аргументами в пользу убедительности его тезиса (и, следовательно, носят пред-математический характер), показывает, что его собственное мнение на этот счет не слишком отличается от моего».

Тем не менее за гипотезой Чёрча стоит весь громадный опыт математики как «вычислительной» науки, глубокое проникновение в природу математической истины. Значение гипотезы Чёрча с годами росло; в «век кибернетики» она стала много интереснее, чем казалась тридцать лет назад, когда ее смысл трудно было, наверно, даже объяснить математикам, не специализирующимся в области логики.

В приведенной выше цитате Л. Кальмар упоминает об эквивалентных формах гипотезы Чёрча. Он имеет в виду прежде всего следующие два тезиса, равносильных, как было строго доказано, тезису Чёрча: тезис Тьюринга и тезис Маркова. Эти «переформулировки» чёрчевской гипотезы заслуживают большого внимания как с философской, так и с кибернетической точки зрения.

Чёрч, Тьюринг и Марков подходят к проблеме с разных сторон, кладут в основу своих построений разные «пред-математические» соображения, причем эти соображения, как мы увидим, все более удаляются от представлений классической математической интуиции. И тот факт, что их теории оказались охватывающими в некотором смысле один и тот же круг процессов, явился серьезным подтверждением (хотя и не доказательством) каждого из тезисов: трудно допустить, что ложные построения, основанные на совершенно разных посылках, окажутся в точности совпадающими, в то время как если предположить, что они истинны, такое совпадение объясняется очень просто: истина едина.

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

В том же году (1936), когда Чёрч выдвинул свой тезис о рекурсивных функциях, английский математик и логик Алан Тьюринг (1912—1954) в поисках элементарных действий, к которым можно свести всякую процедуру вычисления, решил стать на путь ее «механизации». Он исходил из представления, что механические операции являются наиболее простыми и надежными. Однако Тьюринг был далек от стремления изготовить какой-то механизм из железа или других материалов; его интересовала теоретическая сторона дела. Ему важно было убедиться в принципиальной осуществимости такой машины, которая в состоянии проделать любую вычислительную процедуру[9].

Основное свойство машины Тьюринга — то, что она имеет конечное число «внутренних состояний». Механизмов, обладающих конечным набором состояний, великое множество: это, скажем, выключатель, каретка пишущей машинки, кнопочная система радиоприемника, дверной замок, рычаг коробки передач автомобиля, стрелка электрических часов и т. д. Правда, у всех перечисленных сейчас физических объектов между основными состояниями, число которых конечно, имеются некоторые промежуточные состояния (например, когда стрелка электрочасов «прыгает»), но они осуществляются лишь в переходном режиме на очень короткое время и не играют роли в функционировании механизма. Надо тут же добавить, что, наверное, столь же великое множество приборов и механизмов обладает, в принципе, не дискретным, а непрерывным набором состояний (скажем, логарифмическая линейка). Машина Тьюринга есть аналог механизмов первого класса.

Предполагается, что машина Тьюринга реагирует на знаки из некоторого набора знаков — внешнего алфавита, наносимые в ячейках некоторой (бумажной или иной) ленты; в каждой ячейке может быть нанесен только один знак;

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

Это предположение тоже естественно. Почтовый автомат который в наши дни расшифровывает написанный по определенному стандарту индекс отделения связи, служит примером того, как несложный механизм может выполнять про. цедуру «опознавания» простых начертаний.

Набор действий, доступных машине Тьюринга, весьма ограничен. Она может выполнить следующие операции:

(1) перейти в другое внутреннее состояние (или остаться в прежнем состоянии);

(2) стереть знак, напечатанный в обозреваемой ею ячейке ленты, напечатать вместо него другой или оставить знак без изменения;

(3) передвинуть бумажную ленту на стандартное расстояние (скажем, на 1 см), соответствующее размеру ячейки, в левую или в правую сторону;

(4) остановиться (например, отключиться от сети, если она электрическая); остановку машины можно понимать как ее переход в особое — заключительное — состояние.