Decide for a TM M whether L(M) is finite when you already know thet L(M) is regular.

833 Views Asked by At

Consider the following problem: For finite automata it is of course decidable to check if the recognized language is finite, but this obviously not the case for TMs but I wonder if it is possible to decide whether $L(M)$ is finite if you already know (e.g. by some oracle) that $L(M)$ is regular.

I am thinking of an answer where one might construct an FA $\mathcal{A}$ from a TM $M$ with $L(\mathcal{A}) = L(M)$. Is there any way?

Best, Niklas