США
Американский математик и логик.
«Чёрч и Тьюринг, независимо друг от друга, сформулировали идею, гласящую, что функция вычислима, если она рекурсивна. Так называемый «тезис Чёрча-Тьюринга» помог К. Гёделю в его математических исследованиях. Как известно, в 1931 г. Гёдель доказал, что в элементарной математике имеются истины, которые не могут быть доказаны или опровергнуты на базе соответствующих аксиом внутри данной системы»
Жоль К.К., Логика в лицах и символах, М., «Aст»; «Восток-Запад», 2006 г., с.281.
«Алонзо Чёрч в 1936 г. выдвинул гипотезу, получившую название тезиса Чёрча, которая может быть сформулирована следующим образом: всякая вычислимая функция общерекурсивна. Иными словами, Чёрч предположил, что общерекурсивных функций достаточно для реализации любой строгой и однозначно определяемой вычислительной процедуры.
В том же 1936 г. С.К. Клини ввёл понятие частично рекурсивной функции, с которым естественно связывается аналогичная гипотеза относительно частично рекурсивных функций (случаю, когда рекурсивная функция для некоторого набора аргументов не определена, здесь соответствует ситуация вычислительного процесса, продолжающегося неограниченно долго). Эту более общую гипотезу также нередко называют тезисом Чёрча.
Существующая шутка - преимущество заранее постулированных тезисов в том, что они не требуют логических или математических доказательств, - хорошо передаёт возникшую ситуацию.
Действительно, тезис Чёрча (как и два других тезиса, речь о которых ниже), строго говоря, недоказуем.
Предоставим в этой связи слово Ласло Кальмару. «В своём знаменитом исследовании неразрешимых арифметических проблем Чёрч использовал одну рабочую гипотезу, а именно, гипотезу о тождественности понятия эффективно вычислимой функции понятию общерекурсивной функции [...] Эта рабочая гипотеза известна под названием тезиса Чёрча. Она имеет несколько эквивалентных форм. [...] В настоящей статье я не намерен опровергать тезис Чёрча. Этот тезис не есть математическая теорема, которая может быть доказана или опровергнута в строго математическом смысле, поскольку он устанавливает тождество двух понятий, из которых только одно определено математически, в то время как другое употребляется математиками без точного определения. Конечно, тезис Чёрча можно замаскировать под определение: мы называем арифметическую функцию эффективно вычислимой тогда и только тогда, когда она является общерекурсивной; однако в этом случае появляется опасность, что в будущем кто-нибудь определит функцию, которая, с одной стороны, не будет эффективно вычислимой в установленном смысле, а с другой стороны, её значения будут, очевидно, эффективно вычислимыми для любых заданных аргументов. Точно так же если установить по определению, что проблема, содержащая параметр, пробегающий натуральные числа, разрешима тогда и только тогда, когда её характеристическая функция общерекурсивна, возникает опасность, что кто-нибудь в будущем решит проблему, неразрешимую в смысле данного определения. Поэтому мне кажется более целесообразным смотреть на такие утверждения, как тезис Чёрча или отождествление разрешимых проблем с проблемами, обладающими общерекурсивными характеристическими функциями, не как на определения, а скорее как на суждения, правда, суждения не математические, а пред-математические. То обстоятельство, что более двух страниц Чёрча наполнены аргументами в пользу убедительности его тезиса (и, следовательно, носят пред-математический характер), показывает, что его собственное мнение на этот счёт не слишком отличается от моего».
Тем не менее за тезисом Чёрча стоит громадный опыт математики как «вычислительной» науки, глубокое проникновение в природу математической истины. Неудивительно поэтому, что осознание его значимости с годами росло; в «эпоху информатики и кибернетики» он воспринимается как нечто совершенно естественное, иначе, чем пятьдесят-шестьдесят лет назад, когда его смысл трудно было, наверное, даже объяснить математикам, не знакомым с логикой.
В словах Л. Кальмара упоминаются эквиваленты тезиса Чёрча. Имеются в виду прежде всего следующие две гипотезы, равносильные, как было строго доказано, чёрчевской; тезис Тьюринга и тезис Маркова. Эти «переформулировки» тезиса Чёрча заслуживают внимания как с философской, так и с информационно-кибернетической точки зрения.
Чёрч, Тьюринг и Марков подходят к проблеме с разных сторон, кладут в основу своих построений разные «пред-математические» соображения, причём эти соображения, как будет видно из дальнейшего изложения, всё более удаляются от представлений «обычной» математической интуиции. И тот факт, что их теории оказались охватывающими в некотором смысле один и тот же круг процессов, явился серьёзным подтверждением (хотя и не доказательством) каждого из тезисов: трудно допустить, чтобы ложные построения, базирующиеся на совершенно разных предпосылках, оказались, по сути дела, совпадающими, в то время как допущение истинности рассматриваемых «тезисов» объясняет это совпадение очень просто: истина едина.
Однако не только в подобной взаимной «подстраховке» состоит значение «множественности» тезисов вычислимости. Если с заоблачных высот абстракции спуститься на грешную землю и говорить не о вычислимости «в принципе», а о конкретной вычислимости, осуществимой не потенциально, а реальным образом, то эти три теоретических аппарата окажутся далеко не эквивалентными - каждый из них имеет свои особенности, и то, что легче поддается одному, представляет сложность для другого. Поэтому для информатики, остро интересующейся вычи-слимостью в реальное время и с реальными ограничениями, наложенными на объем памяти, разработка и изучение различных теорий вычислимости имеют значительную ценность.
В том же 1936 г., когда Чёрч представил на суд научного мира свой тезис о рекурсивных функциях, английский математик и логик Алан Тьюринг (1912-1954) в поисках элементарных действий, к которым можно свести всякий процесс вычисления, стал на путь его «механизации». При этом он исходил из основных свойств вычислительных процедур как познавательных процессов, выполняемых человеком. Изложение его исходной позиции сделано так выразительно, так ясно, как это умеют делать только классики научной мысли».
Бирюков Б.В., Тростников В.Н., Жар холодных числе и пафос бесстрастной логики, М., «Едиториал УРСС», 2004 г., с. 136-137.
Регистрация на конференц
Страница конференции во ВКонтакте: 
