3
$\begingroup$

Possible Duplicate:
Are there languages that are not in RE nor CO-RE?

Let $ALL$ be the language of all decision problems. My question is, is there a language that is neither recognizable or complement-recognizable? If such a language exists, I believe it would be very interesting to study it (if it is possible!).

$\endgroup$

marked as duplicate by Kaveh Apr 1 '11 at 21:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ I'm not really sure, but I think AH is a subset of ALL. So, if AH does not collapse, $ALL\setminus(RE \cup co-RE)$ is nonempty. $\endgroup$ – M.S. Dousti Apr 1 '11 at 15:18
  • 2
    $\begingroup$ Complexity Zoo: "Each level of AH strictly contains the levels below it." That should answer your question. $\endgroup$ – Robin Kothari Apr 1 '11 at 15:39
  • $\begingroup$ Robin, Sadeq, thank you for your comments and your links. I know of the polynomial hierarchy and I've heard of the arithmetical hierarchy, which turns out to be exactly what I was looking for. Can you post your comment as an answer, so that I can accept it? If not, should I just close the question? $\endgroup$ – chazisop Apr 1 '11 at 15:45
  • 1
    $\begingroup$ "Given a computable predicate $P$, decide whether $P(x)$ is both 'true' and 'false' infinitely many times for positive integers $x$." Neither the positive nor negative result can be verified in a finite amount of time. $\endgroup$ – mjqxxxx Apr 1 '11 at 16:04
  • 1
    $\begingroup$ chazisop, this is not a research-level question (the answer can be found in the first chapters of almost any computability textbook or on Wikipedia). I am therefore closing the question as off-topic. $\endgroup$ – Kaveh Apr 1 '11 at 20:41
3
$\begingroup$

I'm posting my comment as an answer, at the request of the OP.

Arithmetic Hierarchy AH is a class of decision problems defined as below:

Let $Δ_0 = \Sigma_0 = \Pi_0 = R$. Then for $i>0$, let

  • $Δ_i = R^ {\Sigma_{i-1}}$.
  • $\Sigma_i = RE ^{\Sigma_{i-1}}$.
  • $\Pi_i = coRE ^{\Sigma_{i-1}}$.

Obviously, AH $\subseteq$ ALL. On the other hand, "each level of AH strictly contains the levels below it." (As pointed by Robin Kothari in a comment above). Therefore, $ALL\setminus(RE \cup coRE)$ is nonempty.

$\endgroup$
  • 2
    $\begingroup$ It's also worth noting that AH doesn't exhaust ALL either - the AH consists essentially of the (union of) the finite jumps of the recursive degree 0, and the operation can be iterated through countable ordinals beyond $\omega$. See en.wikipedia.org/wiki/Turing_jump for more details. $\endgroup$ – Steven Stadnicki Apr 1 '11 at 18:08

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