упражнения 2 (1162151), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Пусть π — произвольная программа машины Тьюринга, α — ленточная конфигурация, являющаяся заключительной для программы π. Каково множествовычисленных ответов на запрос ? P (X, Y, lef t(α), right(α)) к логической программе Pπ ?Упражнение 1.128. Частично-рекурсивной функцией называется всякая частично определенная функция натурального аргумента f (n) : Nn0 → N0 , которая может быт построена избазовых функций• константы 0,• функции следования s(1) (x) = x + 1,32Глава 1. УПРАЖНЕНИЯ• селекторных функций I (n) (x1 , x2 , . .

. , xn ) = xm , n ≥ 1, 1 ≤ m ≤ n,при помощи следующих операций:(m)(m)1. суперпозиция S: для любой функции f (n) и набора из n функций g1 , . . . , gn , в результате применения операции суперпозиции S[f, g1 , . . . , gn ] образуется функцияh(m) (x1 , . . . , xm ) = f (g1 (x1 , . . .

, xm ), . . . , gn (x1 , . . . , xm ));2. примитивная рекурсия Π: для любой пары функций f (n) и g (n+2) в результате применения операции примитивной рекурсии Π[f, g] образуется функция h(n+1) (x1 , . . . , xn , xn+1 ),удовлетворяющая для любого набора значений переменнных x1 , . . . , xn и любого натурального числа k следующим двум равенствам:h(x1 , . . . , xn , 0) = f (x1 , . .

. , xn ),h(x1 , . . . , xn , k + 1) = g(x1 , . . . , xn , k, h(x1 , . . . , xn , k));3. неограниченная минимизации µ: для любой функции f (n) , n ≥ 1 в результате применения операции неограниченной минимизации µ[f ] образуется функция h(n) (x1 , . . . , xn ),значение которой для любого набора значений переменнных x1 , . . . , xn−1 , xn удовлетворяет следующему соотношению:k,если существует такое натуральное число k, чтоi) выполняется равенство f (x1 , .

. . , xn−1 , k) = xn ,ii) для любого m, 0 ≤ m ≤ k − 1,значение функции f (x1 , . . . , xn−1 , m)h(x1 , . . . , xn−1 , xn ) =определено и отлично от xn ,неопределено в противном случае.Из тезиса Черча следует, что класс эффективно вычислимых арифметических функций совпадает с классом частично-рекурсивных функций. Поэтому для доказательства алгоритмической полноты хорновских логических программ достаточно показать, что все частичнорекрсивные функции могут быть вычислены логическими программами.Условимся представлять натуральные числа в виде списков: пустой список nil будет обозначать число 0, одноэлементный список nil nil — число 1, список nil nil nil — число 2 и т.

д.Список, соответствующий натуральному числу k, будем обозначать k.Покажите, что для каждой частично-рекурсивной функции f (x1 , . . . , xn ) можно ввести пре(n+1)дикатный символ Pfи построить такую хорновскую логическую программу Pf , котораяна любой запрос G : ? Pf (k1 , . . . , kn , Y ).. .• вычисляет единственный ответ {Y /m} тогда и только тогда, когда f (k1 , . . .

, kn ) = m,• не имеет успешных вычислений тогда и только тогда, когда значение f (k1 , . . . , kn ) неопределено.Упражнение 1.129. Выясните, можно ли построить алгоритмы, способные для любойхорновской логической программы P, произвольного запроса G и произвольной подстановкиθ выяснить,1.13. Алгоритмическая полнота и алгоритмическая неразрешимость.331. является ли дерево SLD-резолютивных вычислений запроса G к логической программеP конечным?2. является ли подстановка θ правильным ответом на запрос G к программе P?3. является ли подстановка θ вычисленным ответом на запрос G к программе P?4. существует ли хотя бы один запрос к программе P, для которого существует успешноевычисление?5.

существует ли бесконечно много различных успешных вычислений запроса G к программе P?6. верно ли, что нак запрос G программа P вычисляет то же самое множество ответов,что и некоторая заданная хорновская логическая программа P 0 ?Упражнение 1.130. Докажите, что ни одна система автоматического доказательства теорем не может гарантировать решения следующих вопросов для произвольных формул логикипредикатов:1.

является ли заданное предложение ϕ логическим следствием заданного множества предложений Γ?2. является ли заданная формула ϕ противоречивой?3. является ли заданная формула ϕ выполнимой?4. является ли выполнимой система дизъюнктов Γ = {D1 , . . . , DN }, каждый дизъюнкт Diкоторой содержит не более двух литер?5. имеет ли заданное предложение ϕ конечную модель?6. являются ли две формулы логики предикатов ϕ1 и ϕ2 равносильными?Упражнение 1.131. Алгоритмическая неразрешимость проблемы общезначимости для логики предикатов первого порядка не отменяет возможности построения алгоритмов, проверяющих общезначимость формул специального вида.Докажите, что существует алгоритм, проверяющий общезначимость т.

н. ∀-формул, предваренная нормальная форма которых имеет вид∀x1 ∀x2 . . . ∀xn ϕ(x1 , x2 , . . . , xn ).Каков этот алгоритм?Упражнение 1.132. Докажите, что не существует алгоритма, проверяющего общезначимость т. н. ∃-формул, предваренная нормальная форма которых имеет вид∃x1 ∃x2 . . . ∃xn ϕ(x1 , x2 , . .

. , xn ).А существует ли алгоритм проверки общезначимости ∃-формул, в матрице ϕ(x1 , x2 , . . . , xn )которых не содержится функциональных символов?34Глава 1. УПРАЖНЕНИЯУпражнение 1.133. Докажите, что не существует алгоритма, проверяющего общезначимость формул, предваренная нормальная форма которых имеет вид∃x1 ∃x2 ∃x3 ∀y1 . . . ∀yn ϕ(x1 , x2 , x3 , y1 , . . . , yn ),где n ≥ 1.Упражнение 1.134.

Диадической логикой называется множество формул логики предикатов, содержащих только двухместные предикатные символы. Постройте алгоритм, которыйдля произвольной формулы логики предикатов ϕ строит такую формулу диадической логикиϕ∗ , для которой верно соотношение:|= ϕ ⇐⇒ |= ϕ∗ .Докажите, что проблема общезначимости формул диадической логики алгоритмически неразрешима.Упражнение 1.135. Докажите, что не существует алгоритма, проверяющего общезначимость формул диадической логики, построенных в сигнатуре σ = h∅, ∅, {P (2) }i, т. е.

формул несодержащих констант и функциональных символов и содержащих только один двухместныйфункциональный символ P (2) .Упражнение 1.136. Постройте алгоритм, проверяющий общезначимость формул монади(1)(1)(1)ческой логики, т. е. формул, которые строятся в сигнатуре σ = h∅, ∅, {P1 , P2 , . . . , PN }i,не содержащей констант и функциональных символов и содержащей только одноместныепредикатные символы P1 , P2 , .

. . , PN .Сохранится ли алгоритмическая разрешимость проблемы общезначимости для формул, построенных из одноместных предикатов, в том случае, если в этих формулах наряду с предикатами разрешить использовать многоместные функциональные символы?.

Характеристики

Список файлов ответов (шпаргалок)