Тезис Чёрча

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

· Гёдель-Эбран-Клини. Общерекурсивные функции, определенные с помощью исчисления рекурсивных уравнений [23, с. 261-278].

· Пост. Функции, определяемые каноническими дедуктивными системами [13, с. 66-72].

· Марков. Функции, задаваемые некоторыми алгоритмами (известные под названием нормальные алгоритмы) над конечным алфавитом [23, с.228-250].

· Шепердсон-Стерджис. МНР-вычислимые функции [13].

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

Основной результат [13, с. 57]. Каждое из вышеупомянутых уточнений эффективной вычислимости приводит к одному и тому же классу вычислимых функций.

Вопрос: насколько хорошо неформальное и интуитивное понятие эффективно вычислимой функции отражено в различных формальных описаниях?

Чёрч, Тьюринг и Марков каждый в соответствии со своим подходом выдвинули утверждение (тезис) о том, что класс определенных ими функций совпадает с неформально определенным классом вычислимых функций. В силу основного результата все эти утверждения логически эквивалентны. Название тезис Чёрча теперь применяется к этим и аналогичным им утверждениям.

Тезис Чёрча. Интуитивно и неформально определенный класс эффективно вычислимых функций совпадает с классом l-определимых функций.

Сразу же заметим, что этот тезис не является теоремой, а скорее утверждение, которое принимается на веру, причем вера подкрепляется следующими аргументами [13, с. 75-76].

· Фундаментальный результат: многие независимые варианты уточнения интуитивного понятия вычислимости привели к одному и тому же классу функций.

· Обширное семейство эффективно вычислимых функций принадлежит этому классу. Конкретные функции, рассмотренные в 6.2, образуют исходную часть этого семейства, которую можно расширять до бесконечности методами из 6.2 или более мощными и сложными методами.

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

... Найти задачу - не меньшая радость, чем отыскать решение.

Томас де Куинси

- Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.... Как же искать решения, когда его нет? Бессмыслица какая-то...

- Бессмыслица - искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет.

А. и Б. Стругацкие

"Понедельник начинается в субботу"