Лекции В.А. Захарова, страница 24
Описание файла
PDF-файл из архива "Лекции В.А. Захарова", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 24 страницы из PDF
Результат вычисления запроса может существенноизмениться при перестановке программных утверждений.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММЕще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;..t?P(X Y )ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) tДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t(3), {X /a}t?(4), {X /c}t??ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }?t?P(Y ), R(X )(1), {Y /nil}?R(X ) t6(4), {X /c}tt?(3), {X /a}??ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t*(1), {Y /nil}?R(X ) t6(3), {X /a}t?(4), {X /c}t??ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}?R(X ) t6(3), {X /a}t?(4), {X /c}t??.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t6(3), {X /a}t?(4), {X /c}t??.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?(4), {X /c}t??.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.t?P(X Y )(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?(4), {X /c}t?(3), {X /a}?t?.ДЕРЕВЬЯ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММ.Еще раз пример 2.t?P(X Y )P : P(nil) ←;P(X L) ← P(L), R(X );R(a) ←;R(c) ←;.(2), {X1 /X , L1 /Y }??P(Y ), R(X )t* (2), {Y /X2 L2 }t??P(L2 ), R(X2 ), R(X )(1), {Y /nil}(1), {L2 /nil} ?R(X2 ), R(X ) t?R(X ) t(3), {X2 /a}6?R(X ) t(3), {X /a}t?.И Т.
Д.(4), {X /c}t?(3), {X /a}?t?СТРАТЕГИИ ВЫЧИСЛЕНИЙ ЛОГИЧЕСКИХПРОГРАММПоскольку соображения эффективности превалируют надтребованиями вычислительной полноты, в качествестандартной стратегии вычисления логических программбыла выбрана стратегия обхода в глубину с возвратом.Программист должен сам позаботиться о надлежащем порядкерасположения программных утверждений, чтобы стандартнаястратегия вычисления позволяла отыскать все вычисленныеответы.КОНЕЦ ЛЕКЦИИ 14.Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А. ЗахаровЛекция 15.Алгоритмическая полноталогических программ.Моделирование машин Тьюрингалогическим программами.Теорема Черча.АЛГОРИТМИЧЕСКАЯ ПОЛНОТАВопросы:А что могут вычислятьхорновские логическиепрограммы?Какие задачи можно решать с ихпомощью, а какие нельзя?АЛГОРИТМИЧЕСКАЯ ПОЛНОТАЕсть много разных моделей вычислений.
Одни из них проводятвычисления над строками (словами), другие — над графами,третьи — над молекулами ДНК, и т. п. Как сравнить ихвычислительные способности?Структуры данных, над которыми работают эти модели,позволяют кодировать натуральные числа.
Поэтому чтобысравнить вычислительные способности алгоритмическихмоделей, достаточно выяснить, какие функции натуральногоаргумента способны вычислять эти модели.Исследования показали, что все известные алгоритмическиемодели способны вычислять только частично-рекурсивныефункции натурального аргумента. Это открытие далооснование многим математикам (Тьюринг, Черч, Клини,Гедель, Марков, и др.) выдвинуть следующий тезис.АЛГОРИТМИЧЕСКАЯ ПОЛНОТАТезис ЧерчаКласс эффективно (алгоритмически) вычислимыхарифметических функций в точности совпадает с классомарифметических функций, вычислимых в каждой изперечисленных ниже моделей вычислений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 . .