In complexity, Is the relationship between P and R known? The relationship between P and NP is unknown; However, we can ask an "easier" question, what is the relationship between P and R (=decidable languages)? In other words, is there a (decidable) problem shown to be not solvable in polynomial time? This wikipedia diagram states that EXPSPACE is strictly contained in R, meaning that P is strictly contained in R, however, I couldn't find any further details on this. Thanks! 
 A: Given any total recursive function $\rho:\mathbb N\to \mathbb N$, you can define a decidable subset of $\mathbb N$ which is not decidable by any Turing machine in less than $\rho$ time.
Essentially, this is done by a diagonal argument, by finding a recursive language $L:\mathbb N\to\{0,1\}$ which does not agree with any function that takes $\rho(n)$ time for all $n$.
If $\phi_e$ is an effective enumeration of computable Turing functions, we say $\phi_{e,s}(n)\downarrow$ if the Turing machine finished computation in time $s$ given input $n$.  For any $N$, we enumerate $1\leq e \leq N$ such that for all $1\leq n \leq N$, $\phi_{e,\rho(n)}(n)\downarrow$ and all resulting values are in $\{0,1\}$, and we pick the smallest such $e$ which we have not previously excluded.  Then we define $L(N)=1-\phi_e(N)$.  (If there is no such $e$, then we defint $L(N)=0$.) Now we added this $e$, if it existed, to the "previously excluded" set for later steps.  Note that this all takes a finite amount of time for each $N$.
This induction has the effect that if $\phi_e(n)$ runs in time $\rho(n)$ for all $n$ and always returns $0,1$,  then it gets excluded at some step. (This requires proof, but basically you can show that $\phi_e$ will get excluded by step $N=2e$.)
The resulting $L$ will be a total function which takes only the values $0,1$ and which is not equal to any computable function which takes $\rho(n)$ time to compute for all $n$.
Now, if $\rho(n)=2^n$, then this means that the resulting $L$ cannot, in particular, be computed in polynomial time.
A: By the Time Hierarchy Theorem, we know that class P is strictly contained in class EXPTIME. A natural example of problems that lie in EXPTIME but not P (aka the EXPTIME-complete problems) is the decision problem of whether a deterministic Turing machine would halt on a certain input within $k$ steps.
Now EXPTIME, by definition, is a class of decision problems and is therefore contained in R (and, by Time Hierarchy Theorem, is strictly contained in R). So it follows that $P \subsetneq R$.
