Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Для каждого шага интерпретирующего алгоритма надо построить МТ с алфавитом {0,1}, после чего объединить их должным образом, с помощью операций o, ||, if-then-else, while-do.

Обоснование закончено.

Разрешимость алгоритмических проблем.

В этом разделе мы дадим примеры доказательства неразрешимости конкретной алгоритмической проблемы - проблемы самоприменимости.

Определение 4.1: Алгоритмической проблемой называется проблема построения алгоритма для решения класса задач.

Естественно возникает вопрос: Всякая ли алгоритмическая проблема разрешима? Вплоть до начала ХХ века среди математиков существовала уверенность в разрешимости любой математической проблемы. Как уже отмечалось во введении, Лейбниц был один из первых, кто пришёл к идее исчисления. Он считал, что решение математической проблемы сводится к манипуляции с символами с помощью специальным образом подобранными правилами вывода (замены одних комбинаций символов на другие). Проблема, по мнению Лейбница, состояла лишь в том, чтобы построить надлежащим образом систему этих правил. Более того - он считал, что можно построить универсальный набор правил для решения любой математической проблемы. Джонатан Свифт в своей книге “Приключения Гулливера” подшутил над этой идеей Лейбница в образе мудреца, вращающего колёса с табличками в поисках нужного решения.

Английский математик Чёрч первым дал пример неразрешимой поблемы, известной как проблема выводимости.

Проблема выводимости:

Дана система правил подстановки R и два слова W и S. Можно ли определить выводимо W из S с помощью R?

Чёрч доказал, что не существует алгоритма, который бы для любой системы правил подстановки и любых двух слов давал ответ на этот вопрос.

Другой известный нам пример неразрешимой алгоритмической проблемы - 10-я проблема Гильберта.

Определение 4.2. Алгоритм А называется самоприменимым, если он применим к слову, которое является его описанием.

Проблема самоприменимости:

Дано описание алгоритма А. Требуется построить такой алгоритм, который бы для описания любого алгоритма А определял , является ли алгоритм А самоприменимым или нет.

Теорема 4.1. Распознавание самоприменимости алгоритмически неразрешимо.

Доказательство: Доказывать эту теорему будем методом от противного. Пусть алгоритм А, распознающий самоприменимость, существует. Тогда откорректируем его так, чтобы

А(А)=		s - если А - самоприменим t - если А - не самоприменим, где А - некоторый алгоритм

Построим, имея А, алгоритм В, который

В(А)=

не останавливается, если А самоприменим t - если А - не самоприменим

Таким образом, В применим к самонеприменимым алгоритмам и не применим к самоприменимым.

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





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата