Лекции В.А. Захарова, страница 24

PDF-файл Лекции В.А. Захарова, страница 24 Математическая логика и логическое программирование (53065): Лекции - 7 семестрЛекции В.А. Захарова: Математическая логика и логическое программирование - PDF, страница 24 (53065) - СтудИзба2019-09-18СтудИзба

Описание файла

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 . .

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5034
Авторов
на СтудИзбе
461
Средний доход
с одного платного файла
Обучение Подробнее