Жар холодных числ и пафос бесстрастной логики

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

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

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

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

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

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

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