Is the Collatz conjecture in $\Sigma_1 / \Pi_1$? Prompted by some of the comments on this question, I'm wondering if anything is known about the place of the Collatz Conjecture in the arithmetic hierarchy.  More specifically, is Collatz known to be equivalent to a $\Sigma_1$ or $\Pi_1$ statement?  It's obvious that it can be expressed in the second level of the hierarchy, as $\forall n\exists k . C^{(k)}(n) = 1$ (and I believe functional composition is $\Delta_0$, so the fact that we're using a slightly extended language here should be moot; we can encode the computational path involved in computing $C^{(k)}(n)$ as a finite sequence of integers and thus as a single integer by appropriate coding), but there doesn't seem to be any obvious way of expressing it as a first-level statement...
As suggested in my comment above, I will interpret your question as asking whether the Collatz conjecture is provably equivalent to a $\Pi_1$ or $\Sigma_1$ sentence over some base theory $T$. There are a variety of issues at stake depending on the outcome of the conjecture (in the standard model).

Case 0: The Collatz conjecture is false because some Collatz sequence is periodic with a period other than $4,2,1$. In that case, the Collatz conjecture is provably equivalent to $0=1$ over any theory with enough power to encode and decode the witnessing sequence up to its first repetition (e.g. PA or I$\Sigma_1$).

Case 1: The Collatz conjecture is false because some Collatz sequence never repeats itself. In that case, the conjecture is perhaps equivalent to a $\Pi_1$ sentence. To say that the Collatz sequence starting with some standard number $n_0$ is never repeating is a $\Pi_1$ statement. In the strange scenario where the Collatz sequences that don't repeat are precisely the ones that go through $n_0$, then the Collatz conjecture is equivalent to that $\Pi_1$ statement. More generally, if there is a (standard) finite list $n_0,n_1,\dots,n_k$ such that the Collatz sequences that don't repeat are precisely those that go through one of these, then we also have a $\Pi_1$ sentence equivalent to the Collatz conjecture. Still more generally, if there is a computable sequence $n_0,n_1,\dots$ with that property, we also have a $\Pi_1$ sentence equivalent to the Collatz conjecture. However, if no such computable sequence exists then it is unlikely that we can do better than $\Sigma_2$ unless we use a non-axiomatizable base theory like the $\Pi_1$ theory of the standard model.

Case 2: The Collatz conjecture is true. In that case, the Collatz conjecture is equivalent to the statement that $g(n) = (\mu k)(C^k(n)=1)$ is a total computable function. We can then compare $g$ to various levels of the fast-growing hierarchy for a more precise analysis. For example, if $g(n)$ is bounded above by some $f_k$ where $k$ is finite, then $g$ is actually primitive recursive and the Collatz conjecture is provably true in I$\Sigma_1$ (same as PA except that induction is restricted to $\Sigma_1$ formulas). If $g(n)$ is abounded above by some $f_\alpha$ with $\alpha \lt \varepsilon_0$, then the Collatz conjecture is provably true in PA. If $g$ grows faster than that then a still stronger theory is required to prove the Collatz conjecture.
See http://matwbn.icm.edu.pl/ksiazki/aa/aa91/aa9146.pdf 
"A binomial representation of the 3x + 1 problem" by Maurice Margenstern and Yuri Matiyasevich.