Теория алгоритмов. Зюзысов В.М. - 15 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

2 Вычислимое и невычислимое
2.1 Тезис Чёрча
За последние 70 лет было предложено много различных математических уточнений
интуитивного понятия алгоритма. три из этих подхода мы разобрали. Перечислим
некоторые другие альтернативные способы, которые предлагались следующими
авторами:
Гёдель–Эбран–Клини. Общерекурсивные функции, определенные с помощью
исчисления рекурсивных уравнений [17, с. 261–278].
•
•
•
•
Пост. Функции, определяемые каноническими дедуктивными системами [11, с. 66–72].
Марков. Функции
, задаваемые некоторыми алгоритмами (известные под названием
нормальными алгоритмами) над конечным алфавитом [17, с.228–250].
Шепердсон–Стерджис. МНР–вычислимые функции [11].
Между этими подходами (в том числе, и три выше рассмотренных) имеются
большие различия; каждый из них имеет свои преимущества для соответствующего
описания вычислимости. Следующий замечательный результат получен усилиями многих
исследователей.
Теорема 5 (Основной
результат). [11, с. 57]. Каждое из вышеупомянутых
уточнений эффективной вычислимости приводит к одному и тому же классу вычислимых
функций.
Вопрос: насколько хорошо неформальное и интуитивное понятие эффективно
вычислимой функции отражено в различных формальных описаниях?
Чёрч, Тьюринг и Марков каждый в соответствии со своим подходом выдвинули
утверждение (тезис) о том, что класс определенных
ими функций совпадает с
неформально определенным классом вычислимых функций. В силу основного результата
все эти утверждения логически эквивалентны. Название тезис Чёрча теперь применяется
к этим и аналогичным им утверждениям.
Тезис Чёрча
Интуитивно и неформально определенный класс эффективно вычислимых функций
совпадает с классом частично-рекурсивных функций.
Сразу же заметим, что этот тезис не является теоремой, а скорее утверждение,
которое принимается на веру, причем вера подкрепляется следующими аргументами
[11, с. 75–76].
•
•
•
Фундаментальный результат: многие независимые инварианты уточнения
интуитивного понятия вычислимости привели к одному и тому же классу функций.
Обширное семейство эффективно вычислимых функций принадлежит этому классу.
Конкретные
функции, рассмотренные в 1.2, образуют исходную часть этого семейства,
которую можно расширять до бесконечности методами из 1.2 или более мощными и
сложными методами.
Никто еще не нашел функцию, которую можно было признать вычислимой в
неформальном смысле, но которую нельзя было бы построить, используя один из
формальных методов.
Приведем парадокс, показывающий насколько
мы подходим к опасной границе
между непротиворечивым и противоречивым в обсуждении вычислимых функций
[12, с. 184].
Легко доказать, что множество всюду определенных вычислимых функций f: N→N
является перечислимым, т. е. их можно перенумеровать в виде последовательности
f
1
, f
2
, f
3
,... .

Страницы