Приватний вищий навчальний заклад
ЄвропейськийУніверситет
Уманськафілія
Кафедраматематики та інформатики
Реферат
з дисципліни «Теория алгоритмів тапредставлення знань»
на тему: «ТезисГьоделя. Теорема Черча»
Перевірив: Виконав:
викладач студент3-го курсу
Бєсєдіна С.В. 36групи
Оцінка ______ ЛевицькийЕ.Г.
Умань –2005
Зміст
1.TOC o «1-3» h z u Вступ. PAGEREF _Toc119118926 h 3
2.Теорема Черча. Проблема распознаваниявыводимости алгоритмически неразрешима.PAGEREF _Toc119118927 h 4
3.Проблемараспознавания самоприменимости алгоритмически неразрешима.PAGEREF _Toc119118928 h 5
4.Проблема эквивалентности слов в любомассоциативном исчислении алгоритмически неразрешима.PAGEREF _Toc119118929 h 6
5.Примеры теорий первого порядка.PAGEREF _Toc119118930 h 8
6.Теорема Геделя о неполноте.PAGEREF _Toc119118931 h 9
7.Списоквикористаних джерел. 15
Вступ
Введение понятия машины Тьюринга уточняет понятиеалгоритма и указывает путь решения какой-то массовой проблемы. Однако машина Тьюринга бывает неприменима к начальнойинформации (исходному слову алфавита). Та же ситуация повторяется относительнонекоторых задач, для решения которых не удается создать машины Тьюринга. Одиниз первых результатов такого типа получен Черчем в 1936 году. Он касаетсяпроблемы распознавания выводимости в математической логике.
1).Аксиоматический метод в математике заключается в том, что все теоремы данной теории получаются посредствомформально-логического вывода из нескольких аксиом, принимаемых в данной теориибез доказательств. Например, в математической логике описывается специальныйязык формул, позволяющий любое предложение математической теории записать ввиде вполне определенной формулы, а процесс логического вывода из посылки следствия может быть описан ввиде процесса формальных преобразований исходной формулы. Это достигается путемиспользования логического исчисления, в котором указана система допустимых преобразований,изображающих элементарные акты логического умозаключения, из которыхскладывается любой, сколь угодно сложный формально-логический вывод.
Вопрос ологической выводимости следствия из посылки является вопросом о существованиидедуктивной цепочки, ведущей от формулы к формуле возникает проблема распознавания выводимости: существует ли для двухформул и дедуктивная цепочка,ведущая от к или нет. Решение этойпроблемы понимается в смысле вопроса о существовании алгоритма, дающего ответпри любых и Теорема Черча. Проблема распознаваниявыводимости алгоритмически неразрешима.
Проблемараспознавания самоприменимости. Это вторая проблема, положительное решениекоторой не найдено до сих пор. Ее суть заключается в следующем. Программумашины Тьюринга можно закодировать каким-либо определенным шифром. На лентемашины можно изобразить ее же собственный шифр, записанный в алфавите машины.Здесь как и в случае обычной программы возможны два случая:
1.машина применима к своему шифру, то есть она перерабатывает этот шифр и послеконечного числа тактов останавливается;
2. машинанеприменима к своему шифру, то есть машина никогда не переходит в стоп — состояние.
Таким образом,сами машины (или их шифры) разбиваются на два класса: класс самоприменимых икласс несамоприменимых тьюринговых машин. Проблема заключается в следующем какпо любому заданному шрифту установить к какому классу относится машина,зашифрованная им: к классу самоприменимых или несамоприменимых.
Теорема 2. Проблемараспознавания самоприменимости алгоритмически неразрешима.
3). Проблемаэквивалентности слов для ассоциативных исчислений.
Рассмотримнекоторый алфавит и множество слов вэтом алфавите. Будем рассматривать преобразования одних слов в другие с помощьюнекоторых допустимых подстановок , где и два слова в том жеалфавите Если слово содержит как подслово, например
Ассоциативнымисчислением называется совокупность всех слов в некотором алфавите вместе скакой-нибудь конечной системой допустимых подстановок. Для заданияассоциативного исчисления достаточно задать соответствующий алфавит и системуподстановок.
Если слово может бытьпреобразовано в слово путем однократного примененияопределенной подстановки, то и называются смежнымисловами. Последовательность слов таких, что каждая параслов являются смежными,называется дедуктивной цепочкой, ведущей от слова к слову к слову и называются эквивалентными:
Для каждогоассоциативного исчисления возникает своя специальная проблема эквивалентностислов: для любых двух слов в данном исчислении требуется узнать эквивалентны ониили нет.
Теорема 3. Проблема эквивалентности слов влюбом ассоциативном исчислении алгоритмически неразрешима.
Эта проблемарешена лишь в некоторых ассоциативных исчислениях специального вида.
Математическиетеории.
Аксиоматическиетеории делятся на формальные и неформальные. Неформальные аксиоматическиетеории наполнены теоретико – множественным содержанием, понятие выводимости вних довольно расплывчато и в значительной степени опирается на здравый смысл.
Формальнаяаксиоматическая теория считается определенной, если выполнены следующиеусловия:
1. заданязык теории;
2. определено понятие формулы в этойтеории;
3. выделеномножество аксиом теории;
4. определены правила вывода в этойтеории.
Средиматематических теорий выделяются теории первого порядка. Эти теории не допускаютв своем изложении предикаты, которые имеют в качестве аргументов другиепредикаты и функции. Кроме того, не допускаются кванторные операции попредикатам и функциям. Теории первого порядка называются еще элементарными теориями.
1). Языктеории первого порядка. Рассмотрим некоторый алфавит теории Множество слов этого алфавитаназывается множеством выражений теории Пару и множества выражений, называют языкомтеории.
В алфавит всякой теории первого порядкавходят:
1) символы логических операций
2) символы кванторных операций
3) вспомогательные символы – скобки изапятые;
4) конечное или счетное множество
5) конечное или счетное множествофункциональных букв;
6) конечное или счетное множество предметныхконстант.
В частностипод функциональной буквой может пониматься цепочка логических операций.
Множествопредикатных букв вместе с множеством функциональных букв и констант называетсясигнатурой языка данной теории.
Различныетеории первого порядка могут отличаться друг от друга по составу букв валфавите.
Термы иформулы.
В любойтеории важное значение имеет определение терма и формулы. Фактически это двакласса слов множества.
Термомназывается: а). предметнаяпеременная и переменная константа;
Такимобразом, кроме предметных переменных и констант термами являются цепочки,образованные из предметных переменных и констант посредством символов операций.
Примеры теорий первого порядка.
1). Геометрия (теория равенстваотрезков).
Логическиеаксиомы этой теории те же пять, что упомянутые выше. Первичные термины — множество всехотрезков и = — отношение равенства.
2). Аксиоматическая теориянатуральных чисел.
Аксиоматическоепостроение арифметики натуральных чисел связано с именами Пеано и Дедекинда.Язык теории содержит константу 0, числовые переменные, символ равенства,функциональные символы +,., спомощью функциональных символов. В частности натуральные числа изображаютсятермами вида 0.
Элементарныеформулы в этой теории – это равенства термов, остальные формулы получаются изэлементарных с помощью логических связок. Вводится одна предикатная буква и три функциональных буквы.
— отношениеравенства, — отношение следования (прибавление единицы), — операция суммы, — операция произведения. В качестве специальных аксиом теории натуральных чиселберутся следующие аксиомы:
где — произвольная формула теории натуральныхчисел. Девятая аксиома называется принципом математической индукции. Аксиомы1-2 обеспечивают очевидные свойства равенства, аксиомы 5-8 уточняют свойстваопераций сложения и умножения.
Для произвольных теорий первогопорядка теорема дедукции, доказанная нами в исчислении высказываний, требуетизменения. В первоначальном виде, причем никаких ограничений на предметныепеременные, входящие в, не накладывалось. Для справедливости теоремы дедукциидля произвольных теорий первого порядка необходимо ее изменить следующимобразом.
ТеоремаГеделя о неполноте.В любой непротиворечивой формальной системе, содержащей минимумарифметики, а, следовательно, и в теории натуральных чисел, найдется формальнонеразрешимое суждение, то есть такая замкнутая формула не являются выводимымив системе.
Пусть у насесть некая формальная система T,т.е. некий набор аксиом, из которых мы, пользуясь фиксированных наборомправил перехода и общелогических аксиом, можем доказывать какие-нибудь теоремы.Поставим несколько условий: пусть, во-первых, наша система Tбудет сформулирована на языкеарифметики. Это значит, что формулы аксиом и теорем в T,кроме общелогических символов (таких, как переменные, скобки, ∧«и», ¬ «не-» и прочие логические операции, знак равенства=, а также кванторы существования ∃ и всеобщности ∀) могутсодержать такие символы, как 0 (константа), + (бинарнаяоперация), * (ещё одна операция),
С точки зрения формальных доказательствсистема Tне имеет «семантики», иными словами, смысл используемых в ней символов намбезразличен. Формальное доказательство есть всего лишь некоторая длиннаяцепочка строк, в которой каждая строка есть аксиома T, общелогическая аксиома,или получена из предыдущих строк применением одного из разрешённых правилперехода. Мы обозначили, скажем, одну из операций языка арифметики символом *,потому что она соответствует нашему пониманию умножения; но с точки зрения формальнойсистемы T* — всего лишь символ, который ничего неозначает. Вместо него мог быть любой другой символ, скажем, %, и вседоказательства оставались бы в силе; просто если бы мы захотели определить смыслаксиом или доказываемых нами теорем, нам пришлось бы понимать % как«умножение».
Сказать, чтокакое-то утверждение доказуемо в T— значит сказать, чтоесть некоторое формальное доказательство, которое к нему приводит. Доказуемость— синтаксическое свойство, а не семантическое. С другой стороны, сказать, чтокакое-то утверждение истинно — значит, сказать, что если мы интерпретируемего согласно обычной интерпретации символов T(т.е. * будем пониматькак «умножение», символ 0 — как число 0, итп.), то получаемистинное утверждение о натуральных числах.
Доказуемостьнеобязательно влечёт истинность. Предположим для простоты, что для каждогонатурального числа nв нашем языке есть константа n,позволяющая «говорить» о числе nв формулах нашего языка(на практике мы можем «симулировать» такие константы, не объявляя их,с помощью цепочки терминов: 0, S(0), S(S(0)), S(S(S(0)))итп.). Теперь возьмёмформальную систему T, в которой есть следующая аксиома: 2+2=5.Тогда утверждение
«2+2=5» доказуемо в системе T(т.к. оно даже являетсяаксиомой), но, естественно, ложно (является ложным утверждением онатуральных числах).
Есть формальные системы, которые доказывают только истинные утверждения.Таковы системы, в которых все аксиомы — истинные утверждения (можно доказать,что тогда все правила перехода между аксиомами сохраняют истинность). Такиеформальные системы называются корректными.
Формальная система называется консистентной,если она не может доказать одновременно какое-то утверждение и его отрицание,т.е. доказать противоречие.Неконсистентная формальная система — это плохо и практически бесполезно, т.к.можно легко показать, что из доказательства противоречия можно получитьдоказательство чего угодно. Неконсистентная формальная системадоказывает вообще любое утверждение, так что ничего интересного в ней нет.
Если система корректна, то онаавтоматически консистентна: ведьона доказывает только истинныеутверждения, а какое-то утверждение и его отрицание не могут одновременно бытьистинными: одно из них будет истинным, а другое ложным. Заметим, однако — этоважно! — что «консистентность», как и «доказуемость» естьсвойство синтаксическое, не зависящее от смысла формул и ихинтерпретации; а вот корректность системы есть свойство семантическое, требующеепонятия «истинности».
Наконец, формальная система называется полной, если для любогоутверждения φона может доказать либо φ, либо ¬φ(«не-φ»). Доказательство ¬φназывается такжеопровержением φ; таким образом, полная система может либодоказать, либо опровергнуть любою утверждение. В некотором смысле она «навсе вопросы даёт ответ». Что ни скажешь про натуральные числа — она сможетлибо доказать это, либо опровергнуть. Это свойство полноты –тоже синтаксическое, не пользующееся понятием«истинности».
Теперь мы можем определить три формулировки теоремы Гёделя онеполноте следующим образом:
1. Пусть T— «подходящая» (см. выше) формальнаясистема, и предположим также, что T— корректнаясистема. Тогда множество утверждений, которые Tможет доказать, имножество истинных утверждений не совпадают (а так как все доказуемые спомощью Tутверждения истинны, отсюда сразу следует, что естьистинные утверждения, недоказуемыев T).
2. Пусть T— «подходящая»формальная система, и предположим опять, что Tкорректна. Тогда мы можем построить конкретное утверждение G(называемое«гёделевым утверждением»), обладающее следующим свойством: Gистинно, но недоказуемо в T.
3. Пусть T— «подходящая»формальная система, и предположим, что Tконсистентна. Тогда Tнеявляется полной системой, т.е.существует утверждение Gтакое, что Tнеможет его ни доказать, ни опровергнуть; более того, мы можем построить такоеконкретное G(называемое «гёделевым утверждением»).
Неполнота системы Tутверждается в качестверезультата только в третьей версии, но легко видеть, что она сразу следует иззаключения и в первых двух версиях. В них мы заключаем, что существует какое-тоистинное, но недоказуемое утверждение. Такое утверждение Tнедоказывает, но и опровергнуть его — доказать его отрицание — она не может, т.к.его отрицание ложно, а T(в первых двух вариантахтеоремы) корректна и доказывает только истинные утверждения. Поэтому Tнеможет ни доказать, ни опровергнуть такое утверждение Gи, следовательно, Tнеполна.
Но вот что действительно отличает первые две версии от третьей:условие теоремы. В первых двух версиях от системы Tтребуется бытькорректной; в третьей версии она должна быть всего лишь консистентной — намного более слабое требование. Естьбесчисленное количество консистентных, но некорректных систем. Ещё более важентот факт, что и в условии, и в заключениитретьей версии теоремы используются только синтаксические понятия, нетребующие понятия «истинности», не требующие семантики. Третья версиятеоремы и есть та, которую первоначально доказал Гёдель в начале 30-х годовпрошлого века.
если быть совсем точным, формулировка Гёделя включала дополнительноесинтаксическое условие для теории T, называющееся w-консистентностью(произносится «омега-консистентность»). Однако через пять лет послепубликации статьи Гёделя Россер доказал, что от этого условия можно избавитьсяи достаточно одной консистентности)
То, что в самой сильной и общей своей формулировке теорема Гёделя ненакладывает на Tникаких существенных семантическихусловий, и заключение её тоже вполне синтаксично — это очень важно понять.Важно не только и не столько потому, что иногда мы хотим применить теоремуГёделя к некорректным системам, хоть и это тоже верно. Важно в основном последующим двум причинам.
Во-первых, первая теорема о неполноте Гёделя используется в доказательстве второйтеоремы о неполноте Гёделя, которая доказывает, что «подходящая» (внесколько другом, но схожем с описанным выше, смысле) формальная система Tнеможет доказать собственную консистентность, если она консистентна (если онанеконсистентна, то она может доказать всё что угодно, включая собственнуюконсистентность, как ни парадоксально это звучит). Я не буду вдаваться вподробности, но замечу лишь, что в процессе доказательства второй теоремы онеполноте необходимо показать, что доказательство первой теоремы онеполноте можно формализовать внутри системы T. Иными словами, непросто «если Tконсистента, то она неполна» (третья версияпервой теоремы о неполноте, см. выше), но также это утверждение (точнее, егоарифметический аналог) можно доказать в самой системе T.Но в то время, как можно формализовать «внутри» системы Tтакие понятия, как «формальная система», «консистентность»и «полнота», оказывается, что понятие «истинности»формализовать внутри Tневозможно в принципе. Поэтому первый и второйварианты теоремы Гёделя, хоть они и более просты для доказательства, не могутбыть использованы для доказательства второй теоремы Гёделя.
Во-вторых, теорема Гёделя о неполноте применима не только кформальным системам, сформулированным в языке арифметики (т.е. говорящим онатуральных числах), но также к бесчисленному множеству других формальныхсистем, от которых требуется только, чтобы они были «подходящими» внужном техническом смысле; главное требование здесь — чтобы они были не менеемощными, чем теория Tв языке арифметики, для которой мы собственнодоказываем теорему Гёделя, а это требование обеспечивается возможностью интерпретироватьTв такой новой теории. Например, формальная система ZFC,используемая для формализации теории множеств, а вместе с ней и практическивсей современной математики, намного более мощна, чем какая-нибудь простенькаяарифметическая T, для которой мы доказали теорему Гёделя этотфакт можно строго описать (предъявив интерпретацию, т.е. способперевести утверждения из языка Tв утверждения языка ZFC,и показав, что ZFCтогда доказывает «перевод» всехаксиом T) и из него тогда будет следовать, что и ZFCтоже неполна, т.е. в ней тоже есть какое-то гёделево утверждение G,которое нельзя ни доказать, ни опровергнуть.
Проблема, однако, в том, что в отличие от арифметическихформальных систем, для утверждений которых у нас всегда есть удобный и обычныйспособ определить их истинность(посмотреть на то, верны ли они как утверждения о натуральных числах), длядругих формальных систем, таких, скажем, как ZFC, понятие истинностивообще не определено или определено очень плохо. Для них первая и вторая версиитеоремы Гёделя оказываются неподходящими именно потому, что эти версииопираются на корректность даннойсистемы и на существование определённого понятия истинности утверждений. Подходит толькотретья, чисто синтаксическая версия.
Список використанихджерел
1.www.intuit.ru
2. www.proza.ru
3. www.referat.ru