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




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


3.      Следующая проблема отрицательно полуразрешима:

·         равенство двух функций, заданных с помощью примитивной рекурсии.

4.      Следующая проблема неразрешима и тем самым не является ни положительно полуразрешимой, ни отрицательно полуразрешимой:

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

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

Важно делать различие между «неразрешим» («невычислима») и «не доказано». Так, для вычислимой функции f вообще неразрешимо, всегда ли ее вычисление завершается.

Рекурсивные и рекурсивно-перечислимые множества

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

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

Теорема. Каждый контекстно-зависимый язык (язык типа 1 по Хомскому) является рекурсивным.

Доказательство. Для каждого слова (на основании монотонности длин слов) множество слов, к которым оно сводимо, конечно; это множество может быть вычислено с помощью алгоритма. Отсюда получается существование способа разрешения.

Для подмножества S Í М тотальное отображение

е: N à М

называется перечислением (перенумерацией), если

S = {е(n): n Î N}.

Множество S называется рекурсивно-перечислимым,

если существует вычислимое («рекурсивное») перечисление для множества S.


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