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

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


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

Невычислимые функции

Все формализмы для представления алгоритмов позволяют представлять алгоритмы через конечные термы («программы»). Пусть PRG есть множество всех таких термов, которые представляют одноместные функции, например в нотации m-рекурсии. На самом деле PRG есть формальный язык. Для р Î

PRG обозначим через fp частичное отображение, вычисляемое программой р.

Все элементы р Î PRG есть слова над конечным множеством знаков и могут быть однозначно представлены («закодированы») с помощью натуральных чисел. Соответственно, существует инъективное отображение, гёделизация для PRG:

code: PRG -> N.

Существование такого кодирования получается тотчас из существования вычислимого, инъективного отображения, которое отображает конечные последовательности над “N в N. Например, мы можем

seqcode:N*àN

специфицировать через

seqcode(<n... nk>) = рn11 ,... ,рnkk

,

причем пусть рi является последовательностью простых чисел. Наряду с этим, конечно, мыслимы и многие другие способы кодирования для последовательностей натуральных чисел.



Теорема. Существует тотальная функция

g: -N->N,

которая не является вычислимой.

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

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


Разрешимые предикаты

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

Предикат р называется разрешимым,

если существует алгоритм, который для каждого предложения от аргументов х1, ..., xn вычисляет булевское

значение р (х1, ..., xn). Предикат р называется позитивно полуразрешимым, если имеется алгоритм, который для любого предложения от аргументов х1, ..., xn, при которых р (x1, ..., xn) справедлив, завершается и вычисляет значение true, а в противном случае (если р (x1, ..., xn) несправедлив) вычисляет значение false или же не завершается. Другими словами, положительный ответ выдается корректным образом и в конечное время, а отрицательный ответ следует либо корректно, либо не выдается. Предикат р называется отрицательно полуразрешимым, если -p является положительно полуразрешимым.

Примеры (разрешимость).

1.      Следующие проблемы разрешимы:

·         равенство двух натуральных чисел в их двоичном представлении;

·         определение простоты натурального числа;

·         принадлежность заданного слова языку, определяемому заданной грамматикой типа 3 по Хомскому;

·         существование нулевого места полинома над натуральными числами.

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

·         завершаемость работы машины Тьюринга для определенного входного слов;

·         принадлежность заданного слова языку, определяемому грамматикой типа 0 по Хомскому.



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

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

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

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

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

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

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

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

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

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

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

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

е: N à М

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Содержание раздела