LectLog16 (Старые лекции, в целом тоже самое)

Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А. ЗахаровЛекция 16.Алгоритмическая полноталогических программ.Моделирование машин Тьюрингалогическим программами.Теорема Черча.АЛГОРИТМИЧЕСКАЯ ПОЛНОТАВопросы:А что могут вычислятьхорновские логическиепрограммы?Какие задачи можно решать с ихпомощью, а какие нельзя?АЛГОРИТМИЧЕСКАЯ ПОЛНОТАЕсть много разных моделей вычислений. Одни из них проводятвычисления над строками (словами), другие — над графами,третьи — над молекулами ДНК, и т. п.

Как сравнить ихвычислительные способности?Структуры данных, над которыми работают эти модели,позволяют кодировать натуральные числа. Поэтому чтобысравнить вычислительные способности алгоритмическихмоделей, достаточно выяснить, какие функции натуральногоаргумента способны вычислять эти модели.Исследования показали, что все известные алгоритмическиемодели способны вычислять только частично-рекурсивныефункции натурального аргумента. Это открытие далооснование многим математикам (Тьюринг, Черч, Клини,Гедель, Марков и др.) выдвинуть следующий тезис.АЛГОРИТМИЧЕСКАЯ ПОЛНОТАТезис ЧерчаКласс эффективно (алгоритмически) вычислимых функцийарифметических функций в точности совпадает с классомарифметических функций, вычислимых в каждой изперечисленных ниже моделей вычисленийIмашины Тьюринга—Поста,Iλ-исчисление Черча—Клини,Iсистемы равенств Эрбрана—Геделя,Iалгорифмы Маркова,Iсистемы Колмогорова—Шенхаге,Iмашины Минского,I...Модели вычислений такого вида называются алгоритмическиполными .

Найдется ли место в этом ряду для хорновскихлогических программ?АЛГОРИТМИЧЕСКАЯ ПОЛНОТАДля того чтобы убедиться в алгоритмической полнотехорновских логических программ, достаточно взять любую изперечисленных алгоритмически полных моделей вычислений(например, машины Тьюринга) и показать, что для любойпрограммы Π в выбранной модели найдется подходящаялогическая программа PΠ , воспроизводящая (моделирующая)вычисления программы Π.Итак, вспомним, как устроены машины Тьюринга, и попробуемпостроить логическую программу-интерпретатор машинТьюринга.АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины Тьюринга0Программа1111011110- q1?Команды:увидев "1", стереть его, записать "0" и сдвинуться вправоАЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины Тьюринга0Программа111001- q2?Команды:1110АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины Тьюринга0Программа1110011110- q2?Команды:увидев "0", стереть его, записать "1" и сдвинуться влевоАЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины Тьюринга0Программа11101- q3?Команды:11110АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины ТьюрингаБолее строго модель вычислений машин Тьюрингаописывается так.Задан ленточный алфавит A = {a0 , a1 , a2 , .

. . , an },в котором особо выделен одна из букв a0 (пустой символ ).Ленточным словом назывется всякое слово в алфавите A.Множество всех ленточных слов обозначим A∗ . Для каждогослова w = z1 z2 . . . zn−1 zn будем использовать запись w −1 дляобозначения обратного слова zn zn−1 . . . z2 z1 .Задан алфавит состояний Q = {q0 , q1 , q2 , . . . , qm },в котором особо выделено одно из состояний q0 (начальноесостояние ).АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины ТьюрингаЛенточной конфигурацией называется всякое слово видаw 0 q x w 00 ,гдеIq — состояние, q ∈ Q,Ix — ленточная буква, x ∈ A,Iw 0 , w 00 — ленточные слова, w 0 , w 00 ∈ A∗ .Iq — это то состояние, в котором находится МТ,Ix — это буква, которая записана в той ячейке ленты,которую обозревает считывающая головка МТ,Iw 0 — это ленточное слово, составленное из символов,записанных слева от обозреваемой ячейки,Iw 00 — это ленточное слово, составленное из символов,записанных справа от обозреваемой ячейки.По умолчанию считается, что во всех остальных ячейках лентызаписаны пустые символы.АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины Тьюринга011110111q1Ленточная конфигурация: 0111q1 101111010АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины ТьюрингаЛенточная конфигурация вида u q0 x v называется начальнойконфигурацией .Множество всех конфигураций обозначим ConfA,Q .0 .Множество всех начальных конфигураций обозначим ConfA,QАЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины ТьюрингаКомандой называется всякая пятерка видаq x y q 0 D,гдеIq, q 0 — состояния, q, q 0 ∈ Q,Ix, y — ленточные буквы, x, y ∈ A,ID — направление сдвига головки, D ∈ {L, R}.Эту команду нужно понимать так:если МТ находится в состянии q и обозревает символ x, тозаписать в обозреваемую ячейку символ y , перейти в состояниеq 0 и сдвинуть считывающую головку на одну ячейку внаправлении D.АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины ТьюрингаКаждая команда K задает отношение перехода →K намножестве ленточных конфигурацийα →K βОно определяется так:Iесли α = uzqxv и K = qxyq 0 L, то β = uq 0 zyv ,Iесли α = qxv и K = qxyq 0 L, то β = q 0 a0 yv ,Iесли α = uqxzv и K = qxyq 0 R, то β = uyq 0 zv ,Iесли α = uqx и K = qxyq 0 R, то β = uyq 0 a0 .АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины ТьюрингаПрограмма машины Тьюринга — это произвольное множествокоманд π = {K1 , K2 , .

. . , KN }. Программа π называетсядетерминированной , если для любых двух команд этойпрограммыKi = qi xyqi0 Di ,Kj = qj ztqj0 Dj ,выполняется хотя бы одно из двух условий qi 6= qj , x 6= z.Программа π задает отношение переходовна множествеSленточных конфигураций →π =→K .K ∈πКонфигурация α называется заключительной для программыπ, если не существует никакой конфигурации β, для которыхвыполняется α →π β. Это означает, что α = u q x v , и впрограмме π нет ни одной команды K = qx....АЛГОРИТМИЧЕСКАЯ ПОЛНОТАМашины ТьюрингаВычислением машины Тьюринга с программой π на начальнойконфигурации α0 , α0 ∈ Conf 0 называется последовательностьконфигурацийπ(α0 ) = α0 , α1 , α2 , . .

