Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Question

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of languages S?

I'm stuck with the following instance of that problem: $L = \{ \langle M \rangle \mid M \text{ is a } TM, L_M \in \mathrm{REG}\}$. I have found proof that it is undecidable, however I'm stuck at finding if it's recognizable (synonyms: Turing-acceptable, semidecidable, ...) or not.

The problem in words means: Given a TM M, does the TM decide a language that is an element of REG (the set of regular languages)?

To prove a language is not semi-decidable, I would try to prove that it's complement is semi-decidable and that the language is not decidable (which I did by reduction from the Halting-problem).

To prove it is semi-decidable, I would prove it by reduction to the $A_{TM}$, which is semi-decidable.

I have tried both for this problem, but I get stuck / lose my way of thinking at every try ... Some directions would be greatly appreciated!

Answer 1

You have a good idea for proving that $L$ is not semi-decidable but it's not going to work since neither $L$ nor $\overline{L}$ are semi-decidable. Intuitively, how can saying after finite time "this language is not regular" be easier than "this language is regular" -- you can only inspect finitely many inputs, and all finite languages are regular (thus we can not separate REG from other classes on finite samples).

So we are left with our basic device: reduction from a non-semi-decidable language. The canonical one is the complement of the halting problem, i.e.

$\qquad\displaystyle \overline{K} = \{ \langle M \rangle \mid M(\langle M \rangle) \text{ loops}\}$.

Now we have to define a function for every $M$ whose accepted language is (non-)regular depending on whether $M$ halts on itself in order to establish the contradiction.

So, for any fixed TM $M$, define the following function¹:

$\qquad\displaystyle f_M(w) = \begin{cases} 1, & w = a^n b^n \land M(\langle M \rangle) \text{ terminates after at most $n$ steps} \\ 0, &\text{else} \end{cases} $

The function $f_M$ is clearly computable for any $M$; just check the form of the input and simulate $M$ for $n = \frac{|w|}{2}$ steps if necessary. Note furthermore that given $\langle M \rangle$, we can compute $\langle f_M \rangle$; such compilation is possible because we have (or can assume) a Gödel numbering.

Now we have what we always want when reducing, the equivalence of doom:

$\qquad\displaystyle \langle M \rangle \in \overline{K} \iff \mathcal{L}(f_M) = \emptyset \iff \mathcal{L}(f_M) \in \mathrm{REG}$,

since $\mathcal{L}(f_M) = \{a^n b^n \mid n \geq N \} \not\in \mathrm{REG}$ if $M(\langle M \rangle)$ halts after $N$ steps, i.e. $\langle M \rangle \in K$.

Thus, if we had a semi-decider for your $L$, we could semi-decide $\overline{K}$ which contradicts what we know.

---

1. For ease of notation I use strings as inputs; of course, we'd work on naturals using some computable bijection.