Перейти к навигации Перейти к поиску
В теории сложности вычислений , R является классом задач принятия решений разрешимых с помощью машины Тьюринга , которая является множеством всех рекурсивных языков (также называемыми разрешимыми языков).
Эквивалентные формулировки [ править ]
R равно множеству всех полных вычислимых функций .
Отношения с другими классами [ править ]
Поскольку мы можем решить любую проблему, для которой существует распознаватель, а также со-распознаватель, просто перемежая их, пока не будет получен результат, класс равен RE ∩ co-RE .
Ссылки [ править ]
- Блюм, Ленор, Майк Шуб и Стив Смейл, (1989), «О теории вычислений и сложности над действительными числами: NP-полнота, рекурсивные функции и универсальные машины», Бюллетень Американского математического общества , Новая серия, 21 (1): 1-46.
Внешние ссылки [ править ]