58. Cвязь логического программирования с искусственным интеллектом

ЛП появилось в рамках развития систем ИИ. Исторически первая задача ИИ, для которых использовалось ЛП - задача естественного языкового общения. В дальнейшем оно применялось для программирования экспертных систем и баз знаний. Типовая программа на языке ЛП состоит из набора описания фактов предметной области и набора описания правил. Т.е. соответствует классическому представлению о ядре ЭС.

59. Логическое программирование и функциональное программирование

Функциональная программа состоит из совокупности определений функций. Функции, в свою очередь, представляют собой вызовы других функций и предложений, управляющих последовательностью вызовов. Каждый вызов возвращает некоторое значение и вызвавшую ее функцию, вычисление которой после этого продолжается. Этот процесс повторяется до тех пор, пока запустившая процесс функция не вернет результат пользователю.

В логических языках программирования для решения задачи достаточно описания структуры и условий этой задачи. Поскольку последовательность и способ выполнения программы не фиксируется, как при описании алгоритма, программы могут в принципе работать в обоих направлениях, то есть программа может как на основе исходных данных вычислить результаты, так и по результатам – исходные данные.

60. Логическое программирование и параллельное программирование

Логическая программа обладает высокой степенью параллелелизма, поскольку подцели логического выражения могут выводится независимо друг от друга.

61. Логическая теория Фреге и значение её для логического программирования.

Г.Фреге первый построил систему теории множеств, которая практически была логической, поскольку основной принцип свертки: каждое свойство определяет множество удовлетворяющих ему элементов – имел неограниченную общность. Эта система оказалась противоречивой, но многие конструкции из нее использовались в дальнейшем.

62. Теория Френча и Эрбрана и значение её для логического программирования.

В 1930 г. Френч и Эрбран независимо доказали фунда­ментальную теорему, предоставляющую алгоритм, который способен установить общезначимость логической формулы, если она является таковой. В противном случае этот алгоритм зацикливается. Поэтому проблему установления общезначимости в исчислении предикатов первого порядка стали считать полуразрешимой. Разработанный алгоритм также не нашел практического приме­нения вследствие большой его трудоемкости.

63. Теория Тьюринга, значение для логического программирования.

Машина Тьюринга это абстрактная вычислительная машина. Была предложена Аланом Тьюрингом для формализации понятия алгоритма. Компоненты  В состав машины Тьюринга входит бесконечная лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы. Имеется и другая трактовка В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных). Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но следует отметить, что данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью (суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но, тем не менее, всегда конечна).