6. Тезис Чёрча

Чёрч [1] выдвинул тезис о том, что интуитивное понятие эффективности равнообъемно с точным математическим понятием рекурсивности, которое мы ввели. Этот тезис, известный как тезис Чёрча, можно рассматривать либо как гипотезу относительно

интуитивного понятия эффективности, либо как точную формулировку понятия, которому до сих пор не хватало математической строгости. Используя выражение Поста [1], можно сказать, что оно является фундаментальным открытием относительно границ математических способностей Homo Sapiens.

Мы попытаемся привести некоторые подтверждения тезиса Чёрча. Во-первых, можно спросить, реально ли вообще интуитивное понятие эффективности, так как иначе этот тезис был бы бессмысленным. Психологический факт состоит в том, что многие математики способны развить сильное ощущение понятия эффективности. Например, задолго до зарождения теории рекурсивных функций понятие эффективности использовалось с большой точностью Борелем [1] и Брауэром [2], который основывал на нем многие нетривиальные математические рассуждения.

Одна половина тезиса Чёрча утверждает, что рекурсивно перечислимые множества эффективно перечислимы также в интуитивном смысле. (Мы выбираем понятие рекурсивно перечислимого множества вместо рекурсивной функции в качестве основного понятия рекурсивности.) Это несомненно так: если дано рекурсивно перечислимое множество, то мы можем порождать его элементы один за другим чисто механическим путем, систематически перебирая все доказательства. Один из способов сделать это будет весьма подробно описан в п. 8.

Вторая половина тезиса Чёрча — основная. Она утверждает, что множество, эффективно перечислимое в интуитивном смысле, также и рекурсивно перечислимо. Эффективно перечислимое множество задано предписанием, содержащим конечное число слов и сообщающим нам, как порождать элементы. Мы утверждаем, что такое предписание всегда можно записать в виде канонической системы, которую можно считать чем-то вроде формализованного языка. Мы уже несколько раз демонстрировали, как неформальные предписания, написанные по-русски, могут быть переведены в соответствующим образом построенные канонические языки, и в следующем пункте будет

дано важнейшее применение этой техники. Это должно сделать правдоподобным утверждение о том, что канонические системы достаточно мощны для выражения всех возможных видов эффективных определений.

Другой более формальный тип подтверждений дается тем фактом, что многие сильно различающиеся подходы к понятию вычислимости, например

(см. скан)

оказались эквивалентными. Это сильное свидетельство в пользу тезиса Чёрча. Мы не показали ни одной из этих эквивалентностей, а установили только, что исчисление равенств и машины Тьюринга могут быть сведены к каноническим системам Поста. Это иллюстрирует технику, нужную для таких доказательств, а также позволяет нам, для подтверждения общности принятого нами определения рекурсивности, опираться на тьюринговский анализ вычислительных возможностей человека, намеченный в предыдущем пункте.

Наконец, имеется эмпирическое подтверждение: за 38 лет, прошедших с тех пор, как был выдвинут тезис Чёрча, не была получена никакая процедура, эффективная по общему признанию, но оказавшаяся нерекурсивной.