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