Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable?

Question

Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable? My intuition tells me the answer should be no, but I can't prove it.

I know that it should be non-recursive because the property is nontrivial (i.e there are some TM-recognizable languages which have this property and some which do not), by Rice's theorem.

Also by Rice's theorem, if P is a non-monotone property then Lp (the set of all TMs whose language satisfies P) is not r.e.

However, the property "includes the set of all even length strings" appears to be monotone, since if a set includes the set of all even length strings, then all supersets of that set must also satisfy that property.

On the other hand, the opposite property, let's call it Q, "does not include the set of all even length strings" does not seem to be monotone, hence Lq should be non-recursively-enumerable.

This doesn't prove anything though, since knowing that the complement of a set is non-r.e doesn't tell you anything about the cardinality of the set itself. That's where I'm stuck.

Answer 1

Your intuition is right - this language (call it "$L$") is not r.e. You are also right that this is going to take a bit more work than just using monotonicity.

Informal explanation. To tell that $e$ is in $L$, I need to check that $\Phi_e(\sigma)=1$ for every even-length $\sigma$. This is not a fact I can convince myself of in finite time! Keep in mind that a language is r.e. if (informally) given any $\sigma$ in the language, there is some finite amount of information which would convince me that $\sigma$ is in the language.

Formal explanation. We can actually show that $0''$ - the Halting Problem's Halting Problem - is reducible (in fact, equivalent to) $L$. This not only shows that $L$ is not r.e., but even that $L$ is strictly more complicated than any r.e. language! This isn't too hard: we can construct a computable total $f$ such that $\Phi_e$ is total iff $\Phi_{f(e)}$ accepts every string of even length - let $\Phi_{f(e)}(\sigma)$ (for $\sigma$ even length) chop off the first half of $\sigma$, and run $\Phi_e$ on the rest; and if that halts, then $\Phi_{f(e)}$ accepts. (And $\Phi_{f(e)}$ automatically rejects odd-length $\sigma$s, say.)

At this point, all we need is that the set of indices of total machines has degree $0''$, but this is a standard exercise.

Answer 2

There is a technique, called the Tarski--Kuratowski calculation by Rogers, which allows you to compute an upper bound on the noncomputability of this kind of set. There is a phenomenon that, once we have the natural upper bound, most specific sets we look at will actually be at the strength of the upper bound. The upper bound is stated in terms of the arithmetical hierarchy.

In this case, the upper bound is obtained as follows:

• A program is in the set if and only if it halts on every string of even length.
• So, a program is in the set if and only if, for every string of even length, there is some finite number of steps after which the program halts on that string.
• So, the set is $\Pi^0_2$ in the arithmetical hierarchy.

Now, by Post's theorem, a set is r.e. if and only if it is $\Sigma^0_1$ in the arithmetical hierarchy. Since our upper bound is $\Pi^0_2$, this suggests (by the phenomenon above) that we should try to prove our set is $\Pi^0_2$ complete, which will then show that the set is not $\Sigma^0_1$.