Na teoria da complexidade computacional, R é a classe de problemas de decisão solúveis por uma máquina de Turing, que é o conjunto de todas as linguagens recursivas.
R é igual ao conjunto de todas as funções computáveis totais.
Já que podemos decidir qualquer problema para o qual existe um reconhecedor e também um co-reconhecedor por simplesmente intercalá-los até que um obtenha resultado, a classe é igual a RE ∩ coRE.
A Complexidade Do Zoo: Classe R