Изменения

Перейти к: навигация, поиск

M-сводимость

111 байт убрано, 09:00, 20 января 2012
Нет описания правки
== Применение ==
Этой леммой удобно пользоваться для доказательств неразрешимости различных задачПриведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи сводя к ней ''(а не наоборот!)'' другую, неразрешимость которой уже доказана.  Например, :* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]], [[Примеры неразрешимых задач: однозначность грамматики|задачи однозначности КС-грамматики]] или проверки, выводится ли в КС-грамматике хотя бы один палиндром.
== Литература ==

Навигация