Тезис Гьоделя. Теорема Черча
    Реферат з дисципліни "Теория алгоритмів та представлення знань"
    Виконав студент 3-го курсу 36 групи Левицький Е.Г.
    Європейський Університет
    Уманська філія
    Кафедра математики та інформатики
    Умань - 2005 Вступ
    Введение понятия машины Тьюринга уточняет понятие алгоритма и указывает путь решения какой-то массовой проблемы. Однако машина Тьюринга бывает неприменима к начальной информации (исходному слову алфавита). Та же ситуация повторяется относительно некоторых задач, для решения которых не удается создать машины Тьюринга. Один из первых результатов такого типа получен Черчем в 1936 году. Он касается проблемы распознавания выводимости в математической логике.
    1). Аксиоматический метод в математике заключается в том, что все теоремы данной теории получаются посредством формально-логического вывода из нескольких аксиом, принимаемых в данной теории без доказательств. Например, в математической логике описывается специальный язык формул, позволяющий любое предложение математической теории записать в виде вполне определенной формулы, а процесс логического вывода из посылки следствия может быть описан в виде процесса формальных преобразований исходной формулы. Это достигается путем использования логического исчисления, в котором указана система допустимых преобразований, изображающих элементарные акты логического умозаключения, из которых складывается любой , сколь угодно сложный формально-логический вывод.
    Вопрос о логической выводимости следствия из посылки является вопросом о существовании дедуктивной цепочки, ведущей от формулы к формуле . В связи с этим возникает проблема распознавания выводимости: существует ли для двух формул и дедуктивная цепочка, ведущая от к или нет. Решение этой проблемы понимается в смысле вопроса о существовании алгоритма, дающего ответ при любых и . Черчем эта проблема была решена отрицательно. Теорема Черча. Проблема распознавания выводимости алгоритмически неразрешима.
    Проблема распознавания самоприменимости. Это вторая проблема, положительное решение которой не найдено до сих пор. Ее суть заключается в следующем. Программу машины Тьюринга можно закодировать каким-либо определенным шифром. На ленте машины можно изобразить ее же собственный шифр, записанный в алфавите машины. Здесь как и в случае обычной программы возможны два случая:
    1. машина применима к своему шифру, то есть она перерабатывает этот шифр и после конечного числа тактов останавливается;
    2. машина неприменима к своему шифру, то есть машина никогда не переходит в стоп - состояние.
    Таким образом, сами машины (или их шифры) разбиваются на два класса: класс самоприменимых и класс несамоприменимых тьюринговых машин. Проблема заключается в следующем как по любому заданному шрифту установить к какому классу относится машина, зашифрованная им: к классу самоприменимых или несамоприменимых.
    Теорема 2. Проблема распознавания самоприменимости алгоритмически неразрешима.
    3). Проблема эквивалентности слов для ассоциативных исчислений.
    Рассмотрим некоторый алфавит и множество слов в этом алфавите. ............