Xreferat.com » Рефераты по математике » Тезис Гьоделя. Теорема Черча

Тезис Гьоделя. Теорема Черча

Реферат з дисципліни «Теория алгоритмів та представлення знань»

Виконав студент 3-го курсу 36 групи Левицький Е.Г.

Європейський Університет

Уманська філія

Кафедра математики та інформатики

Умань – 2005

Вступ

Введение понятия машины Тьюринга уточняет понятие алгоритма и указывает путь решения какой-то массовой проблемы. Однако машина Тьюринга бывает неприменима к начальной информации (исходному слову алфавита). Та же ситуация повторяется относительно некоторых задач, для решения которых не удается создать машины Тьюринга. Один из первых результатов такого типа получен Черчем в 1936 году. Он касается проблемы распознавания выводимости в математической логике.

1). Аксиоматический метод в математике заключается в том, что все теоремы данной теории получаются посредством формально-логического вывода из нескольких аксиом, принимаемых в данной теории без доказательств. Например, в математической логике описывается специальный язык формул, позволяющий любое предложение математической теории записать в виде вполне определенной формулы, а процесс логического вывода из посылки Тезис Гьоделя. Теорема Черча следствия Тезис Гьоделя. Теорема Черча может быть описан в виде процесса формальных преобразований исходной формулы. Это достигается путем использования логического исчисления, в котором указана система допустимых преобразований, изображающих элементарные акты логического умозаключения, из которых складывается любой , сколь угодно сложный формально-логический вывод.

Вопрос о логической выводимости следствия Тезис Гьоделя. Теорема Черча из посылки Тезис Гьоделя. Теорема Черча является вопросом о существовании дедуктивной цепочки, ведущей от формулы Тезис Гьоделя. Теорема Черча к формуле Тезис Гьоделя. Теорема Черча. В связи с этим возникает проблема распознавания выводимости: существует ли для двух формул Тезис Гьоделя. Теорема Черча и Тезис Гьоделя. Теорема Черча дедуктивная цепочка, ведущая от Тезис Гьоделя. Теорема Черча к Тезис Гьоделя. Теорема Черча или нет. Решение этой проблемы понимается в смысле вопроса о существовании алгоритма, дающего ответ при любых Тезис Гьоделя. Теорема Черча и Тезис Гьоделя. Теорема Черча. Черчем эта проблема была решена отрицательно.

Теорема Черча. Проблема распознавания выводимости алгоритмически неразрешима.

Проблема распознавания самоприменимости. Это вторая проблема, положительное решение которой не найдено до сих пор. Ее суть заключается в следующем. Программу машины Тьюринга можно закодировать каким-либо определенным шифром. На ленте машины можно изобразить ее же собственный шифр, записанный в алфавите машины. Здесь как и в случае обычной программы возможны два случая:

1. машина применима к своему шифру, то есть она перерабатывает этот шифр и после конечного числа тактов останавливается;

2. машина неприменима к своему шифру, то есть машина никогда не переходит в стоп - состояние.

Таким образом, сами машины (или их шифры) разбиваются на два класса: класс самоприменимых и класс несамоприменимых тьюринговых машин. Проблема заключается в следующем как по любому заданному шрифту установить к какому классу относится машина, зашифрованная им: к классу самоприменимых или несамоприменимых.

Теорема 2. Проблема распознавания самоприменимости алгоритмически неразрешима.

3). Проблема эквивалентности слов для ассоциативных исчислений.

Рассмотрим некоторый алфавит Тезис Гьоделя. Теорема Черча и множество слов в этом алфавите. Будем рассматривать преобразования одних слов в другие с помощью некоторых допустимых подстановок Тезис Гьоделя. Теорема Черча , где Тезис Гьоделя. Теорема Черча и Тезис Гьоделя. Теорема Черча два слова в том же алфавите Тезис Гьоделя. Теорема Черча Если слово Тезис Гьоделя. Теорема Черча содержит Тезис Гьоделя. Теорема Черча как подслово, например Тезис Гьоделя. Теорема Черча, то возможны следующие подстановк Тезис Гьоделя. Теорема Черча, Тезис Гьоделя. Теорема Черча, Тезис Гьоделя. Теорема Черча.

Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Для задания ассоциативного исчисления достаточно задать соответствующий алфавит и систему подстановок.

