25
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Не существует алгоритма, определяющего по произвольной грамматике, является ли она [[wikipedia:ru:Неоднозначная грамматика Существенно неоднозначные языки | неоднозначной]].
|proof=
Будем доказывать от противного. Для этого произведем [[M-сводимость|m-сведение]] множества решений [[Примеры неразрешимых задач: проблема соответствий Поста|проблемы соответствий Поста]] к множеству решений нашей задачи. А так как множество решений ПСП неразрешимо, то из m-сведения будет следовать неразрешимость нашей задачи.
