Класс R

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории сложности вычислений классом R (от англ. the recursive languages) называют множество всех рекурсивных языков. Эквивалентно класс R можно определить как множество задач распознавания (англ.) разрешимых на машине Тьюринга. Класс R равен пересечению классов RE и co-RE.