Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages?
I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and also that all the language that do have Turing machines are in $\mathsf{RE}$, so is it true that for any language that is in $\mathsf{coRE} \setminus \mathsf{R}$ there's isn't a Turing machine? I wonder why is that so, can someone elaborate?
We can associate a language to a Turing machine in several ways.
If the Turing machine halts on all inputs, then the language accepted by the Turing machine consists of all words which cause the Turing machine to halt in an accepting state. The class $\mathsf{R}$ consists of all languages which are accepted by some Turing machine.
For an arbitrary Turing machine, the language recognized by the Turing machine consists of all words that cause the Turing machine to halt (in any state). The class $\mathsf{RE}$ consists of all languages which are recognized by some Turing machine.
If $L \in \mathsf{coRE} \setminus \mathsf{R}$, then in particular $L \notin \mathsf{R}$, and so no Turing machine accepts $L$. If $L$ were recognized by some Turing machine then $L \in \mathsf{RE}$. However, this is impossible, since then $L \in \mathsf{RE} \cap \mathsf{coRE} = \mathsf{R}$.
Let me expand on the first sentence of Yuval Filmus' answer:
We can associate a language to a Turing machine in several ways.
Yuval mentions two: acceptance (which characterizes $\mathsf{R}$) and recognition (which characterizes $\mathsf{RE}$). There are others, however. Most obviously, we could consider "co-recognition" - say that a Turing machine $M$ "co-recognizes" a language $L$ if the strings in $L$ are exactly the strings on which $M$ does not halt. Then of course co-recognition characterizes $\mathsf{coRE}$.
However, that's a bit unnatural. Much more natural in my opinion is the notion of limit computability. Phrased in terms of natural numbers for simplicity, this is the following:
A function $f:\mathbb{N}\rightarrow\mathbb{N}$ is limit computable iff there is a computable function $h:\mathbb{N}^2\rightarrow\mathbb{N}$ such that $$f(x)=\lim_{s\rightarrow\infty} h(x,s),$$ or more precisely such that for all $x$ there is some $n$ such that for all $s>n$ we have $h(x,s)=f(x)$.
A set $X$ is limit computable, meanwhile, iff there is some limit computable function $f$ such that $X=\{i: f(i)=1\}$. (There are many other equivalent formulations of this.)
It turns out that limit computability has a very nice alternate characterization:
(Shoenfield) A function $f$ is limit computable iff it is computable relative to the halting problem $\emptyset'$.
(And via Post we get another characterization in terms of "definitional complexity.")
Of course this includes both $\mathsf{RE}$ and $\mathsf{coRE}$, and much more besides: there are sets computable relative to the halting problem which are not Turing equivalent to any set in $\mathsf{RE}$. (This is hard to prove!)
And there are even more ways to assign languages to sets; for example, we can talk about "limit recognizability" (which is to limit computability as recognizability is to acceptance), which gives us the $\Sigma^0_2$ languages.
