Задачи (Старые варианты экзамена), страница 7

Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программы с использованием стандартной стратегии вычисления, но лишьпри добавлении операторов is и not, потому что...4. Существуют арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что...Задача 13. Известно, что логическая программа P 0 получена из хорновской логической программы Pв результате применения следующего преобразования: в конце каждого программного утверждения (будьто процедура или факт) D : A0 ← A1 , .

. . , Am был поставлен оператор отсечения так, что образовалосьутверждение D : A0 ← A1 , . . . , Am , !. Какие из приведенных ниже утверждений всегда справедливы ипочему?1. При обращении с любым запросом G к программе P 0 стандартная стратегия вычисления выдаст те жесамые ответы, что и при обращении с запросом G к программе P, потому что...2. При обращении с любым запросом G к программе P 0 стандартная стратегия вычисления выдасттолько самый первый ответ из тех, которые выдает стандартная стратегия вычисления на запрос G кпрограмме P, потому что...3.

При обращении с любым запросом G к программе P 0 стандартная стратегия вычисления выдаст толькосамый последний ответ из тех, которые выдает стандартная стратегия вычисления на запрос G кпрограмме P, потому что...4. Ни одно из приведенных выше утверждений в общем случае неверно, потому что...Задача 13 (3 балла). Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программы с использованием стандартной стратегии вычисления, потому что...2.

Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что...3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программы с использованием стандартной стратегии вычисления, но лишьпри добавлении операторов is и not, потому что...4. Существуют арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что...Задача 13 (3 балла).

Докажите, что существует алгоритм, проверяющий общезначимость формуллогики предикатов, предваренная нормальная форма которых имеет вид∀x1 ∀x2 . . . ∀xn ϕ(x1 , x2 , . . . , xn ).Каков этот алгоритм?Задача 13 (3 балла). Известно, что формула PLTL ϕ имеет длину n, а конечная модель (LTS) Mимеет m состояний. Тогда система Хинтикки для формулы ϕ и LTS M представляет собой ориентированный граф, в котором содержится самое большее1. O(nm ) вершин, потому что....2. O(mn ) вершин, потому что....3. n2O(m) вершин, потому что....4.

m2O(n) вершин, потому что....5. 2O(nm) вершин, потому что....Задача 13 (3 балла). Из логической программы P (содержащей операторы отсечения и отрицания)с запросом G были удалены все операторы отсечения, в результате чего образовалась новая программаP 0 . Какие из приведенных ниже утверждений будут всегда верны и почему?1.

Всякое успешное вычисление запроса G к программе P будет также являться успешным вычислением запроса G к программе P 0 , потому что...2. Всякое успешное вычисление запроса G к программе P 0 будет также являться успешным вычислением запроса G к программе P, потому что...3. Всякий вычислимый ответ на запрос G к программе P будет также являться вычислимым ответомна запрос G к программе P , потому что...4. Всякий вычислимый ответ на запрос G к программе P 0 будет также являться вычислимым ответом на запрос G к программе P, потому что...5. Ни одно из приведенных выше утверждений в общем случае неверно..