Вопрос 18

Общее понятие исчисления (дедуктивная система)

Исчисления представляют собой список разрешительных правил – называются предупреждающими правилами или правилами вывода

Эти правила разрешают переходить от одних конструктивных правил к другим в рамках ансамбля. Подобно таму как алгоритм задает алгоритмический или вычислительный процесс исчисление задает исчислительный процесс (порождающий). Разбивается на шаги, каждый шаг состоит из полученного нового конструктивного объекта из уже полученного.

Объекты к которым применяются правила называются посылками.

Функциональное отличие алгоритма от исчисления.

Применение одного и того же правила к одним и тем же посылкам может давать разные результаты.

Для каждого правила число посылок фиксировано если все эти числа ориентированы числом (к) то исчисление называется посылочными.

Если объект B получается из объектов (a1;a2;…;aB.) применяем одно из разрешительных правил исчисления, и если (a1;a2;…;aK.) является допустимым объектом, то и B является допустимым объектом.

Начало индукции обеспечивает нуль посылочных правил (из ничего)

Объекты некоторого ансамбля W с которыми работает исчисление называется рабочей средой исчисления.и все состояния исчисляемого процесса должны лежать в W.

Вопрос 19

Разрешимое множество

Множество разрешимо если содержится в некотором ансамбле и для него существует разрешающий алгоритм.(U)

U – разрешающий алгоритм для подмножества А, ансамбля х, Если множество допустимых входов совпадает с Х, и U отвечает на вопрос (xЄХ) ЄА .

Множество разрешимо тогда и только тогда, когда его проблемма разрешения решима.

Объединение, пересечение и т.п Разрешимых множеств – разрешимы, конечное множество разрешимо, Критерии разрешимости множества заключаются в том, что множество A в ансамбле Х разрешимо тогда и только тогда, когда

А Є Gen(X) (множество породимо)

А Є х \ Gen(X) (дополнение породимо)

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

Перечислимые множества.

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

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

Признаки.

ООФ или ОЗФ множество натуральных чисел; Пустое множество всюду определено. Объеденение или пересечение перечислимы (не разность!)

Вопрос 20

Рассмотрим массовую задачу, т.е. класс П однотипных, похожих конкретных задач. Если для решения массовой задачи найден алгоритм, решающий эту задачу, то о задаче говорят как об алгоритмически разрешимой проблеме.

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

В силу тезиса Тьюринга можно считать, что под алгоритмом понимается машина Тьюринга-Поста, а на основании тезиса Чёрча следует говорить, что для алгоритмической разрешимости необходимо, чтобы решение задачи находилось с помощью частично рекурсивной функции. Отсюда вытекает, что если доказать, что решение задачи дается функцией, не являющейся частично рекурсивной, то такую задачу имеет смысл объявить алгоритмически неразрешимой.

Существуют ли алгоритмически неразрешимые проблемы (в указанном выше смысле)? Да, такие проблемы математикам известны. Таковыми является, например, проблема доказательства общезначимости формулы в исчислении предикатов (теорема Чёрча), проблема самоприменимости машин Тьюринга и проблема останова машины Тьюринга.