Если слово Тезис Гьоделя. Теорема Черча может быть преобразовано в слово Тезис Гьоделя. Теорема Черча путем однократного применения определенной подстановки, то Тезис Гьоделя. Теорема Черча и Тезис Гьоделя. Теорема Черча называются смежными словами. Последовательность слов Тезис Гьоделя. Теорема Черча таких, что каждая пара слов Тезис Гьоделя. Теорема Черча являются смежными, называется дедуктивной цепочкой, ведущей от слова Тезис Гьоделя. Теорема Черча к слову Тезис Гьоделя. Теорема Черча. Если существует цепочка, ведущая от слова Тезис Гьоделя. Теорема Черча к слову Тезис Гьоделя. Теорема Черча, то Тезис Гьоделя. Теорема Черча и Тезис Гьоделя. Теорема Черча называются эквивалентными: Тезис Гьоделя. Теорема Черча~Тезис Гьоделя. Теорема Черча.

Для каждого ассоциативного исчисления возникает своя специальная проблема эквивалентности слов: для любых двух слов в данном исчислении требуется узнать эквивалентны они или нет.

Теорема 3. Проблема эквивалентности слов в любом ассоциативном исчислении алгоритмически неразрешима.

Эта проблема решена лишь в некоторых ассоциативных исчислениях специального вида.

Математические теории.

Аксиоматические теории делятся на формальные и неформальные. Неформальные аксиоматические теории наполнены теоретико – множественным содержанием, понятие выводимости в них довольно расплывчато и в значительной степени опирается на здравый смысл.

Формальная аксиоматическая теория считается определенной, если выполнены следующие условия:

задан язык теории;

определено понятие формулы в этой теории;

выделено множество аксиом теории;

определены правила вывода в этой теории.

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

1). Язык теории первого порядка. Рассмотрим некоторый алфавит Тезис Гьоделя. Теорема Черча теории Тезис Гьоделя. Теорема Черча Множество слов Тезис Гьоделя. Теорема Черча этого алфавита называется множеством выражений теории Тезис Гьоделя. Теорема Черча Пару Тезис Гьоделя. Теорема Черча, состоящую из алфавита Тезис Гьоделя. Теорема Черча и множества выражений, Тезис Гьоделя. Теорема Черча называют языком теории.

В алфавит Тезис Гьоделя. Теорема Черча всякой теории Тезис Гьоделя. Теорема Черча первого порядка входят:

символы логических операций Тезис Гьоделя. Теорема Черча

символы кванторных операций Тезис Гьоделя. Теорема Черча

вспомогательные символы – скобки и запятые;

конечное или счетное множество Тезис Гьоделя. Теорема Черча- местных предикатных букв;

конечное или счетное множество функциональных букв;

конечное или счетное множество предметных констант.

В частности под функциональной буквой может пониматься цепочка логических операций.

Множество предикатных букв вместе с множеством функциональных букв и констант называется сигнатурой языка данной теории.

Различные теории первого порядка могут отличаться друг от друга по составу букв в алфавите.

Термы и формулы.

В любой теории важное значение имеет определение терма и формулы. Фактически это два класса слов множества.

Термом называется: а). предметная переменная и переменная константа;

Таким образом, кроме предметных переменных и констант термами являются цепочки, образованные из предметных переменных и констант посредством символов операций.

Примеры теорий первого порядка.

1). Геометрия (теория равенства отрезков).

Логические аксиомы этой теории те же пять, что упомянутые выше. Первичные термины Тезис Гьоделя. Теорема Черча - множество всех отрезков и = - отношение равенства.

2). Аксиоматическая теория натуральных чисел.

Аксиоматическое построение арифметики натуральных чисел связано с именами Пеано и Дедекинда. Язык теории содержит константу 0, числовые переменные, символ равенства, функциональные символы +, . , Тезис Гьоделя. Теорема Черча(прибавление единицы) и логические связки, то есть. Термы строятся из константы 0 и переменных с помощью функциональных символов. В частности натуральные числа изображаются термами вида 0.

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

