Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?
I don't know the best way to express RH inside PA, but the following inequality $$\sum_{d \mid n} d \leq H_n + \exp(H_n)\log(H_n),$$ where $H_n = 1+1/2+\cdots+1/n$ is the $n$-th harmonic number, is known to be equivalent to RH. [J. Lagarias, An elementary problem equivalent to the Riemann hypothesis, Amer. Math. Monthly, 109 (2002), 5347–543.] The same paper mentions another inequality of Robin, $$\sum_{d \mid n} d \leq e^\gamma n \log\log n \qquad (n \geq 5041),$$ where $e^\gamma = 1.7810724\ldots$, which is also equivalent to RH. Despite the appearance of $\exp,$ $\log$ and $e^\gamma$, it is a routine matter to express these inequalities as $\Pi^0_1$ statement. (Indeed, the details in Lagarias's paper make this even simpler than one would originally think.)
Yes. This is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem, and some standard number theory. A number of papers have details of the $\Pi^0_1$ sentence. To begin with, take a look at the relevant paper in Mathematical developments arising from Hilbert's problems (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill., 1974), Amer. Math. Soc., Providence, R. I., 1976.
Update, Jun 22/16: Interest in recent work of Scott Aaronson and Adam Yedidia on small Turing machines whose behavior is not decidable in $\mathsf{ZFC}$ had the side effect of leading to explicit examples of Turing machines that halt if and only if there is a counterexample to Riemann's hypothesis. One such machine is described (with links) starting on page 11 of their paper, using Lagarias equivalence mentioned in François's answer. A short discussion (in Spanish), also providing the relevant links, can be seen here. The results were announced in Scott's blog, here.
I realized that none of the answers present what I consider to be the most straightforward $\Pi^0_1$ expression for the Riemann hypothesis, namely bounds on the error term in the prime number theorem. I will write it in terms of Chebyshev’s $\psi$ function as I find it more natural, but it works for $\pi$ just the same. The following are equivalent:
The Riemann hypothesis.
$\psi(x)-x=O(x^{1/2+\epsilon})$ for all $\epsilon>0$.
$|\psi(x)-x|\le\frac1{8\pi}\sqrt x\log^2 x$ for all $x\ge74$.
The equivalence of 1 and 2 is classical, the explicit bound in 3 is due to Schoenfeld. Now, the large leeway between 2 and 3 allows one to write the bound as a $\Pi^0_1$ sentence, even though we cannot compute exactly all the logarithms involved: let $\mathrm{psi}(n)$, $\mathrm{sqrt}(n)$, and $\mathrm l(n)$ be computable functions that provide rational approximations within distance $1$ of $\psi(n)$, $\sqrt n$, and $\log n$, respectively. Then RH is equivalent to $$\forall n\,|\mathrm{psi}(n)-n|\le42+\mathrm{sqrt}(n)\,\mathrm l(n)^2.$$
The beauty of this is not only that it is in line with the form of RH most likely to be useful in elementary number theoretic arguments, but perhaps more importantly, it easily generalizes to extensions of the RH to other $L$-functions.
For a specific formulation, Section 5.7 of Iwaniec and Kowalski’s Analytic number theory states for a large class of $L$-functions (basically, functions in the Selberg class with a polynomial Euler product; the assumptions are somewhat negotiable, in particular I’m confident one can eliminate the Ramanujan–Petersson hypothesis at the expense of somewhat worse bounds) the equivalence of
The Riemann hypothesis for $L(s)$.
$\psi_L(x)-n_Lx=O(x^{1/2+\epsilon})$ for all $\epsilon>0$.
$|\psi_L(x)-n_Lx|\le c\sqrt x\,(\log x)\log(x^dq_L)$.
Here $c$ is an absolute constant that can (in principle) be extracted from the proof, $d$ is the degree of the Euler product, $n_L$ is the order of the pole of $L(s)$ at $s=1$, $q_L$ is a conductor of sorts, and $$\psi_L(x)=\sum_{n\le x}\Lambda_L(n),$$ where $\Lambda_L(n)$ is a “von Mangoldt” function of $L$ extracted from the expansion of the logarithmic derivative of $L$ as a Dirichlet series: $$-\frac{L'(s)}{L(s)}=\sum_{n=1}^\infty\Lambda_L(n)\,n^{-s}.$$ The upshot is that the RH for a class of $L$-functions is $\Pi^0_1$, provided the class is “recursively enumerable”: we can parametrize the class as $L(s,a)$ where the $a$’s are finite objects (including basic data like $d,n_L,q_L$) in such a way that the set of valid $a$’s is r.e., and given $a$, $n$, and $\epsilon>0$, we can compute an approximation of $\Lambda_L(n)$ within distance $\epsilon$ (or equivalently, if we can approximately compute terms of the Euler product).
For example, each of the following can be expressed as a $\Pi^0_1$ sentence:
The RH for Dirichlet $L$-functions.
The RH for Dedekind zeta-functions.
The RH for Hecke $L$-functions.
(The first two classes can be enumerated in a straightforward way. Finite-order Hecke characters are also easily enumerable, as ray class groups are finite and computable. The case of general Hecke characters needs a bit more work, but basically, one can enumerate a basis of suitably normalized infinity types using an effective version of Dirichlet’s unit theorem.)
I can’t tell (but would be interested to hear from someone more knowledgeable) whether the RH for standard automorphic $L$-functions is also $\Pi^0_1$, that is, whether these functions are recursively enumerable. (There are certainly only countably many up to normalization, and polynomially many of bounded analytic conductor, so conceivably this may be true.)