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



         

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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




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