- отношение равенства, - отношение следования (прибавление единицы), - операция суммы, - операция произведения. В качестве специальных аксиом теории натуральных чисел берутся следующие аксиомы:

где - произвольная формула теории натуральных чисел. Девятая аксиома называется принципом математической индукции. Аксиомы 1-2 обеспечивают очевидные свойства равенства, аксиомы 5-8 уточняют свойства операций сложения и умножения.

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

Теорема Геделя о неполноте. В любой непротиворечивой формальной системе, содержащей минимум арифметики, а, следовательно, и в теории натуральных чисел, найдется формально неразрешимое суждение, то есть такая замкнутая формула Тезис Гьоделя. Теорема Черча, что ни Тезис Гьоделя. Теорема Черча, ни Тезис Гьоделя. Теорема Черча не являются выводимыми в системе.

Пусть у нас есть некая формальная система T, т.е. некий набор аксиом, из которых мы, пользуясь фиксированных набором правил перехода и общелогических аксиом, можем доказывать какие-нибудь теоремы. Поставим несколько условий: пусть, во-первых, наша система T будет сформулирована на языке арифметики. Это значит, что формулы аксиом и теорем в T, кроме общелогических символов (таких, как переменные, скобки, ∧ "и", ¬ "не-" и прочие логические операции, знак равенства =, а также кванторы существования ∃ и всеобщности ∀) могут содержать такие символы, как 0 (константа), + (бинарная операция), * (ещё одна операция), < (отношение "меньше, чем"), S(x) (функция, обозначающая "следующий за x элемент", т.е. x+1). Во-вторых, пусть система T будет достаточно мощной, что в нашем случае значит, что она умеет доказывать некоторые достаточно простые формулы отношений между натуральными числами (подробности я опускаю). Например, если мы не внесём вообще никаких аксиом в T, то она ничего нетривиального не сможет доказать, т.е. будет недостаточно мощной и теорема Гёделя к ней относиться не будет. Но любой достаточно полный список аксиом арифметики (например, перечисляющий обычные тривиальные свойства операций умножения и сложения, отношения < и функции S(x)) оказывается достаточно мощным для наших целей. В-третьих, система T должна быть в некотором техническом смысле "легко описываемой" — в ней должно быть либо конечное количество аксиом, либо бесконечное, но описываемое с помощью какого-то заранее известного алгоритма. Любую формальную систему, отвечающую этим трём условиям, назовём подходящей (это не стандартная терминология, просто для удобства только в этой записи).
С точки зрения формальных доказательств система 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 (т.к. оно даже является аксиомой), но, естественно, ложно (является ложным утверждением о натуральных числах).
Есть формальные системы, которые доказывают только истинные утверждения. Таковы системы, в которых все аксиомы — истинные утверждения (можно доказать, что тогда все правила перехода между аксиомами сохраняют истинность). Такие формальные системы называются корректными.
Формальная система называется консистентной, если она не может доказать одновременно какое-то утверждение и его отрицание, т.е. доказать противоречие. Неконсистентная формальная система — это плохо и практически бесполезно, т.к. можно легко показать, что из доказательства противоречия можно получить доказательство чего угодно. Неконсистентная формальная система доказывает вообще любое утверждение, так что ничего интересного в ней нет.
Если система корректна, то она автоматически консистентна: ведь она доказывает только истинные утверждения, а какое-то утверждение и его отрицание не могут одновременно быть истинными: одно из них будет истинным, а другое ложным. Заметим, однако — это важно! — что "консистентность", как и "доказуемость" есть свойство синтаксическое, не зависящее от смысла формул и их интерпретации; а вот корректность системы есть свойство семантическое, требующее понятия "истинности".
Наконец, формальная система называется полной, если для любого утверждения φ она может доказать либо φ, либо ¬φ ("не-φ"). Доказательство ¬φ называется также опровержением φ ; таким образом, полная система может либо доказать, либо опровергнуть любою утверждение. В некотором смысле она "на все вопросы даёт ответ". Что ни скажешь про натуральные числа — она сможет либо доказать это, либо опровергнуть. Это свойство полноты – тоже синтаксическое, не пользующееся понятием "истинности".

Теперь мы можем определить

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: