Продемонстрированная нами серия однообразных действий показывает те «микроакции», из которых складывается мю-операция. Главная особенность вычислительного процесса данного типа состоит в том, что в качестве его кирпича фигурирует условный оператор, очень важный в кибернетике.
Условным операторам называется такое предписание, которое определяет действие не единственным образом, а предусматривает два его варианта: первый осуществляется в случае, когда условие, входящее в состав оператора, выполнено, а второй реализуется в противном случае, если условие не выполнено. Условие, конечно, должно быть таково, чтобы проверка его выполнения носила конструктивный — осуществимый по ясным правилам в течение конечного времени — характер. Можно еще сказать, что условный оператор образует «точку ветвления» процесса вычисления, зависящего от выполнения или невыполнения некоторого конструктивно проверяемого условия.
Наличие условного оператора вносит элемент своего рода неопределенности (осуществляя вычислительный процесс по схеме, содержащей такой оператор, мы не знаем заранее, на каком шаге будет выполнено заключенное в нем условие и будет ли выполнено вообще), не принятый в классической теории функций прием отыскания значений с помощью «проб и ошибок», прямым перебором натурального ряда. Однако этот элемент вполне естествен, если смотреть на математику как на результат человеческого творчества, как на процесс созидания знаковых моделей.
Перебор значений натурального аргумента с проверкой на каждом этапе простого условия не вызывает опасений в отношении своей ненадежности; во всяком случае он более надежей, чем такие процессы, санкционированные классическим анализом, как, скажем, переход к пределу или оперирование с действительными числами, большинство из которых остаются не выразимыми ни в какой символике. Каждый отдельный шаг в мю-операции общепонятен, элементарен и целиком и одновременно обозрим; акты же ветвления процессов в зависимости от выполнения условий пронизывают всю природу и человеческое поведение и всем хорошо знакомы.
Изложенные соображения и привели к мысли, что для обеспечения гарантированной работы математики без возникновения парадоксов (типа расселовского или других, не открытых еще, антиномий) следует считать осуществимыми (хотя, в общем случае, только потенциально) лишь те вычислительные процессы, которые реализуются рекурсивными функциями. Но не будет ли такое ограничение обеднять математику, лишать ее ценных вычислительных средств, которые не могут быть сведены к «композицию рекурсивных функций?
По мере углубления в проблему выяснялось, что все «обиходные» функции, принятые в анализе, выражаются через рекурсивные функции, так что в этом плане обеднения не происходит. Учитывая этот факт, А. Чёрч в 1936 году выдвинул гипотезу, получившую название тезиса Чёрча, которая может быть сформулирована следующим образом: вычислимы те, и только те, математические объекты, которые могут быть получены с помощью общерекурсивиых функций. Другими словами, Чёрч предположил, что общерекурсивных функций достаточно для реализации любой строгой и однозначно определяемой вычислительной процедуры.
В том же 1936 году С. К. Клини ввел понятие частично рекурсивной функции, с которым естественно связывается аналогичная гипотеза относительно частично рекурсивных функций (случаю, когда рекурсивная функция для некоторого набора аргументов не определена, здесь соответствует ситуация вычислительного процесса, продолжающегося неограниченно долго). Эту более общую гипотезу также нередко называют тезисом Чёрча[5].
Иногда шутят: в математике тезисы хороши тем, что их не не нужно доказывать. Действительно, тезис Чёрча (как и два других тезиса, о которых речь пойдет ниже) недоказуем математически. Об этом очень ясно сказал Ласло Кальмар[6]. «В своем знаменитом исследовании неразрешимых арифметических проблем Чёрч[7] использовал рабочую гипотезу о тождественности понятия эффективно вычислимой функции понятию общерекурсивной функции... Эта рабочая гипотеза известна под названием тезиса Чёрча. Она имеет несколько эквивалентных форм... В настоящей статье я не буду опровергать тезис Чёрча. Этот тезис не есть математическая теорема, которая может быть доказана или опровергнута в строго математическом смысле, поскольку он устанавливает тождество двух понятий, из которых только одно определено математически, в то время как другое употребляется математиками без точного определения. Конечно, тезис Чёрча можно замаскировать под определение: мы называем арифметическую функцию эффективно вычислимой тогда, и только тогда, когда она является общерекурсивной; однако в этом случае появляется опасность, что в будущем кто-нибудь построит функцию, которая, с одной стороны, не будет эффективно вычислимой в установленном таким образом смысле, а с другой стороны, ее значения будут очевидно эффективно вычислимыми для любых заданных аргументов.
Точно так же, если установить по определению, что проблема, содержащая параметр, пробегающий натуральные числа, разрешима тогда, и только тогда, когда ее характеристическая функция[8] общерекурсивна, возникает опасность, что кто-нибудь в будущем решит проблему, не разрешимую в смысле данного определения. Поэтому мне кажется более целесообразным смотреть на такие утверждения, как тезис Чёрча или отождествление разрешимых проблем с проблемами, обладающими общерекурсивными характеристическими функциями, не как на определения, а скорее как на суждения, правда, суждения не математические, а пред-математические. То обстоятельство, что более двух страниц статьи Чёрча наполнены аргументами в пользу убедительности его тезиса (и, следовательно, носят пред-математический характер), показывает, что его собственное мнение на этот счет не слишком отличается от моего».
Тем не менее за гипотезой Чёрча стоит весь громадный опыт математики как «вычислительной» науки, глубокое проникновение в природу математической истины. Значение гипотезы Чёрча с годами росло; в «век кибернетики» она стала много интереснее, чем казалась тридцать лет назад, когда ее смысл трудно было, наверно, даже объяснить математикам, не специализирующимся в области логики.
В приведенной выше цитате Л. Кальмар упоминает об эквивалентных формах гипотезы Чёрча. Он имеет в виду прежде всего следующие два тезиса, равносильных, как было строго доказано, тезису Чёрча: тезис Тьюринга и тезис Маркова. Эти «переформулировки» чёрчевской гипотезы заслуживают большого внимания как с философской, так и с кибернетической точки зрения.
Чёрч, Тьюринг и Марков подходят к проблеме с разных сторон, кладут в основу своих построений разные «пред-математические» соображения, причем эти соображения, как мы увидим, все более удаляются от представлений классической математической интуиции. И тот факт, что их теории оказались охватывающими в некотором смысле один и тот же круг процессов, явился серьезным подтверждением (хотя и не доказательством) каждого из тезисов: трудно допустить, что ложные построения, основанные на совершенно разных посылках, окажутся в точности совпадающими, в то время как если предположить, что они истинны, такое совпадение объясняется очень просто: истина едина.
Но не только в такой взаимной «подстраховке» состоит значение «множественности» тезисов вычислимости. Если спуститься с небес на землю и говорить не о вычислимости «в принципе», а о конкретной вычислимости, осуществимой не потенциально, а реальным образом, то три аппарата уже окажутся далеко не эквивалентными — каждый из них имеет свои технические особенности, и то, что легко поддается одному аппарату, представляет собой большую сложность для другого. Поэтому для кибернетики, остро интересующейся вычислимостью в реальное время и с реальными ограничениями, наложенными на объем памяти, развитие разных теорий вычислимости представляет большую ценность.
В том же году (1936), когда Чёрч выдвинул свой тезис о рекурсивных функциях, английский математик и логик Алан Тьюринг (1912—1954) в поисках элементарных действий, к которым можно свести всякую процедуру вычисления, решил стать на путь ее «механизации». Он исходил из представления, что механические операции являются наиболее простыми и надежными. Однако Тьюринг был далек от стремления изготовить какой-то механизм из железа или других материалов; его интересовала теоретическая сторона дела. Ему важно было убедиться в принципиальной осуществимости такой машины, которая в состоянии проделать любую вычислительную процедуру[9].
