Сборник задач для самостоятельных занятий, страница 7

Алгоритмическая полнота и алгоритмическая неразрешимость.313. Программа порождает всевозможные суффиксы заданного слова L, представленногосписком букв. Обращение к программе должно имет вид ? all_suffixes(L,X).4. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , .

. . , an },содержащихся в списке L однократно. Обращение к программе должно имет вид ?single(L,X).5. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , . . . , an },содержащихся в списке L многократно. Обращение к программе должно имет вид ?multiple(L,X).6. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , . . . , an },содержащихся в списке L1 и не содержащихся в списке L2 . Обращение к программедолжно имет вид ? filter(L1,L2,X).7. Программа порождает всевозможные сочетания элементов заданного бесповторного списка L1 .

Обращение к программе должно имет вид ? combination(L1,X).8. Программа порождает всевозможные сочетания элементов заданного бесповторного списка L1 , длина которых равна длине заданного списка L2 . Обращение к программе должноимет вид ? combination2(L1,L2,X).9. Программа порождает всевозможные сочетания c повторением элементов заданного бесповторного списка L1 , длина которых равна длине заданного списка L2 . Обращение кпрограмме должно имет вид ? combination_repit(L1,L2,X).1.13Алгоритмическая полнота и алгоритмическая неразрешимость.Упражнение 1.125. Возьмите ленточную конфигурацию α0 , представленную на рис. ??, ипостройте дерево SLD-резолютивных вычислений для запроса ? P (lef t(α0 ), right(α0 ), X, Y ),обращенного к логической программе Pπ , представленной на рис.

??.Упражнение 1.126. Какое устройство имеют деревья SLD-резолютивных вычислений запросов ? P (lef t(α), right(α), X, Y ), обращенных к логическим программам Pπ , соответствующим детерминированным программам машин Тьюринга.Упражнение 1.127. Пусть π — произвольная программа машины Тьюринга, α — ленточная конфигурация, являющаяся заключительной для программы π. Каково множествовычисленных ответов на запрос ? 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 .Сохранится ли алгоритмическая разрешимость проблемы общезначимости для формул, построенных из одноместных предикатов, в том случае, если в этих формулах наряду с предикатами разрешить использовать многоместные функциональные символы?.