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