Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on the following problem: let $W_e$ be the computably enumerable set which is the domain of the $e$-th Turing program, and $K$ be the Halting problem, at which level of the arithmetic hierarchy does each of the following sets appear?

  1. $A_1=\{e: W_e$ contains no even numbers $\}$
  2. $A_2=\{e: W_e$ contains some element of $K\;\}$
  3. $A_3=\{e: W_e$ contains every element of $K\;\}$
  4. $A_4=\{e: W_e$ is infinite $\}$

I think $A_1 \in \Pi_1$ because it can written as $A_1=\{\exists x \in W_e (\forall n \neg (x=2n) )\}$, i.e. one universal and one bounded quantifier. I'm a little bit worried that the bounded set is c.e., does it change things?

Since $K \in \Sigma_1$ and $A_2=\{e: \exists x \in W_e (x \in K)\}$, $A_2$ is in $\Sigma_1$, but it's not $\Pi_1$ so it's not $\Delta_1$.

$A_3=\{e: \forall x \in K (x \in W_e)\}$ so it's $\Pi_1$

I'm not sure what to do with $A_4$

I would also like to view these sets in the context of Turing machine, but can't wrap my head around it.

share|improve this question
@Arturo Thanks for adding the \text, I tried that but the font that it produces is different than the font that the page uses (at least on my browser, which I think uses Times News Roman). I also tried \textrm which has the same problem, while \textnormal is not recognized. –  nullgraph Aug 24 '11 at 19:13
I couldn't quite understand what the problem was that created the LaTeX error (the box surrounding the closing }) in the first and fourth sets, which is why I did it this way. You can undo it if it's too much of an issue with your display (I know what you mean and it happens when I browse at home, but it's never bothered me much, especially when the text is in a stand-alone formula as it is here), but if you do please try to figure out what the LaTeX error is and correct it. –  Arturo Magidin Aug 24 '11 at 19:17
Okay, I've semi-reverted. I think it's a MathJax problem of some sort: I could reproduce the LaTeX error if there was no space between the final { and the preceding text in the first and fourth line, but for some reason after I added some other space in the second and third lines, it stopped complaining. Anyway, I hope this looks the way you hoped. –  Arturo Magidin Aug 24 '11 at 19:21
@nullgraph: I'm not sure about your notion of "bounded quantifier". Are you suggesting that $K$ is recursive, since $K = \{x : x \in K \}$? Why makes $\exists x \in W_e$ bounded, and what are the implications for the arithmetic hierarchy? –  Yuval Filmus Aug 25 '11 at 17:10
@Yuval, the definition we had in my class didn't say anything about the bounding set being finite, I was confused about this as well. –  nullgraph Aug 26 '11 at 2:20
show 2 more comments

3 Answers

up vote 2 down vote accepted

$(x \in K)$ or $(x \in W_e)$ does not count as a bounded quantifier in Computability Theory where bounded means bounded by a number. Note this is different than in the first order theory of Set theory.

For all of these, my Halting Problem or Jump $K$ is defined as $K = \{e : \Phi_{e}(e) \downarrow\}$. The notation $\Phi_{e,s}(x)$ means run the $e^\text{th}$ Turing Program for $s$ steps on input $x$. The important part is that this is computable.

  1. On the surface, $A_1$ is $\Pi_1^0$.

$A_1 = \{e : (\forall n)(\forall s)(\Phi_{e,s}^\emptyset(2n)\uparrow)\}$

This is $\Pi_1^0$. In fact, it well known that $K$ is the $\Sigma_1^0$ 1-complete (complete via 1-reductions). Therefore, the complement of $K$ is $\Pi_1^0$ 1-complete. The claim is that $A_1$ is also $\Pi_1^0$ 1-complete. Define the function $f$ as follows :

$\Phi_{f(e)}(x) = \begin{cases} 1 & \quad x = 0 \wedge (\Phi_e(e)\downarrow) \\ \uparrow & \quad \text{otherwise} \end{cases}$

By some theorem (maybe the s-m-n theorem), the function $f$ exists and is injective and used to prove the 1-reduction $\bar{K} \leq_1 A_1$. That is, if $e \in \bar{K}$, then $W_{f(e)} = \emptyset$. Thus $f(e) \in A_1$. If $e \in K$, then $W_{f(e)} = \{0\}$, then $f(e) \notin A_1$. Thus $\bar{K} \equiv_1 A_1$.

For the second one, one can write

$A_2 = \{e : (\exists x)(\exists s)(\Phi_{x,s}(x)\downarrow)\}$

This is $\Sigma_1^0$. This set is also $\Sigma_1^0$-complete. Define the function $f$ as follows :

$\Phi_{f(e)}(x) = \begin{cases} 1 & \quad x = e \\ \uparrow & \quad \text{otherwise} \end{cases}$

Note that $W_{f(e)} = \{e\}$. Thus, this function witnesses $K \leq_1 A_2$.

The third one as far as I can tell is $\Pi_2^0$

$A_3 = \{e : (\forall n)((\exists s)(\Phi_{n,s}(n)\downarrow) \Rightarrow (\exists t)(\Phi_{e,t}(n)\downarrow))\}$

I believe $A_3$ is $\Pi_2^0$ 1-complete. $A_4$ or $Inf$ is $\Pi_2^0$ complete (as I will say again below). I will show $A_3$ is $\Pi_2^0$ complete by reducing $Inf$ to it. Define the function $f$

$\Phi_{f(e)}(x) = \begin{cases} 1 & \quad (\exists s)(\exists t)(s > x \wedge \Phi_{e,t}(s)\downarrow \wedge \Phi_{e,s}(e)\downarrow \\ \uparrow & \quad \text{otherwise} \end{cases}$

I believe this function witness that $Inf \leq_1 A_3$. If $e \in Inf$, then $W_{f(e)}$ contains $K$ since if $x \in K$ there exists a $s > x$ such that $s \in W_e$ and $\Phi_{e,s}(e)\downarrow$. Thus $x \in W_{f(e)}$. If $e \notin Inf$, then $W_e$ is finite. Let $j$ be the largest element in $W_e$. Since $K$ is infinite, it is clear that $W_{f(e)}$ does not contain $K$ since $W_{f(e)}$ is bounded by $j$.

The fourth one is well known. It is often called Inf

$A_4 = Inf = \{e : (\forall n)(\exists x)(\exists t)(x > n \wedge \Phi_{e,t}(x)\downarrow)\}$

$Inf$ is $\Pi_2^0$ complete. Look in Soare's book for a proof.

If my proofs are correct, all you sets above can certainly be defined by a $\Pi_1^0$, $\Sigma_1^0$, $\Pi_2^0$ and $\Pi_2^0$ formula, respectively, but in some sense you can even prove the lowest they can be on the hierarchy are these places.

share|improve this answer
add comment

The class of recursive languages consists of those languages for which there exists an algorithm that always terminates and answers correctly whether a given input belongs to the language or not. For example, consider the language of all triples $(e,x,t)$ such that the $e$th program, when run on input $x$, stops after at most $t$ steps. This language is recursive since you can simulate the $e$th program on input $x$, and after at most $t$ steps of the simulation, you can tell whether the triplet belongs to the language or not.

Some languages, however, are not recursive. An example is the language $K$ of those programs that halt on the empty input. A classical argument shows that $K$ cannot be recursive. Hypercomputation comes to our rescue. Consider the following algorithm for deciding whether $e$ belongs to $K$:

  1. Put false in the variable flag.
  2. For $t = 0$ to $\infty$: Simulate $e$ for $t$ steps, and if it halts, put true into flag.
  3. Return flag.

We schedule the iteration of step $2$ to run in times $1/2,1/4,1/8,\ldots$, and run step $3$ at time $1$. So step $3$ runs after all the infinite number of iterations of step $2$, and can tell whether the program $e$ ever halts or not. Of course, this is not realistic since we cannot really run our program in ever-increasing speeds, so that's why we call it "hypercomputation".

We can abstract this process of "compressing time" by forgetting about the mechanism, and replacing it by a quantifier: $\exists t$ such that program $e$ halts after $t$ steps. We call this "existential compression", and term the languages that can be computed this way $\Sigma_1$. In this type of compression, the hypercomputation accepts iff at least one of the compressed computations accept. The notation comes from the fact that for indicator (zero/one) variables $v_i$, we have $\sum_i v_i \geq 1$ iff there exists some $i$ such that $v_i \geq 1$.

There is also "universal compression", in which the computation rejects if at least one of the compressed computations reject. This is denoted $\Pi_1$, which reminds us of the rule $\prod_i v_i = 0$ iff $v_i = 0$ for some $i$. The corresponding quantifier is $\forall$.

Why are existential and universal compressions considered different? Suppose we take a two-parameter algorithm, and compress it existentially twice. This operation might seem more complicated than single compression, but in fact it's perfectly possible to do the compression only once. All we need is some way to enumerate over all pairs of integers: double existential compression amounts to running some recursive algorithm $A(x,y)$ on all possible pairs $(x,y)$, and deciding whether any of the executions accept. We can replace the enumeration over all pairs by an enumeration of some single variable $z$, and then convert $z$ to $(x,y)$ as follows: $$ 0 \mapsto (0,0) \; 1 \mapsto (1,0) \; 2 \mapsto (0,1) \; \cdots. $$ So compressing time existentially twice is no stronger than doing it once. The same applies for universal compression. But if we alternate two different kinds of compression, we do get something stronger. Consider, for example, the language of all $e$ such that the $e$th machine halts on all inputs. This can be written as $\forall x \exists t$ such that $e$ halts on $x$ after at most $t$ steps. So first we compress existentially (over $t$), then universally (over $x$). An argument similar to the one showing that $K$ isn't recursive also shows that this new language isn't $\Sigma_1$ or $\Pi_1$. So we've gained something by alternating quantifiers.

Finally, let's address your confusion about bounded quantifiers. These are quantifiers which are bounded by some definite quantity. Consider, for example, the language of all $e$ such that the $e$th mating halts on every input $x$ after at most $2^x$ steps. This can be realized as $\forall x \exists t \leq 2^x$ such that $e$ halts on $x$ after at most $t$ steps. We don't need any "tricks" to handle the quantification over $t$, since all we need is to try all values of $t$ between $0$ and $2^x$, and then we know the answer. So this bounded quantifier "doesn't count". Something like $x \in K$ isn't bounded, since $K$ isn't recursive. It is shorthand for "$\exists t$ such that $x$ halts after $t$ steps", and here the $t$ isn't bounded. The classes $\Sigma_k$/$\Pi_k$ are define by $k$ alternating quantifiers and then a recursive predicate (= language). The predicate $x \in K$ isn't recursive.

share|improve this answer
add comment

As I understand, by "$W_e$ is infinite" you mean that $\varphi_e(x)$ halts for infinitely many $x$, where $\varphi_e$ is the TM corresponding to $e$.

The set $W_e$ is infinite iff for every $x$ there is some $y > x$ which is in $W_e$, i.e. for every $x$ there is some $y > x$ such that $\varphi_e(y)$ halts. Does that help?

share|improve this answer
I see, I forgot that I could use <, and was thinking that I need infinitely many $\neg(x_1 = x_2)$. So since $\exists x$ and $\exists y$ are both bounded by $W_e$ is $A_4$ in $\Sigma_0$ then? –  nullgraph Aug 24 '11 at 19:23
$\Sigma_0$ is the class of recursive sets. Is $A_4$ recursive? Take another look at your quantifiers. –  Yuval Filmus Aug 25 '11 at 17:07
add comment

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.