| Реферат з дисципліни «Теория алгоритмів та представлення знань» Виконав студент 3-го курсу 36 групи Левицький Е.Г. Європейський Університет Уманська філія Кафедра математики та інформатики Умань – 2005 Вступ Введение понятия машины Тьюринга уточняет понятие алгоритма и указывает путь решения какой-то массовой проблемы. Однако машина Тьюринга бывает неприменима к начальной информации (исходному слову алфавита). Та же ситуация повторяется относительно некоторых задач, для решения которых не удается создать машины Тьюринга. Один из первых результатов такого типа получен Черчем в 1936 году. Он касается проблемы распознавания выводимости в математической логике. 1). Аксиоматический метод в математике заключается в том, что все теоремы данной теории получаются посредством формально-логического вывода из нескольких аксиом, принимаемых в данной теории без доказательств. Например, в математической логике описывается специальный язык формул, позволяющий любое предложение математической теории записать в виде вполне определенной формулы, а процесс логического вывода из посылки  следствия  может быть описан в виде процесса формальных преобразований исходной формулы. Это достигается путем использования логического исчисления, в котором указана система допустимых преобразований, изображающих элементарные акты логического умозаключения, из которых складывается любой , сколь угодно сложный формально-логический вывод. Вопрос о логической выводимости следствия из посылки является вопросом о существовании дедуктивной цепочки, ведущей от формулы к формуле . В связи с этим возникает проблема распознавания выводимости: существует ли для двух формул и дедуктивная цепочка, ведущая от к или нет. Решение этой проблемы понимается в смысле вопроса о существовании алгоритма, дающего ответ при любых и . Черчем эта проблема была решена отрицательно. Теорема Черча. Проблема распознавания выводимости алгоритмически неразрешима. Проблема распознавания самоприменимости. Это вторая проблема, положительное решение которой не найдено до сих пор. Ее суть заключается в следующем. Программу машины Тьюринга можно закодировать каким-либо определенным шифром. На ленте машины можно изобразить ее же собственный шифр, записанный в алфавите машины. Здесь как и в случае обычной программы возможны два случая: 1. машина применима к своему шифру, то есть она перерабатывает этот шифр и после конечного числа тактов останавливается; 2. машина неприменима к своему шифру, то есть машина никогда не переходит в стоп - состояние. Таким образом, сами машины (или их шифры) разбиваются на два класса: класс самоприменимых и класс несамоприменимых тьюринговых машин. Проблема заключается в следующем как по любому заданному шрифту установить к какому классу относится машина, зашифрованная им: к классу самоприменимых или несамоприменимых. Теорема 2. Проблема распознавания самоприменимости алгоритмически неразрешима. 3). Проблема эквивалентности слов для ассоциативных исчислений. Рассмотрим некоторый алфавит  и множество слов в этом алфавите. Будем рассматривать преобразования одних слов в другие с помощью некоторых допустимых подстановок  , где  и  два слова в том же алфавите Если слово  содержит как подслово, например  , то возможны следующие подстановк  ,  ,  . Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Для задания ассоциативного исчисления достаточно задать соответствующий алфавит и систему подстановок. Если слово  может быть преобразовано в слово  путем однократного применения определенной подстановки, то и называются смежными словами. Последовательность слов  таких, что каждая пара слов  являются смежными, называется дедуктивной цепочкой, ведущей от слова  к слову  . Если существует цепочка, ведущая от слова к слову , то и называются эквивалентными: ~ . Для каждого ассоциативного исчисления возникает своя специальная проблема эквивалентности слов: для любых двух слов в данном исчислении требуется узнать эквивалентны они или нет. Теорема 3. Проблема эквивалентности слов в любом ассоциативном исчислении алгоритмически неразрешима. Эта проблема решена лишь в некоторых ассоциативных исчислениях специального вида. Математические теории. Аксиоматические теории делятся на формальные и неформальные. Неформальные аксиоматические теории наполнены теоретико – множественным содержанием, понятие выводимости в них довольно расплывчато и в значительной степени опирается на здравый смысл. Формальная аксиоматическая теория считается определенной, если выполнены следующие условия: задан язык теории; определено понятие формулы в этой теории; выделено множество аксиом теории; определены правила вывода в этой теории. Среди математических теорий выделяются теории первого порядка. Эти теории не допускают в своем изложении предикаты, которые имеют в качестве аргументов другие предикаты и функции. Кроме того, не допускаются кванторные операции по предикатам и функциям. Теории первого порядка называются еще элементарными теориями. 1). Язык теории первого порядка. Рассмотрим некоторый алфавит  теории  Множество слов  этого алфавита называется множеством выражений теории Пару  , состоящую из алфавита и множества выражений,  называют языком теории. В алфавит всякой теории  первого порядка входят: символы логических операций  символы кванторных операций  вспомогательные символы – скобки и запятые; конечное или счетное множество  - местных предикатных букв; конечное или счетное множество функциональных букв; конечное или счетное множество предметных констант. В частности под функциональной буквой может пониматься цепочка логических операций. Множество предикатных букв вместе с множеством функциональных букв и констант называется сигнатурой языка данной теории. Различные теории первого порядка могут отличаться друг от друга по составу букв в алфавите. Термы и формулы. В любой теории важное значение имеет определение терма и формулы. Фактически это два класса слов множества. Термом называется: а). предметная переменная и переменная константа; Таким образом, кроме предметных переменных и констант термами являются цепочки, образованные из предметных переменных и констант посредством символов операций. Примеры теорий первого порядка. 1). Геометрия (теория равенства отрезков). Логические аксиомы этой теории те же пять, что упомянутые выше. Первичные термины - множество всех отрезков и = - отношение равенства. 2). Аксиоматическая теория натуральных чисел. Аксиоматическое построение арифметики натуральных чисел связано с именами Пеано и Дедекинда. Язык теории содержит константу 0, числовые переменные, символ равенства, функциональные символы +, . ,  (прибавление единицы) и логические связки, то есть. Термы строятся из константы 0 и переменных с помощью функциональных символов. В частности натуральные числа изображаются термами вида 0. Элементарные формулы в этой теории – это равенства термов, остальные формулы получаются из элементарных с помощью логических связок. Вводится одна предикатная буква и три функциональных буквы. - отношение равенства, - отношение следования (прибавление единицы), - операция суммы, - операция произведения. В качестве специальных аксиом теории натуральных чисел берутся следующие аксиомы: где - произвольная формула теории натуральных чисел. Девятая аксиома называется принципом математической индукции. Аксиомы 1-2 обеспечивают очевидные свойства равенства, аксиомы 5-8 уточняют свойства операций сложения и умножения. Для произвольных теорий первого порядка теорема дедукции, доказанная нами в исчислении высказываний, требует изменения. В первоначальном виде, причем никаких ограничений на предметные переменные, входящие в, не накладывалось. Для справедливости теоремы дедукции для произвольных теорий первого порядка необходимо ее изменить следующим образом. Теорема Геделя о неполноте. В любой непротиворечивой формальной системе, содержащей минимум арифметики, а, следовательно, и в теории натуральных чисел, найдется формально неразрешимое суждение, то есть такая замкнутая формула , что ни , ни  не являются выводимыми в системе. Пусть у нас есть некая формальная система T, т.е. некий набор аксиом, из которых мы, пользуясь фиксированных набором правил перехода и общелогич
|