- •Вопрос 1
- •Вопрос 2
- •Вопрос 3
- •Вопрос 4
- •Вопрос 5
- •Вопрос 6
- •Вопрос 7
- •Вопрос 8
- •Вопрос 9
- •Вопрос 10
- •Вопрос 11
- •Вопрос 12
- •Вопрос 13
- •Вопрос 14
- •Вопрос 15
- •Вопрос 16
- •Вопрос 17
- •Вопрос 18
- •Вопрос 19
- •Вопрос 20
- •Вопрос 21
- •Вопрос 22
- •23 Частично и общерекурсивные функции.
- •Вопрос 24
- •Вопрос 25
- •Вопрос 27
- •Вопрос 28
- •Вопрос 29
- •Вопрос 30
- •Вопрос 31
- •Вопрос 32
- •Вопрос 33
- •Вопрос 34
- •.Вопрос 35
- •Вопрос 36
- •Вопрос 37
- •Вопрос 38
- •Вопрос 39
- •Вопрос 40-41
- •Вопрос 42
- •Вопрос 43
- •Вопрос 44
- •Вопрос 45
- •1 Год сек. Тобит – предел Бреммермана
- •Вопрос 46
- •Вопрос 47
- •Вопрос 48
- •7 Неразрешимых проблем:
- •Вопрос 49
- •§5.2 Полиномиальные и экспоненциальные алгоритмы
- •Вопрос 50
Вопрос 21
Проблема сходимости Поста
Пост в 1944 году сформулировал проблему. Изучая неразрешимые породимые множества, было обнаружено, что заведомо не разрешимые проблемы сводятся друг к другу.
Одним из основных методов доказательства сводимости одной проблемы к другой является диагональная конструкция. Формулируется эталонная проблема и по отношению к ней устанавливается неразрешимость любой проблемы.
Проблема сводимости Поста получила отрицательное решение, это значит, что существуют различные категории неразрешимых проблем.
Пусть х и у ансамбли, P принадлежит х, Q принадлежит y. А и В – проблема разрешения для P и Q. Сводимость проблемы В к проблеме А или сводимость по разрешимости множества Q к множеству P означает наличие некоторого единого способа преобразования информации о пренадлежности или не пренапренадлежности элементов x в информацию о пренадлежности или нет Q заданного произведения образом эл-та y.
Проблема сводимости поста породила следующие направления исследования:
1 Может ли быть решена эта проблема методами Поста
2 Исследование степеней неразрешимости. НА совокупности всех множеств в ансамбле задается предпорядок P>Q => проблема разрешения для Q, сводится к разрешению P. Степени неразрешимости называют Тьюринговыми степенями. Все разрешимые множества имеют степень 0, неразрешимые породимые множества 1.
Вопрос 22
Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что
если f(n) определено для некоторого натурального n, то алгоритм A останавливается на входе n и печатает f(n) ;
если f(n) не определено, то алгоритм A не останавливается на входе n.
Несколько замечаний по поводу этого определения:
Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определенная функция вычислима (в качестве A надо взять программу, которая всегда зацикливается).
Можно было бы изменить определение, сказав так: " если f(n) не определено, то либо алгоритм A не останавливается, либо останавливается, но ничего не печатает ". На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).
Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1} ), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, " конструктивные объекты ". Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.
Для функций, скажем, с действительными аргументами и значениями понятие вычислимости требует специального определения. Здесь ситуация сложнее, определения могут быть разными, и мы о вычислимости таких функций говорить не будем. Отметим только, что, например, синус (при разумном определении вычислимости) вычислим, а функция sign(x), равная -1, 0 и 1 при x < 0, x = 0 и x > 0 соответственно - нет. Точно так же требует специального определения вычислимость функций, аргументами которых являются бесконечные последовательности нулей и единиц и т.п.