. , αi , αi+1 , . . .удовлетворяющая следующим условиям:Iдля любого i, i ≥ 0, верно αi →π αi+1 ;Iпоследовательность π(α0 ) либо является бесконечной,либо заканчивается заключительной конфигурацией αN .В последнем случае αN называется результатом вычисления .Результат бесконечного вычисления считается неопределенным.Ясно, что вычисление π(α0 ) детерминированной машиныТьюринга однозначно определяется начальной конфигурациейα0 и программой π.МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИЧтобы логические программы могли моделировать вычислениямашин Тьюринга, нужно выбрать подходящие логическиеконструкции для представления конфигураций и команд.Ленточные слова будем представлять списками:слово w = z1 z2 . . .

zn будет представлено спискомlist(w ) = z1 z2 . . . zn nil... ..Каждая ленточная конфигурация α = u q z v будетпредставлена парой списков left(α), right(α), гдеleft(α) = list(u −1 ),right(α) = q z list(v )...Например,left(0111q1 1011110) = 1 1 1 0 nil,right(0111q1 1011110) = q1 1 0 1 1 1 1 0 nil.............МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИКаждой команде K = q b c q 0 L сопоставим пару программныхутверждений D1 (K ), D2 (K ):.

..... ... ..D1 (K ) : P(Z X , q b Y , X 0 , Y 0 ) ← P(X , q 0 Z c Y , X 0 , Y 0 );D2 (K ) : P(nil, q b Y , X 0 , Y 0 )← P(nil, q 0 a0 c Y , X 0 , Y 0 );Каждой команде K = q b c q 0 R сопоставим пару программныхутверждений D1 (K ), D2 (K ):.. .... ... . .D1 (K ) : P(X , q b Z Y , X 0 , Y 0 ) ← P(c X , q 0 Z X , X 0 , Y 0 );D2 (K ) : P(X , q b nil, X 0 , Y 0 )← P(c X , q 0 a0 nil, X 0 , Y 0 );МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИКроме того, для каждой пары q, z, где q ∈ Q, z ∈ A, введемфакт Dq,z :....Dq,x : P(X , q x Y , X , q x Y ) ←;Теперь для каждой машины Тьюринга π = {K1 , K2 , .

. . , KN }выделим множество Tπ всех пар qx, которые не являютсяначалами ни одной из команд программы π...и построим хорновскую логическую программу[Pπ = {D1 (K ), D2 (K ) : K ∈ π} ∪Dqx .(qx∈Tπ )Можно надеяться, что логическая программа Pπвоспроизводит все вычисления машины Тьюринга π.МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИПримерПустьK1 =K2 =K3 =A = {0, 1} и пусть π = {K1 , K2 , K3 }, гдеq0 0 1 q1 R,q1 0 1 q0 L,q1 1 1 q1 R.Машина Тьюринга c программой π транслируется влогическую программу Pπ .МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИПримерЛогическая программа Pπ :..

...P(Z .X , q .0.Y , X , Y )P(nil, q .0.Y , X , Y )P(X , q .1.Z .Y , X , Y )P(X , q .1.nil, X , Y )P(X , q .1.Z , X , q .1.Z )P(X , q0 0 Z Y , X 0 , Y 0 )P(X , q0 0 nil, X 0 , Y 0 )01100110000000. ... ..P(X , q .Z .1.Y , X , Y );P(nil, q .0.1.Y , X , Y );P(1.X , q .Z .Y , X , Y );P(1.X , q .0.nil, X , Y );← P(1 X , q1 Z Y , X 0 , Y 0 );← P(1 X , q1 0 nil, X 0 , Y 0 );←←←←← ;001100000000МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИЛемма 1Для любой пары ленточных конфигураций α, β ∈ Conf икоманды K отношение перехода α →K β выполняется тогда итолько тогда, когда запросGα : ?P(left(α), right(α), X , Y )и одно из программных утверждений D1 (K ), D2 (K )имеют SLD-резольвенту Gβ :?P(left(β), right(β), X , Y ).ДоказательствоСамостоятельно.МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИЛемма 2Ленточная конфигурация α ∈ Conf является заключительнойдля машины Тьюринга π тогда и только тогда, когда запросGα : ?P(left(α), right(α), X , Y )Sи одно из программных утверждений множестваDqx(qx∈Tπ )имеют пустой дизъюнкт в качестве SLD-резольвенты.ДоказательствоСамостоятельно.МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИТеорема (о моделировании МТ логическимипрограммами)Для любой машины Тьюринга π и начальной конфигурации α0вычислениеα0 →π α1 →π α2 →π · · · →π αNзавершается заключительной конфигурацией αN тогда итолько тогда, когда запросGα0 : ?R(left(α0 ), right(α0 ), X , Y )к хорновской логической программе Pπ имеет успешноевычисление с вычисленным ответомθ = {X /left(αN ), Y /right(αN )}.ДоказательствоСледует из лемм 1 и 2.МОДЕЛИРОВАНИЕ МАШИН ТЬЮРИНГАЛОГИЧЕСКИМИ ПРОГРАММАМИТаким образом, хорновские логические программы обладаютне меньшими вычислительными воможностями, чем машиныТьюринга.

Значит, логическое программирование — этоуниверсальная модель вычислений, позволяющая вычислятьвсе эффективно вычислимые функции.Но это также означает, что логическому программированиюприсущи все те трудности анализа поведения программ,которые присущи и другим универсальным моделямвычислений. Речь идет об алгоритмически неразрешмыхзадачах.Например, интересен вопрос о том, можно ли по заданномузапросу G к логической программе P выяснить, имеет ли этотзапрос хотя бы одно успешное вычисление. Тогда не пришлосьбесполезно тратить время на построение дереваSLD-резолютивных вычислений.ТЕОРЕМА ЧЕРЧАТеорема Тьюринга об алгоритмическойнеразрешимости проблемы остановаПроблема останова машин Тьюринга алгоритмическинеразрешима, т.