Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Разрешимость - часть 4


Следует обратить внимание на различие между перечислимым и рекурсивно-перечислимым.

Пример (рекурсивная перечислимость).

1.      Множество примитивно-рекурсивных функций является рекурсивно-   перечислимым, но не рекурсивным.

2.      Множество аргументов, для которых m-рекурсивная функция завершается, рекурсивно-перечислимо, но не обязательно рекурсивно.  

Если множество рекурсивно-перечислимо, то его характеристический предикат положительно полуразрешим.

Теорема. Любой язык Хомского рекурсивно-перечислим.

Доказательство. Грамматика языка тотчас индуцирует над деревом вывода способ перечисления.

Теорема. Множество аргументов, для которых частично рекурсивная функция не завершается, в общем случае не является рекурсивно-перечислимым.

Доказательство. Если бы множество было перечислимым, то была бы разрешима проблема завершаемости для частично рекурсивных функций.

Теорема. Язык S над множеством знаков Т точно тогда является рекурсивным, когда и множество S, и множество T*\S являются рекурсивно-перечислимыми.

Доказательство.

1.      Если S и T*\S перечислимы, то тотчас получается способ разрешения для характеристического предиката для S:  параллельно перечисляются множества S и T*\S. Как только при этом встречается заданное слово, вопрос решен.

2.      Если S рекурсивно, то можно (очевидным образом существующий) способ перечисления для Т* уточнить к способу перечисления для множества S и соответственно для T*\S.

Рассмотрим теорему, которая устанавливает связь между разрешимостью и рекурсивной перечислимостью.

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

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




Содержание  Назад  Вперед