MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I take a list of $2*m$ natural numbers {$n_k$}. I encode them in some way together to a single bit sequence. Now I feed this bit sequence to a Turing machine $T$. Call the statement "For all $n_1$, there exists an $n_2$ so that for all $n_3$, there exists an $n_4$... so that for all $n_{2*m-1}$, there exists an $n_{2*m}$ so that the Turing machine $T$ halts." statement $S_m$.

Now: Can statements of the form "There exists a $m$ so that statement $S_m$ is true" be, in general, formalized within the general notation for number-theoretic statements; does it lie in the Kleene Hierarchy?

share|cite|improve this question
I believe that you are essentially just asking about Post's theorem. It isn't clear to me if the machine $T$ is supposed to be fixed, or if it is a parameter somehow. It is also not clear to me whether this is a research-level question; once the details are clarified Post's theorem will almost certainly give an immediate answer. – Carl Mummert Jan 18 '12 at 12:28

The answer is no.

Consider first the following version of the question. Regarding your Turing machine $T$ as a parameter, let $\varphi_{T,m}$ be the statement: $$\forall n_1\exists n_2\forall n_3\cdots\exists n_{2m}\ \ T\ \text{ accepts }\ \langle n_1,n_2,\ldots,n_{2m}\rangle.$$

The question is whether $\varphi_{T,m}$ is an assertion about $T$ and $m$ that exists in the Kleene hierarchy. In other words, does the set $S=\{(T,m)\mid \varphi_{T,m}\}$ have arithmetic complexity?

The answer to this version of the question is no. This set has hyperarithmetic complexity, which is on top of the Kleene arithmetic hierarchy. The reason is that it is essentially a truth predicate for arithmetic truth. For any $\Sigma_{2m}$ sentence $\forall n_1\cdots\exists n_{2m}A(\vec n)$, where $A$ is $\Delta_0$, let $T$ be a Turing machine accepting the satisfying instances of $A$, and thus $\theta$ is true exactly when $\varphi_{T,m}$. It follows that one can compute all the iterated jumps $0^{(n)}$ from an oracle for $S$, and thus it has higher complexity than $\Sigma_n$ for any particular $n$. Meanwhile, the set $S$ is computable from the omega jump $0^{(\omega)}=\oplus_n 0^{(n)}=\{\langle n,x\rangle\mid x\in 0^{(n)}\}$, since we can decide $\Sigma_n$ truth uniformly from $0^{(n)}$. Thus, the set $S$ is Turing equivalent to $0^{(\omega)}$. This oracle is Turing equivalent to the set $\{{}^\ulcorner\varphi^\urcorner \mid \mathbb{N}\models\varphi\}$, as $\varphi$ ranges over the arithmetic assertions. This set is known as TA, for ``true arithmetic''.

The succinct way to say it is: arithmetic truth is not arithmetic.

Now let's turn to your actual question, which is about the assertion $\exists m\ \varphi_{T,m}$, where you have quantified over $m$. Thus, your question is inquiring about the complexity of the set $\{T\mid \exists m\ \varphi_{T,m}\}$. The argument above gives the hyperarithmetic iterated jump $0^{(\omega+1)}$ as an upper bound on the complexity of this, since we can compute arithmetic truth from $0^{(\omega)}$, and you've added one more quantifier on top of this. Conversely, let's prove that the statement is not arithmetic. For any arithmetic sentence $\theta=\forall n_1\exists n_2\cdot \exists n_{2k}\psi(\vec n)$, where $\psi$ is $\Delta_0$, let $T$ be a Turing machine that accepts $\vec x$ just in case $\vec x$ has length $2k$ and $\psi(\vec x)$ holds. Thus, $\varphi_{T,m}$ holds if and only if $m=k$ and $\theta$ holds. Thus, your statement $\exists m\ \varphi_{T,m}$ holds if and only if $\theta$ holds. Thus, we have reduced TA to your set, and so your set is strictly in the hyperarithmetic hierarchy. So the answer is no.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.