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

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

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

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

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

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

Умань – 2005

Вступ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





1  2  3 | Следующая страница реферата