Тезис Гьоделя. Теорема Черча (стр. 1 из 3)

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

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

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

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

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

Умань – 2005

Вступ

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

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

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

Вопрос о логической выводимости следствия

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

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

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

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

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

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

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

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

Рассмотрим некоторый алфавит

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

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

Если слово

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

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

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

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

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

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

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

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

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

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

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

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

1). Язык теории первого порядка. Рассмотрим некоторый алфавит

теории Множество слов этого алфавита называется множеством выражений теории Пару , состоящую из алфавита и множества выражений, называют языком теории.

В алфавит

всякой теории первого порядка входят:

символы логических операций

символы кванторных операций

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

конечное или счетное множество

- местных предикатных букв;

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

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