Существуют рекурсивно перечислимые, но не рекурсивные языки, один из таких языков Lu . Сведением Lu к проблеме P можно доказать, что P не имеет алгоритма.
Теорема.Язык Lu рекурсивно перечислим, но не рекурсивен.
Доказательство. Была доказана рекурсивная перечислимость языка Lu . Допустим, что Lu рекурсивен, тогда по теореме язык Lu рекурсивен и существует допускающая его машина M, т.е. Lu = L(M). Преобразуем M
в машину M ’, допускающую Lu : если вход w есть wi , т.е. код машины Mi , то M ’ определяет, допускает ли Mi вход wi . Поскольку M допускает
Lu, то M допускает wi , если Mi не допускает wi , т.е. когда wi Î Ld.
Таким образом, M ’ допускает w тогда и только тогда, когда wÎ Ld.
Поскольку по теореме машины M ’ не существует, получено противоречие, следовательно, язык Lu не является рекурсивным. “
