# Why REC languages is undecidable under emptiness and finiteness?

Membership problem of Recursive languages are decidable.

My approach:

Let $$L$$ be a recursive language and $$M$$ be the Turing Machine that accepts it. For string $$w,$$ if $$w ∈ L,$$ then $$M$$ halts in final state. If $$w ∉ L,$$ then $$M$$ halts in non-final state. (halts always!). That's why Recursive languages are decidable for Membership problem

My question is in same logic, why finiteness, emptiness is undecidable? Don't want any concrete proof. I just want brief concepts like my approach.

To decide whether a language is empty you'd have to run $$M$$ on all possible input strings and verify that $$M$$ always rejects. How are you going to do that in a way that ensures that your algorithm always terminates?

Similarly, to decide whether $$L$$ is finite you'd have to check that $$M$$ rejects almost always, i.e., always except for at most a finite number of inputs.

Formally, you can reduce the halting problem to problem of deciding whether a language $$L$$, encoded as a decider machine for $$L$$, is empty/finite.

For example, given Turing machine $$T$$ you can define a Turing machine $$T'$$ that takes a string $$x$$ as input and simulates $$T$$ on empty input for $$|x|$$ steps. If the simulation ends, $$T'$$ accepts. Otherwise $$T'$$ rejects. Then, you can decide if $$T$$ halts on empty input by checking if the language recognized by $$T'$$ is not empty.

• one thing tell reduction only possible to undecidable to undecidable? Reduction Decidable to undecidable possible? Oct 14, 2021 at 11:09
• empty input means Oct 14, 2021 at 12:09
• I'm not sure how it helps, but yes: it is possible to reduce a decidable language to an undecidable one. Empty input means that the contents of the tape are the empty word, usually denoted with $\varepsilon$. Oct 14, 2021 at 12:29